본문 바로가기

전체 글

 (97)
백준 1158번 - 요세푸스 접근 방식 문제를 보고 패턴(k값)이 있는 원형수열(?)임을 생각하고 전에 풀어봤던 풍선터뜨리기 문제가 떠올라서 그 문제 풀이와 같이 front와 back을 바꿔 원으로 돌아가는 패턴을 구현할 수 있는 덱(deque)을 통해 접근해 보았다. 논리 흐름(알고리즘) 주어진 사람 수 만큼의 숫자를 넣고, 주어진 key-1번(숫자가 pop되면서 1번 실행) front값을 back값으로 보내주면 front값에 순서대로 구할 값이 남게 된다. 러시안룰렛처럼 key번 돌리고 총알을 쏜다고 생각하면 된다. 총알이 다 떨어질 때까지 이 과정을 반복하면 답이 나온다. 마지막 출력 조건에서 삐끗했는데, 반복문에 단순히 ", "출력을 더해주면 마지막에 로 출력되기 때문에 따로 조건문을 걸어주었다.
백준 1406번 - 에디터 접근방식 커서의 왼쪽과 오른쪽을 구분하여 문자 하나하나 순서대로 최신화하기에 스택이 적합하다고 생각하여 문제를 풀어나갔다. 이 과정에서 처음엔 스택을 하나로 설정하였는데, 왼쪽과 오른쪽을 나누는 과정에서 스택을 2개로 나누어 따로따로 해결해 나가는것이 합리적이라는것을 깨달았다. 논리 흐름(알고리즘) 커서를 기준으로 왼쪽 문자들을 left스택에, 오른쪽 문자들을 right스택에 저장하고, 커맨드 키가 L일 경우 오른쪽 스택에서 왼쪽 스택으로 문자를 옮겨주고 R일 경우 왼쪽 스택에서 오른쪽 스택으로 문자들을 최신화 시킨다. B와 P일 경우에는 커서의 왼쪽 문자를 바꾸어주기 때문에 left스택에서 최신화 시켜주었다. 구현 과정에서 char형이기 때문에 가독성을 위해 switch문으로 구현할 수 있었다. 마지막..
백준 10799문제 - 쇠막대기 문제 접근방법 처음엔 입력값으로 막대와 레이져 모양을 문자열로 받고 레이져가 나올 경우의 나누어지는 막대값을 세아리면 된다. 레이져가 나올때 마다 막대의 개수가 각각 다를 수 있기때문에 현재의 막대 개수를 순차적으로 삽입 삭제가 유용한 스택을 사용하면 되겠다고 생각했다. 논리 흐름(알고리즘) 처음에는 입력값을 문자열로 받고 이를 스택에 저장하면서 ')' 가 나오면 레이져일테니까 스택에 저장되어있는 '(' 수를 더해주면 되겠다고 생각했으나, ')' 가 나올때 레이져일 경우와 막대일 경우로 2가지로 나누어진다고 깨달았다. 만약 ')' 가 등장했을 때 레이져일 경우 '(' 가 저장되어있는 수를 결과값에 더해주고 ')'가 등장했을 때 막대가 끊기면서 결과값에 +1을 더해준다. 이 때 막대 안에는 무조건 레이져가..
백준 2346번 - 풍선터트리기 이 문제는 정확히는 기억 안나지만 예전에 풀었던 수건돌리기(?) 문제와 비슷하다고 느꼈다. 정방향으로 가면 프론트를 백으로, 역방향으로 가면 백을 프론트로 보내면 된다. 여기서 주의할 점은 자주 등장하는 pair의 활용과 정방향으로 갈 땐 풍선이 터지면서 프론트가 다음 풍선으로 바뀌기 때문에 tmp--를 따로 해주었고 역방향으로 갈 땐 풍선이 터지더라도 백과 상관이 없기 때문에 tmp++를 따로 해주지 않는다는 점이다.
백준 17219번 - 비밀번호 찾기 간단한 map에 대한 활용을 묻는 문제이다. 맵에 각 사이트와 비밀번호를 짝지어 저장하고 찾는 사이트의 비밀번호를 찾아서 출력해주면 된다.
백준 2841 문제 - 외계인의 기타 연주 문제 이해를 먼저 하자면 누르고 있던 프렛값 보다 주어진 프렛값이 더 크면 그냥 그 위에 누르면 되고(높은 프렛값의 소리만 나옴), 주어진 프렛값이 더 작으면 더 높은 프렛값들의 손가락을 떼고 누른다(높은 프렛값이 주어진 프렛값이 되도록). 예를 들어 1번 줄의 프렛을 누르다가 다른줄의 프렛이 주어지더라도 기존 줄의 프렛은 안떼도 된다. 먼저 라인이 비어있을 때는 간단하게 프렛값 삽입 후 다음 루프로 넘어간다. (16~19 줄) 라인이 비어있지 않으면 주어진 프렛값이 가장 큰 수가 될 수 있도록 세팅(주어진 프렛값 보다 큰 프렛값 삭제) 후 주어진 프렛값을 삽입해준다. (22~30 줄) 이 과정에서 삽입과 삭제(pop(),push()) 연산의 수를 구하는것이 답이다.
백준 2075 - N번째 큰 수 처음에 벡터를 통해 n*n 수를 각각 삽입하고 n*n-n번째 수(N번째 큰 수)를 출력했는데 메모리 초과가 나왔다. 문제를 읽어보니 12MB 메모리 제한이 있었다. 1500*1500 = 2250000이고 int는 4byte이니까 대략 8.~MB를 사용한다고 생각하니 단순하게 배열 크기를 할당하고 오름차순 정렬 후에 n*n-n 수를 출력하였다.
백준 7785번 - 회사에 있는 사람 사람 이름과 출퇴근 현황을 짝 지어 풀기 위해 1302번과 같이 map으로 접근하여 풀었다. map의 데이터 저장 방식을 알고 있어서 막힐 부분은 딱히 없었다. 주의할 점은 출력 순서가 역사전이기 때문에 반복문 순서를 뒤집었다. 반복문 조건때문에 map.begin은 따로 출력해주었다. 문제풀이 논리를 서술하자면, 이름과 출근 현황을 최신화하여 저장 역사전순으로 출력 반복문 조건으로 인해 첫 데이터 따로 출력

티스토리툴바