백준 14719. 빗물https://www.acmicpc.net/problem/14719일반적인 구현 문제였다. 2차원 세계의 벽의 높이가 주어졌을때, 그 사이에 고일수있는 빗물의 양을 구한다, 나는 2차원 배열로 벽을 그린 후, 0행부터 N-1행까지 행을 기준으로 돌면서 채울수있는 가로표면을 누적해가면서 풀었다.하지만 어떤 아이디어를 통해 더 빠르게 구현하는 방법이 있는것을 깨달았다!그래서 두가지 방법으로 풀어보았다. 1번이 내 첫 풀이, 2번이 더 효율적인 풀이이다. 풀이 11. map[][]에 벽을 저장한다2. 행별로 탐색하면서 양옆이 막혔을때(즉, block이 2일때) 그 사이의 거리를 구해 저장한다. 즉, 위 그림에서 block이 두개일때인 index=3에서 이전 벽이 있던 index=0을 뺀 ..

유니온앤파인드(Union And Find)그래프/트리에서 쓰는 대표적인 알고리즘으로, 서로소인 부분집합을 표현한다.즉, 여러 노드가 있을때 두 노드가 같은 그래프에 있는가?를 판단할 수 있는 알고리즘이다.union(합치는)연산과 find(어느 집합에 속하는지)연산으로 이루어져있다. 알고리즘 구현 방법1. parent[] 배열을 만들고, 각 인덱스에 인덱스값을 넣는다(parent[i] = i, 모든 노드가 자기자신을 부모로 가리킨다)2. union(a,b)의 경우, a와 b를 합치는 작업을 한다. parent[2]=1이 됨으로써 집합을 표현할 수 있다(더 작은값 쪽으로 합친다)3. 그러나 이렇게했을경우, 1-2-3이 연결되었을때 parent[1]=1, parent[2]=2, parent[3]=2가 되기 ..

투포인터(Two-Pointer)두개의 포인터를 활용해 특정 조건을 만족하는 부분구간을 찾는 알고리즘이다.일반적으로는 정렬된 배열에 대해서 수행한다. 반복문 두개를 활용해 탐색하지 않고, 선형 반복문 1개만 사용하므로 O(N)의 시간복잡도를 갖는다. 알고리즘 구현 방법1. 배열의 특정위치에서 두개의 포인터를 셋팅한다(start, end)2. 두 포인터 사이의 구간을 보고 조건을 만족하는지 확인한다.3. 조건을 찾을때 까지 반복한다. cf) 이때 두 포인터 사이의 간격이 일정하게 유지되면 슬라이딩윈도우이다. 백준 2467. 용액https://www.acmicpc.net/problem/2467두 수의 합이 0에 가까운 집합을 구하는 문제이므로, 투포인터 또는 이진탐색을 활용할 수 있다.직관적으로 투포인터로 풀..

위상정렬(Topology Sort)사이클이 없는 방향그래프의 모든 노드를 방향성에 거스르지 않고 순서대로 나열하는것!특정 노드로 들어오는 간선의 갯수를 진입차수, 특정 노드에서 나가는 간선의 갯수를 진출차수라고 가정했을때1 -> 2 -> 3 순서대로 정렬하는것이다. 즉, 진입차수가 없는것부터 시작해서, 진입차수에 속하는 노드가 이미 방문 되면 그 이후의 노드를 선택할 수 있게되는것. 위 그림에서는 1번을 먼저 선택하고, 2번을 선택할수있고(3번은 2번선택전엔 선택불가), 그다음 3번을 선택하는것이다. 알고리즘 구현 방법Queue를 활용해 구현할 수 있다. 간단히 생각해보면, 우선 큐에 진입차수가 0인 노드들을 넣어두고, 하나씩 방문처리 하면서 동시에 해당 노드가 진입차수로 설정된 노드들의 차수를 하나씩..