병아리 개발자의 실력 양성기

문제 1. 어떤 수 N (=upperbound) 보다 작은 소수 목록(prime numbers)을 구하라. 소수는 1과 자기 자신만을 약수로 갖는 수이다. 그러므로 무언가의 2배, 3배, 4배 등이 되는 수라면 이는 소수가 아니다. N=60이라고 하면, 그보다 작은 소수들은 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59] 가 있을 것이다. 이를 구하는 가장 효율적인 방법은 기원전에 발견되었다(에라토스테네스의 체, Sieve of Eratosthenes). 이 방법은 우선 모든 수를 소수라고 추정한 뒤, 어떤 소수의 배수처럼 소수가 아닌 수를 지워나가는 것이다. 먼저 0, 1은 소수가 아니라고 정의한다. 최초의 소수인 2를..

양의 정수 n과 k가 주어진다. 정수 n의 약수는 n % i == 0을 만족하는 정수 i로 정의된다. n의 모든 약수를 오름차순으로 정렬한 목록을 고려하여, 이 목록에서 k번째 약수를 반환하거나 n의 약수가 k개 미만인 경우 -1을 반환하세요. 이 문제를 O(n) 복잡도보다 적게 해결하도록 해봅시다 (제한 조건: 1

내가 가장 좋아하는 취미가 뭐냐 묻는다면 알고리즘 문제를 코딩으로 푸는 것이라 말하겠다. 이전에는 제2외국어를 배우거나 스위치를 사서 슈퍼마리오를 아주 재미있게 즐겨왔지만, 외국어는 이를 대신해 줄 도구들이 많아져 공부에 대한 ROI (return on investment) 가 작아지고 있고 게임은 이제 대체로 재미가 없다. 프로그래밍을 하다 보니 결국 그 게임 속 세계라는 것도 사람이 설정해 놓은 조건을 달성하면서 포인트나 스테이지라는 결과값을 얻게 되는 것에 다름아니라는 생각이 들어 몰입이 잘 되지 않았기 때문이다. 그러나 더 큰 이유는 알고리즘 문제를 푸는 과정과 풀었을 때의 성취감이 게임을 할 때 보다 훨씬 크기 때문인 듯 하다. 그래서 나는 알고리즘 문제 풀이도 바둑이나 장기처럼 즐길 수 있는 ..

최소신장트리(MST) 각 간선(edge)의 weight가 1이나 0이 아닌 경우에 모든 노드를 한 트리로 묶은 것(spanning tree)의 weight의 합이 최소가 되는 것을 MST (minimum spanning tree) 라 한다. 이를 구하는 방법은 union find를 쓰는 Kruskal과, Dijkstra의 변형인 Prim이 있는데, 통상 CP에서는 전자를 많이 쓴다고 한다. UnionFind Kruskal을 쓰려면 union find 자료구조를 정의해서 사용해야 한다. 다음 코드는 path compression과 union-by-rank가 모두 적용된 클래스이다. class UnionFind: def __init__(self, N: int) -> None: # N: number of ve..

SCC - Kosaraju Strongly Connected Components (Directed Graph) 는 노드간에 모두 연결된 경우를 말한다. CC와 다른 점은, 방향 그래프에서 dfs를 수행해서 일방향으로 닿을 수 있는 경우로는 요건이 충족되지 못하며, 서로간에 모두 닿을 수 있는 그래프의 부분집합이어야 한다. 그림을 보자 [1]. Kosaraju는 dfs를 두 번 돌려서 SCC를 찾는 알고리즘이다. 아래 그림에서 먼저 dfs 이용해서 Topological Sort를 수행한 결과 S = {0, 1, 3, 4, 5, 7, 6, 2} 가 된다. 이 결과의 의미는, 각 vertex를 방문시 종결 순서의 역순으로 이를 나열한 것이다. 두 번째 dfs에서는 그 결과 S의 원소를 앞에서부터 차례로 짚어가..

한 점(node 1)에서 시작하여 연결된 노드를 방문할 때 방문이 되지 않는 점을 찾는 것을 하고자 한다. 문제는 다음에서 가져왔다. https://open.kattis.com/problems/wheresmyinternet Where's My Internet?? – Kattis, Kattis Photo by Jerry John from Flickr A new town is being built far out in the country, and currently there are $N$ houses. People have already started moving in. However, some of the houses aren’t connected to the internet yet, and natural..

그래프 이론은 방대하다. 기본적으로 방문, 최단거리, DAG, 사이클, MST가 있고, 고급 알고리즘으로는 SCC, 경로, flow 등이 있다. 트리도 그래프의 일종이나 그 특성상 더 적합한 알고리즘이 있기도 하므로 별도로 다루게 된다. 이번 시간에 다룰 문제는 다음과 같다. Connected Components Topological Sort Bipartite or Cycle Check Shortest Path (BFS) Graph traversal 문제 중에서 더 어려운 Strongly Connected Components, Articulation Points/Bridges, Flood Fill은 몇 차례에 나누어 다루기로 하겠으며, MST, SSSP, APSP, Special Graph (최단/장 거..

서로 다른 동전으로 목표합을 구하는 방법의 수를 구하는 문제이다. 다만, 하나는 같은 동전 조합이면 순서가 달라고 1가지로 치고(조합), 나머지는 순열을 구하는 문제이다. 조합문제 https://leetcode.com/problems/coin-change-2/ Coin Change 2 - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 순열문제 https://leetcode.com/problems/combination-sum-iv/ Combination Sum I..

Linked List (singly) 도, Tree도 모두 DAG인 그래프의 일종이라 할 수 있다. 그래프의 사이클을 찾는 방법은 크게 방문된 노드를 기록해 두었다가 (O(n) space), 방문하려는 노드가 이미 방문한 적이 있다면 cycle 이 있다고 보고하는 방법과, Floyd가 제시한 two pointer를 사용하는 방법이 있다 (O(1) space). 이전에 전자에 대해 다루었으므로 오늘은 후자를 다뤄본다. 아무래도 공간을 사용한 전자가 더 속도가 빠르기는 하다. 사이클 여부 토끼는 2걸음씩, 거북이는 1걸음씩 걷는다. 사이클이 존재한다면 둘이 만날 것이고 그렇지 않다면 토끼가 먼저 종점에 도달할 것이다. # Definition for singly-linked list. # class ListN..

23:59, 00:00 의 분 단위 차이는 1분이다. 이런 시간들이 여러개 있을 때 그 최소 차이를 구하는 문제이다. https://leetcode.com/problems/minimum-time-difference/ Minimum Time Difference - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 시계 바늘처럼 일정 값에 도달하면 다시 원점으로 돌아가는 자료는 circular array로 모델링 할 수 있다. 아래 코드를 직접 보자. # https:/..