2023년 9월 4일 알고리즘 문제풀이 문제 1 백준 1167 문제 링크 1차 시도 나의 생각 입력값을 list로 받은 후 가장 앞인 0번 index는 어떤 정점의 정보인지를 나타낸다고 생각하였고 그 이후 둘 씩 짝지어서 도착 정점과 거리로 설정하였다. 이를 바탕으로 인접리스트를 만들고 index를 2씩 뛰어넘어 -1이 나오면 더이상 정보가 없으므로 다음 줄로 넘어갔다. 이후에는 두 점간의 거리를 bfs를 통해 탐색하도록 하였다. 모든 점간의 거리를 찾아 최댓값을 도출하였다. 하지만 메모리,시간초과가 뜬다… 다찾아보면 안되나보다. ...
2023년 8월 9일 알고리즘 문제풀이 문제 1 백준 11725 문제 링크 1차 시도 나의 생각 연결된 두 점 중 누구를 부모로 할 것인가에 대해 많이 고민했다. 확실한 것은, 1번과 연결된 노드들의 부모는 모두 1번 노드일 것이라는 것이다. 그래서 모두 1번노드 쪽으로 향하니 번호가 작은 노드가 부모인 것으로 설정해야하나 고민했다. 물론 나도 지금 생각해보면 뭔 말도 안되는 소리인지 모르겠다. 결국 어떤 방법으로 풀어야 할지 감을 못잡았다 결과 오답 코드 X 2차 시도 나의 생각 지금 내가 공부하고 있는 단원이 DFS인 것을 떠올리니 쉽게 해결됐다. 실제 코딩 테스트에선 단원을 모로는 채로 풀어야 하기 때문에 문제만 보고 알아차려야 하는데.. 걱정이다 ...
2023년 8월 3일 알고리즘 문제풀이 백준 1991 문제 링크 1차 시도 나의 생각 왼쪽 자식이 존재하면 재귀를 통해 들어가고, 없을 때 오른쪽 자식도 확인하는 과정을 거쳤다. 정답을 위한 배열에 왼쪽 자식과 부모, 오른쪽 자식을 어느 타이밍에 추가해야할 지 헷갈렸고 이로 인해 코드를 완성하지 못했다. 결과 오답 코드 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 48 49 50 51 52 53 54 55 56 import sys arr = [] n = int(sys.stdin.readline()) for _ in range(n): p, l, r = sys.stdin.readline().rstrip().split() arr.append([p, l, r]) front = ['A'] mid = [] back = [] def search_front(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': ans.append(x[1]) search_front(x, arr, ans) if x[2] != '.': ans.append(x[2]) search_front(x, arr, ans) def search_mid(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_mid(x, arr, ans) else: ans.append(x[0]) if x[2] != '.': search_mid(x, arr, ans) break def search_back(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_back(x, arr, ans) else: ans.append(node) if x[2] != '.': search_back(x, arr, ans) ans.append(x) ans.append(node[0]) search_front(arr[0], arr, front) search_mid(arr[0], arr, mid) search_back(arr[0], arr, back) print(front) print(mid) print(back) 2차 시도 나의 생각 정답을 위한 배열에는 항상 부모만 넣는다는 기준을 세웠다. 또 왼쪽자식과 오른쪽 자식의 탐색을 if-else 조건문을 사용하였는데 별개로 하였다. 즉 왼쪽 자식을 먼저 탐색해 존재하면 재귀를 통해 최대한 깊숙히 들어간 후 더이상 왼쪽자식이 존재하지 않을 때 그 때의 부모노드를 배열에 추가하면 전체 트리에서 가장 왼쪽에 있는 노드를 배열에 추가한 것으로 구현된다는 것을 깨달았다. 순회의 방식에 따라 왼쪽 자식 탐색, 부모노드 삽입, 오른쪽 자식 탐색의 순서만 변경해주었다. ...
Red-Black Tree 개념 레드-블랙 트리. 이진 검색 트리의 한 종류이다. 그렇다면 트리는 뭔지, 이진 검색트리는 또 뭔지, 레드-블랙 트리는 어떤 특별한점이 있는지부터 알아보겠다. 자료구조(data structure) 개발자 공부를 하면서 수도 없이 들어봤을 자료구조. 지금 자료구조가 뭐냐고 묻는다면 나는 “list, set, deque, queue, stack 같은 것들처럼 데이터들이 어떤 형태와 관계로 들어있는지를 나타내는 것입니다.“라고 대답할 것 같다. 면접이라 생각하고 머릿속에 떠오르는걸 그대로 받아적었는데 생각보다 나쁘지 않은데? 그럼 정확한 정의부터 살펴보자. INTRODUCTION TO ALGORITHMS THIRD EDITION 책에는 ...