B_log

문제 - NxN의 배열이 주어질 때에 각 row에서 숫자를 선택해나가는데 한 column에 한 요소만 선택되게하여 최소 합을 구한다. 문제 상황 - 하나의 선택이 다음 선택에 영향을 미치는 구조이므로 단순히 최소값들을 모으는 것으로 최소합을 구할 수 없다. 해결 전략 - 완전탐색으로 하기에는 경우의 수가 너무 커질 수 있어 backtracking의 pruning 조건을 삽입한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 # row를 파라미터로 받는 최소 합을 찾는 함수 def find_min(row): global part..

문제 - 기존에 풀었던 미로 문제와 흡사하지만 이동한 최소거리를 계산하는 문제이다. 이동 가능 위치는 0, 벽은 1, 출발점은 2, 목적지는 3이다. 문제 상황 - 기존에는 목적지 도착이 가능한지 여부였지만 이번에는 최소 거리다. 그냥 거리가 아니라 최소거리이므로 조건을 잘 설정해야한다. 해결 전략 - 재귀를 이용한 풀이에 문제가 있어 큐를 이용해 다시 풀었다. distance 배열을 만들어 큐가 돌때마다 (해당 위치 +1) 값을 저장해 출발점(2)에서 부터의 거리를 계산하였다. - visited 항목을 통해 이미 도착한 위치를 파악하고 변수 하나를 추가해 이동한 거리를 파악한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

문제 - N개로 이루어진 수열에서 맨 앞의 값을 맨 뒤로 보내는 작업을 M번 했을 때, 맨 앞의 값을 구한다. 문제 상황 - 원형큐의 모형을 하고 있다. 해결 전략 - 실제로 원형큐를 구현할 필요 없이 index의 움직임만으로 쉽게 구현 가능하다. 코드 1 2 3 4 5 6 7 8 9 10 11 # testcase T = int(input()) for idx in range(T): N, M = map(int, input().split()) N_list = list(map(int, input().split())) # 큐의 맨 앞 front = 0 # 맨 앞의 인덱스를 N%M만큼 이동 front += M%N # 주어진 요소를 출력 print(f"#{idx+1} {N_list[front]}") cs 해설 - ..

문제 - 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는다. 기준은 [(i+j)//2 + 1: ]이 된다. 문제 상황 - 기저조건까지 리스트를 세분화해서 내려간 뒤 다시 위로 올라오며 조건을 판단한다. 해결 전략 - 숫자 1이 가위, 2, 2는 바위, 3은 보 이므로 조건을 통해 대소비교를 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 # 가..

문제 - NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하여 도착할 수 있으면 1, 아니면 0을 출력한다. 출발지는 2이고 도착지는 3이다. 1은 벽이고 0이 진행할 수 있는 경로이다. 문제 상황 - 방문 여부를 체크하며 방문하지 않은 곳을 방문하여 3이 아닐 시에 그 주변을 탐색한다. 해결 전략 - search 함수를 만들어 방문 위치를 갱신하며 3을 찾고, 못찾았을 경우 그 주변의 0을 찾아 다시 그 위치에서 탐색을 시작한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 # 0 통로, 1 벽, 2 출발점, 3 도..

문제 후위 표기법을 이용한 연산은 다음과 같은 규칙을 가지고 있다. 1. 숫자는 스택에 넣는다. 2. 연산자를 만나면 스택의 숫자 두 개를 꺼내 더하고 결과를 다시 스택에 넣는다. 3. ‘.’은 스택에서 숫자를 꺼내 출력한다. 연산이 불가능할 경우 'error'를 출력한다. 문제 상황 - 형식이 잘못된 경우를 정의해야한다. 연산자를 만났을 때 꺼낼 숫자가 2개 미만이면 연산이 불가능하다. 해결 전략 - 문제의 조건을 그대로 시뮬레이션 하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 # testcase 입력 T = int(input()) # testc..

문제 - 문자열 s의 반복된 부분을 삭제한다. 연속문자를 계속 지워나간다. CAAABBA 의 경우 AA를 지워 CABBA가 되고 BB를 지워 CAA, 다시 AA를 지워 C만 남는다. 남은 길이를 출력한다. 문제 상황 - 연속되는 문자를 지우는 상황으로 카카오 문제의 인형뽑기 문제와 비슷하다. 연속으로 같은 것이 있으면 지워지는 개념이다. 해결 전략 - stack을 활용해서 채워나가면서 마지막 두 값이 같은지를 확인하는 부분을 만든다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 T = int(input()) for idx in range(T): s = list(input()) # 들어오는 문자를 확인할 스택 stack = [] # stack에 채울 숫자를 하나하나 확인..

문제 노드들이 주어질 때 출발점에서 목표로 도달할 경로가 존재하면 1을 출력, 없으면 0을 출력한다. 문제 상황 - 단방향 연결이며 depth를 찾는게 아니라 경로의 존재여부를 탐색하는 것이기 때문에 쉬운 문제다. 해결 전략 - DFS / BFS 모두 활용 가능하지만 직관적인 DFS를 활용하기 위해 스택을 사용하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 # testcase 개수 T = int(input()) for idx in range(T): # v = 노드의 수, e = 연결의 수 v, e = map(int, input().split()) # 연..