ALGORITHM (31) 썸네일형 리스트형 [알고리즘] DFS (Depth First Search) DFS (Depth First Search) 그래프를 전체 탐색하는 깊이 우선 탐색 DFS는 탐색을 시작한 시작점부터 해당 부분을 완벽하게 탐색하고 다음으로 넘어가는 방식이다. 아래 그림을 보면 좀더 빠르게 이해할 수 있다. 위 그림처럼 한개의 분기에 대해 모든 탐색이 완료되면 다음 분기로 넘어가고, 완벽하게 탐색한 후에 다음 분기로 넘어가는 흐름을 띄고 있다. 이는 스택, 재귀호출 방식으로 구현할 수 있다. 일반적으로 재귀호출을 사용하였을때 구현하기 편해 자주 사용하지만, 스택오버플로우가 발생할 수 있기 때문에 잘 구현해야 한다 (노드 방문시 방문여부를 검사하면서 진행해야 무한반복에 빠지지 않을 수 있다). 장점 한 분기의 깊이가 깊더라도 완벽하게 탐색하고 다음 분기로 넘어가기 때문에 목표노드가 깊은 .. [문제풀이] 백준 4673번 셀프 넘버 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net org_numbers = set(range(1, 10001)) gen_numbers = set() for number in org_numbers: keep = number while number > 0: keep += int(number % 10) number = int(number / 10) gen_numbers.add(keep) self_numbers = sorted(org_numbers-gen_numbers.. [알고리즘] 완전탐색 (Exhaustive Search) Exhaustive Search 완전탐색은 무식하게 문제를 풀어나가는 방식이라고 하는데, 필자 생각에는 무식하다는 표현은 어울리지 않는 것 같다. 대부분의 알고리즘 문제는 완전탐색으로 다 풀수 있을 정도로 강력한 방식이다. 물론 그래서 무식하다고 부를 수 있지만 사실 컴퓨팅 성능이 미친듯이 좋으면 어떤알고리즘을 쓰더라도 빠르게 결과를 볼 수 있다. 그래서 무식한 방법이라고 절대 무시하면 안된다. 완전탐색을 문제를 해결하기 위한 모든 경우의 수를 나열하고, 정답을 찾아가는 방법을 의미한다. 완전탐색에는 Brute-Force, Bitmask, Recursive Fuction, Permutation, BFS, DFS 알고리즘이 있다. 완전탐색은 탐색의 방법론을 의미하고 그 안에 다양한 알고리즘들이 있다. Br.. [문제풀이] 백준 14713번 앵무새 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 7차 시도 n = int(input()) lines = [] for i in range(n): lines.append(list(map(str, input().split()))) target = list(map(str, input().split())) for item in target: correct = False for idx in range(n): if len(lines[idx]) != 0: if item == lines[idx][0]: lines[i.. [문제풀이] 백준 13335번 트럭 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 1차 시도 total_count = 0 n, w, L = map(int, input().split()) trucks = list(map(int, input().split())) bridge = [0] * w while True: bridge.pop(0) total_count += 1 if len(trucks) > 0: if sum(bridge) + trucks[0] [문제풀이] 백준 2161번 카드01 1차 시도 import queue q = queue.Queue() trash = [] n = int(input()) for data in range(1, n+1): q.put(data) while q.qsize() != 1: # step-1 trash.append(q.get()) # step-2 q.put(q.get()) trash.append(q.get()) for t in trash: print(t, end=' ') 어려운 문제는 아니었다. Queue에서 enqueue와 dequeue를 잘 이해하고 FIFO를 잘 파악하고 있다면 어렵지 않게 풀수 있는 문제이다. [문제풀이] Stack - 균형잡힌 세상 1차 시도 while True: input_data = input() if input_data == '.': break input_data = input_data.replace(' ', "") stack = [] for character in input_data: if character == '(' or character == '[': stack.append(character) elif character == ')': if len(stack) != 0: last = stack.pop() if last != '(': print("no") stack = None break else: print("no") stack = None break elif character == ']': if len(stack) !=.. [문제풀이] Stack - 괄호 1차 시도 n = int(input()) for idx in range(n): line = input() stack = [] for character in line: if character == '(': stack.append(character) elif character == ')': if len(stack) != 0: stack.pop() else: print("NO") stack = None break if stack is not None: if len(stack) == 0: print("YES") else: print("NO") 어렵지 않은 문제였다. 이전 1 2 3 4 다음
