분류 전체보기 64

그래프 알고리즘 코드 정리 [3: 최소신장트리(MST)]

최소신장트리(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..

알고리즘/Graph 2022.11.28

Online Judge Runtime Error (RE/RTE) 원인: I/O

로컬 PC에서 돌려보면 테스트 케이스 답도 맞았는데 자꾸 RTE가 뜨는 경우, I/O 문제를 고려해 보자. OJ (Online Judge)는 입출력 형태가 다양해서 이를 잘 대응하는 방법을 알아야 여기서 RTE 해결하느라 많은 시간 안쓰고 본 문제 푸는데 집중해서 실력을 키울 수 있다. 나도 여러 번 삽질(?)을 해서 알아낸 것으로, 입력 유형별로 좋은 I/O를 정리해 보겠다. Python 3 기준이다. input() 쓰지 말자 왜냐고? RTE가 잘 난다. 예를 들어, UVa 352 의 경우 다음과 같은 입력 자료를 다뤄야 한다. 전형적인 EOF 문제이다. 자료를 설명하면, 먼저 n by n 행렬의 n을 나타내는 숫자가 나오고 그 뒤에 행렬의 자료가 문자열로 입력된다. 그 다음 케이스가 같은 형태로 이어..

Soft Talks 2022.11.27

그래프 알고리즘 코드 정리 [2: SCC]

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의 원소를 앞에서부터 차례로 짚어가..

알고리즘/Graph 2022.11.25

면접 전에 꼭 할 일

면접을 잘 본 것 같은데, 대답을 대체로 잘 했다고 생각되는데 탈락하는 경우에는 다음을 하지 않았는지 돌아보면 좋을 것 같다. 회사와 직무에 대한 리서치 회사가 어떻게 좋은지, 해당 직무에서는 무슨 일을 하는지 등에 대해 현직자를 통해 최대한 정보를 수집하는 것을 추천한다. 그렇지 않다면 직무와 회사에 대한 진실성이 드러나지 않아 면접관으로부터 '이 사람은 뽑더라도 오지 않겠구나' 하는 인상을 줄 수 있다. 아무리 가장을 하려고 해도 정말로 그 회사가 좋고 너무 가고 싶은 열의는 자연스레 면접 과정에서 드러나게 마련이다. 면접관은 같은 포지션에 대해 많은 지원자를 보기 때문에, 그 사람의 역량 외에도 그 사람이 얼마나 이 직무에 와서 오래 떠나지 않고 근무할지에 대해서도 알고자 할 것이다. 이를 위해서 ..

Soft Talks 2022.11.19

그래프 연결성 판정

한 점(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..

알고리즘/Graph 2022.11.19

그래프 알고리즘 코드 정리 [1: 기본 탐색(traversal)]

그래프 이론은 방대하다. 기본적으로 방문, 최단거리, 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 (최단/장 거..

알고리즘/Graph 2022.11.13

BFS로 최단경로 찾기 (shortest path by BFS)

BFS (너비 우선 탐색)는 가장 가까운 연결 노드부터 탐색하는 방식으로, 파이썬에서는 collections.deque를 이용해 구현한다. 간선 (edge)의 weight가 모두 1인 경우에 최단경로와 그 경로의 길이를 출력하는 프로그램을 작성해보자. 아주 좋은 문제가 있어 이를 가져왔다. 잠시 생각해보고 아래에 작성한 코드를 보기를 추천한다. https://cses.fi/problemset/task/1667/ CSES - Message Route cses.fi 우리 목적은 "Uolevi's computer is 1 and Maija's computer is n." 라는 문제 정의로부터, 결국 0번 vertex에서 시작해 n-1번 vertex까지 방문 가능한 최단경로를 찾는 것이다. 먼저 각 vertex..

카테고리 없음 2022.11.11

카카오 개발자 영입 합격수기

돌 지난 아기의 육아를 하며 낮에는 직장에서 바쁘고 일이 어려운 부서에서 일하며 학부 전공조차 문과이던 내가 카카오에 개발자로서 경력자 채용에 합격하게 되었다. 지금 회사 및 향후 조인할 조직과의 관계가 있어 관련 직무나 나의 상세한 배경, 수행 프로젝트(포트폴리오) 등 상세한 내용은 입사후에 더 이야기하게 되겠지만, 앞서 말한 것과 같이 저런 열악한 조건에서 소위 네카라 라고 불리는 탑 IT 서비스 회사 중 하나에 합격한 과정을 기억이 생생할때 기록해 두면 다른 분들에게도 도움이 될 것 같다. 포트폴리오 구성과 입사지원 나는 현재 회사에서 업무상 필요성을 느껴 전 직원이 활용하는 어플리케이션을 풀스택으로 제작했다. 다만 구체적으로 어떤 일을 했는지는 재직중인 회사의 정보가 노출될 수 있고 또 나의 신상..

Soft Talks 2022.10.03

Windows 10 에서 C++ 프로그램 컴파일하기

Linux 계열과 달리 Windows 운영체제를 설치해도 C++ 컴파일러가 포함되어 있지 않다. 따라서 이를 추가로 설치하고 경로 지정을 해줘야 한다. 먼저, minGW를 설치한다(https://www.mingw-w64.org/downloads/). minimum GNU for Windows 라는 뜻의 프로그램들로, 이로부터 g++ 를 설치하면 c++ 컴파일이 가능하다. 그다음, minGW가 설치된 경로를 찾아, bin 폴더를 path에 추가하여 어디서든 실행이 가능하도록 한다. setx path "%PATH%;C:\MinGW\bin" 그리고, 소스코드를 작성하여 .cpp 확장자로 저장한 다음, 아래 화면과 같이 명령어를 입력하여 컴파일 함으로써 .exe 파일을 만들고 실행한다. 컴파일시: g++ Pro..

IT in General/C++ 2022.09.25