https://school.programmers.co.kr/learn/courses/30/lessons/87377 문제 풀어보기 문제 풀이의 흐름 직선이 주어지면 주어진 직선에서 교점을 구한다 그중 정수 교점만 따로 변수로 저장 교점을 모두 표현할 수 있는 최소한의 사각형을 알아낸다 모든 교점은 *을 찍어서 표현한다. 배열을 거꾸로 뒤집어 반환한다. 직선의 개수가 10의 3승밖에 안되기 때문에 반복문을 중첩으로 사용해도 괜찮다 풀이 1. 주어진 직선에서 교점을 구한다 식 두개를 만들어서 교점을 구해야한다. for i in range(n): a, b, e = line[i] for j in range(i + 1, n): c, d, f = line[j] if a * d == b * c: # 평행이라면 교점이 ..
coding test
그래프 순회 그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기한다. 그래프 순회에는 크게 깊이 우선 탐색과 너비 우선 탐색의 두가지 알고리즘이 있다. BFS graph = { 'A': ['B', 'D', 'E'], 'B': ['A', 'C', 'D'], 'C': ['B'], 'D': ['A', 'B'], 'E': ['A'] } 너비 우선 탐색을 그래프를 가까운데 부터 탐색한다는 것이다. 탐색 순서 a → b→ d → e → c 너비 우선 탐색을 구현한 코드 from collections import deque # start_v : 시작노드 def bfs(graph, start_v): visited = [start_v] # 사전세팅 : 가장 처음에 있는 노드를 큐에 집어넣..
그래프 정의 💡 그래프는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프 종류 방향 그래프 vs 무향 그래프(코테에 많이 등장한다) 다중 그래프 vs 단순 그래프 가중치 그래프 ⇒ 다익스트라 그래프 활용 그래프 문제는 정말 많이 나온다 현실 세계의 사물이나 추상적인 개념간의 연결 관계를 표현한다. 도시들을 연결하는 도로망 지하철 연결 노선도 컴퓨터 네트워크 소셜 네트워크 분석 그래프 표현 방법 그래프 라는 것은 vertex 와 edge가 연결 됐는지 안됐는지가 중요하다 구현 방법 인접 리스트 인접 행렬 암시적 그래프 인접 행렬 graph = [ [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], [1, 0, 0,..
문제 해석 깊이의 정의 문제에서 깊이라는 것은 root 노드에서 얼마나 많이 떨어져 있나를 이야기한다 예제 예제 1 root 노드 3 1 ⇒ 깊이 : 2 예제 2 root 노드 3 5, 1 0, 8 ⇒ 깊이 : 3 예제 3 노드가 하나도 없을 땐? : 깊이 0 노드가 root 노드만 있을 땐? : 깊이 1 트리가 한쪽으로만 쭉 나열되어 있을 땐? : 레벨을 확인하면 되는 문제라서 상관없다. 접근 트리를 순회해야한다. BFS를 사용한다 : 한 레벨에 있는 노드들을 모두 순회 해야한다. # 큐 선언 q = queue(); # 큐에 뭔가 있다는건 접근할 노드가 있다는 것. 큐에 뭔가 있다면 계속 반복해야함 while q: cur_node = q.popleft(); # 큐에 있는 노드(접근 예정 노드)를 방문함..
LeetCode - The World's Leading Online Programming Learning Platform 문제 해석 중요한 점은 자기 자신을 포함한 것을 조상이라고 생각하는 것 case1 주어진 노드 : 5, 4 주어진 노드의 조상 : 3 공통 노드 : 3 가장 낮은 공통 노드 : 3 case2 주어진 노드 : 5, 4 주어진 노드의 조상 : 4, 2, 5, 3 공통 노드 : 3, 5 가장 낮은 공통 노드 : 5 case3 주어진 노드 : 6, 4 주어진 노드의 조상 : 4, 2, 6, 5, 3 공통 노드 : 5, 3 가장 낮은 공통 노드 : 5 구현 PostOrder 방식 문제 구현은 이 그림을 기준으로 한다. 여기서 q가 오타인데 7이 아니라 4이다 포인트는 주어진 노드에서 거슬러 올..
DFS(깊이 우선 탐색) by recursion 접근 방식 a → b → c → d → b → a → e → f → g → e → e 의 순서로 접근을 한다 깊이를 우선적으로 탐색하기 때문에 세로 방향을 먼저 탐색하고 만약에 형제 노드를 방문하고 싶다면 부모노드로 다시 올라와서 형제 노드로 접근해야한다 접근하는 코드 def traversal(root): if root is None: return traversal(root.left) traversal(root.right) 루트만 있으면 루트가 가리키는 트리에 속한 모든 노드를 접근한다 종류 전위순회(preorder) 중위순회(inorder) 후위순회(postorder) 접근 방식은 위와 같다! 순서만 달라질뿐! 전위순회 전위순회의 순서는 A → B → A..
트리순회 트리순회란? 💡 트리탐색이라고도 불리우며 트리의 각 노드를 방문하는 과정을 말한다. 모든 노들를 한 번씩 방문 해야 하므로 완전 탐색이라고도 불린다. 순회 방법으로는 너비 우선 탐색의 BFS와 깊이 우선 탐색의 DFS가 있다. BFS(너비 우선 탐색) 탐색 순서 루트노드로 부터 가까운 노드들 다 탐색하고 다음 그 아래 레벨의 노드들 탐색하는 말그대로 길이를 탐색하는 것. 위의 그림에서 볼때 2, 3번 노드를 먼저 탐색 후 4번 5번 6번 노드를 탐색한다 아래의 코드는 아주 기본적인 템플릿으로 안보고 짤 줄 알아야한다!! from collections import deque def levelOrder(root): visited = [] if root is None: return 0 q = dequ..
Tree 💡 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성됨 트리 관련 용어 노드 : 구성 요소 간선 (Edge) : 노드간에 연결된 선 루트 노드(Root) : 트리의 시작점 리프 노드(Leaf) : 트리의 마지막 노드 자식 노드(child), 부모 노드(parent), 형제 노드(sibiling) 차수 (degree) : 각 노드 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다 조상 (ancestor) : 위쪽으로 간선을 따라가면 만나는 모든 노드 자손 (descendant) : 아래쪽으로 간선을 따라가면 만나는 모든 노드 높이 (height) : 루트 노드에서 가장 멀리있는 리프 노드 까지의 거리, 즉 리프 노드중에 최대 ..
