Jane's PS Blog

LeetCode Merge Two Sorted Lists

Description  Constraints The number of nodes in both lists is in the range 0, 50. -100 <= Node.val <= 100 Both l1 and l2 are sorted in non-decreasing order.  Solution Source https://leetcode.com/pro…

이코테 Chapter 10 그래프 실전 문제 (3)

실전 문제 3: 커리큘럼 Testcase Solution deep copy 관련 설명 링크 각 강의 번호는 1부터 N까지 구성되며 동시에 여러 개의 강의를 들을 수 있다는 조건을 놓치지 말자. time을 저장하는 리스트를 따로 만들 생각을 못했다. 잘 모르겠어서 해설을 보고 다시 풀어봤다. Source https://github.com/ndb796/py…

이코테 Chapter 10 그래프 실전 문제 (2)

실전 문제 2: 도시 분할 계획 Testcase Solution 1차 시도 8이 나와야하는데 6이 나온다. 원인을 찾았다. 간선 중에 가장 큰 값을 빼면 안 되고 최소신장트리에 포함된 간선 중에 제일 큰 값을 빼야 한다. 2차 시도: 성공 모범 풀이 Source https://github.com/ndb796/python-for-coding-test

이코테 Chapter 10 그래프 실전 문제 (1)

실전 문제 1: 팀 결성 Testcase Solution 문제 설명부터 union-find 알고리즘 냄새가 풀풀 난다. 모범 풀이는 아래와 같다. Source https://github.com/ndb796/python-for-coding-test

이코테 Chapter 10 그래프 이론 (3)

위상 정렬(Topology Sort) 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 진입차수: 특정한 노드로 들어오는 간선의 개수 동작 과정 진입차수가 0인 노드를 큐에 넣는다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이된 노드를 큐에 넣는다. 큐가 빌 때까지 2번과 3번을 반…

이코테 Chapter 10 그래프 이론 (2)

신장 트리(Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 → 본래의 그래프의 모든 노드를 포함하면서 → 모든 노드가 서로 연결되어 있고 → 사이클이 존재하지 않아야 한다 (트리의 속성) 트리 자료구조이므로 노드가 N개일 때 간선의 개수는 N-1개이다. 크루스칼 알고리즘 최소 신장 트리 알고리…

이코테 Chapter 10 그래프 이론 (1)

서로소 집합(Disjoint Sets) 공통 원소가 없는 두 집합 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 → 합집합(union)과 찾기(find) 연산으로 조작하기 때문에 union-find 자료구조라고도 부른다. union: 두 개별 집합을 하나의 집합으로 합치는 연산 find: 특정한 원소가 속한…

이코테 Chapter 9 최단 경로 (2)

플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘 다이나믹 프로그래밍 2차원 리스트에 최단 거리 정보를 저장한다. 구현 시간복잡도 : Input Output 실전 문제 1: 미래 도시 Testcase 1 Testcase 2 Solution 플로이드 워셜 알고리즘을 그대로 적용하기만 하면 풀린…

이코테 Chapter 9 최단 경로 (1)

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 → Weighted Graph에서 Edge의 가중치 합이 최소가 되는 경로를 찾는 것이 목적이다. 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리…

이코테 Chapter 8 다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming) 연속적이지 않은 데이터에 대해 메모이제이션 기법을 사용하는 경우 배열이나 리스트가 아닌 사전(dict) 자료형을 이용하는 게 더 효과적이다. 완전 탐색으로 접근했을 때 시간 초과가 뜬다면 다이나믹 프로그래밍으로 해결할 수 있는지 부분 문제들의 중복 여부를 확인해보는 것이 좋다. 재귀함수를 이용한 탑…