B_log

문제 - 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()) # 연..

문제 주어진 입력에서 {}와 ()가 제대로 짝을 이루는지 확인한다. 정상적인 짝인 경우 1을, 아니면 0을 출력한다. 문제 상황 - 두 종류의 괄호이므로 스택을 활용해 매칭을 확인한다. 해결 전략 - 짝을 이루는 두 괄호가 있으므로 dict자료형을 이용하여 스택에 push, pop 한다. 코드 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 # testcase 개수 T = int(input()) for idx in range(T): # 짝을 확인 할 dictionary brackets = {'}':'{', ')':'('} # 입출력을 확인할 stack check = [] testcase = l..

문제 - N개의 정수를 가장 큰 수, 가장 작은 수, 2번째로 큰 수, 2번째로 작은 수의 식으로 정렬한다. 문제 상황 - 최대값과 최소값을 찾는게 아니라 계속 큰 값과 작은 값을 출력해야하므로 선형시간에 해결하기가 어렵다. 10개만 만들면 되므로 변수를 5개씩 만들어 top5, bot5 를 비교해가면 O(N)에 비교 가능하다. 해결 전략 - top list = [, , , ,] 처럼 변수 리스트를 두개 만들면 O(N)에 가능하지만 범위가 크지 않으므로 그냥 O(NlogN)의 sorted 함수를 사용하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T = int(input()) for idx in range(T): N = int(input()) N_list = list(m..

문제 집합 A는 1부터 12까지의 숫자를 원소로 가지고 있다. 이 때, 원소의 개수가 N개이며 그 합이 K인 부분집합의 개수를 출력한다. 문제 상황 - 부분 집합을 완전 탐색으로 전체 조사해야한다. 해결 전략 - 원소의 개수가 12개 이므로 부분집합의 총 수는 공집합을 포함하여 2^12 = 4096으로 크기가 작기 때문에 완전탐색으로 하여도 문제가 없다. 완전탐색하며 합이 K와 같은지를 판별하면 된다. 코드 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 # 부분 집합의 집합을 찾는 함수 def subset(lst): n = len(lst) # 부분 집합들을 담을 집합 result = [] #..

문제 문제 상황 - 각각 빨간색과 파란색으로 칠해진 부분이 주어지고 이 두 부분이 겹쳐 보라색이 된 부분의 넓이를 구한다. - 같은 색이 다시 칠해지는 경우 겹쳐지는 색이 의미가 없으므로 반드시 다른 색이 겹쳐져 색이 변한 것을 처리해야한다. (예를 들어, color red = 1, color blue =2 일 때, red를 2번 칠하면 2가 된다고 blue가 되는 것이 아니다.) 해결 전략 - 문제의 조건이 색깔이 2개 밖에 없는 점에 주목한다. 1 1 2 같이 색칠이 될 경우는 기존에 1이 있으면 1을 안 칠한다는 조건, 즉 기존 색깔에 다를 경우만 칠한다고 설정할 수 있지만 1 2 1 처럼 칠하면 이미 3인 보라색이 되어버려 여기에 또 1을 더해 4가 된다. 그래서 조건을 3보다 작은 동시에 기존 ..