programming study/항해99 커리큘럼 (82) 썸네일형 리스트형 [항해99 1기] [Chapter2-2] 자료구조, 알고리즘 (14) (2021.3.16) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 2667 문제 링크 # 큐 자료형 사용하기위해 deque import from collections import deque # 지도의 크기 N = int(input()) # 지도 정보 입력 받기 M = [list(input()) for _ in range(N)] # 지도의 정보 정수형으로 변환 for i in range(N): M[i] = list(map(int, M[i])) # 방향 # 상, 하 dx = [-1, 0, 1, 0] # 좌, 우 dy = [0, -1, 0, 1] # 집 수를 카운트할 리스트 선언 cnt_list = [] # 카운트를 저장할 변수 선언 cnt = 0 # 깊이 우선 탐색으로 지도의 단지를 탐색 # M:.. [항해99 1기] [Chapter2-2] 자료구조, 알고리즘 (13) (2021.3.15) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 1260 문제 링크 # BFS를 사용하기위해 deque 가져오기 from collections import deque # N: 정점의 개수 , M: 간선의 개수, V: 탐색을 시작할 정점의 번호 N, M, V = map(int, input().split()) # 간선의 개수만큼 입력 받기 # 인접 리스트를 받을 리스트 선언 G = [[] for _ in range(N + 1)] # 입력받은 정보를 인접 리스트로 변환하기 for _ in range(M): a, b = map(int, input().split()) G[a].append(b) G[b].append(a) # 이차원 리스트의 각 리스트를 오름차순 정렬 for x in G.. [항해99 1기] [Chapter2-2] 자료구조, 알고리즘 (12) (2021.3.14) 01. 분할 정복 Divide and conquer 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 원래 문제의 해를 구하는 방식 아래와 같은 절차를 거친다 Divide 2개 이상의 작은 문제들로 쪼갠다. Conquer 나누어진 작은 문제들을 푼다. Combine 나누어 해결한 문제들을 합친다. 02. 백트래킹 Backtracking 해답을 찾는 과정에서 해답이 될 가능성이 있는지를 확인한다. 해답이 될 가능성이 적으면 부모 노드로 돌아온다. 특정한 조건을 만족하는 경우만 살펴 본다. 단순 깊이 우선 탐색보다 효율이 증가 깊이 우선 탐색은 가능한 모든 경로를 탐색 [항해99 1기] [Chapter2-2] 자료구조, 알고리즘 (11) (2021.3.13) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 9184 문제 링크 def w(a, b, c): # 메모에 전달받은 인자값들이 키로 있으면 그 값을 리턴 if (a, b, c) in memo.keys(): # memo 딕셔너리의 (a, b, c) 값 리턴 return memo[(a, b, c)] # 문제에서 제시된 조건을 이용하여 메모이제이션 if a 20: # 메모이제이션 memo[(20, 20, 20)] = w(20, 20, 20) return memo[(20, 20, 20)] elif a < b < c: # 메모이제이션 memo[(a, b, c)] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c) return memo[(a.. [항해99 1기] [Chapter2-2] 자료구조, 알고리즘 (10) (2021.3.12) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 10815 문제 링크 # 상근이의 숫자 카드의 개수 N = int(input()) # 숫자 카드에 적혀있는 정수 cards = list(map(int, input().split())) # 정렬 cards.sort() # 구분할 카드 수 M = int(input()) # 숫자 카드인지 구분할 정수 nums = list(map(int, input().split())) # 이분탐색 for x in nums: # 카드를 소유한 경우 check = True # 시작점 start = 0 # 끝점 end = N - 1 # 중간점 mid = (start + end) // 2 while start cards[mid]: start = mid + .. [항해99 1기] [Chapter2-1] 자료구조, 알고리즘 (9) (2021.3.11) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 2606 문제 링크 # 컴퓨터의 수 n = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 c = int(input()) # 감염 여부 체크 infested = [] # 인접한 컴퓨터 딕셔너리 computer = {} for i in range(1, n + 1): computer[i] = [] # 입력 받기 for _ in range(c): # a: 감염된 컴퓨터 b: 인접 컴퓨터 a, b = map(int, input().split()) computer[a].append(b) computer[b].append(a) # DFS 선언 def DFS(computer, cur_com, infested):.. [항해99 1기] [Chapter2-1] 자료구조, 알고리즘 (8) (2021.3.11) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 1. 트리 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조 비선형구조: 표현에 초점을 맞춘 자료구조 cf) 선형구조: 자료를 저장하고 꺼내느 것에 초점이 맞춰져 있다. 1.1 용어 정리 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node: Child Node가 하나도 없는 노드 Sibling: 동일한 Parent Node를 가진 노드 Depth: 트리에서 Node가 가질 수 있.. [항해99 1기] [Chapter2-1] 자료구조, 알고리즘 (7) (2021.3.10) Baekjoon Online Judge 백준 온라인 저지 사이트의 문제 풀이 4949 문제 링크 while True: string = input() if string == ".": break # 먼저 들어온 괄호가 먼저 나가게 되므로 스택 자료구조형을 사용한다 stack = [] # 괄호 탐색 for x in string: # 여는 괄호 발견시 스택에 쌓아두기 if x == "(" or x == "[": stack.append(x) # 스택의 마지막 원소의 괄호와 문자열의 괄호가 짝이 맞는지 검사 elif x == ")": if not stack or stack[-1] == "[": print("no") break elif stack[-1] == "(": stack.pop() elif x == "]": .. 이전 1 ··· 6 7 8 9 10 11 다음 목록 더보기