늦깎이 IT

[ LCS란? ] LCS란 Longest Common Subsequence의 약자로 최장 공통 부문 문자열이다. 여기서 Subsequence란 연속적이지 않은 부분 문자열이다. 다음과 같은 문자열 A와 B가 있다고 하자. A = { ABCBDAB } // B = { BCDB }이때 문자열 B는 문자열 A의 Subsequence이다. 위처럼 연속적이지는 않지만, 순서는 맞는 문자열을 Subsequence라고 한다. LCS는 두 개의 문자열이 주어졌을 때, Common Subsequence들 중 가장 긴 문자열을 뜻한다. [ 생각해보기 ] 아래 그림과 같이 문자열 A와 B가 있다고 가정하자.LCS의 마지막 문자가 A라고 한다면, 문자열 X와 Y 어딘가에도 문자열 A를 포함하고 있을 것이다. 그렇다면, 아래 ..

[백준 16985번] URL Maaaaaaaaaze URL [전체 소스코드 GitHub에서 확인하기] 1. 두 가지경우에 대한 완전탐색을 실행해야 한다. 2. 우선, 각각의 판의 순서(?)를 정하는 모든 경우의 수를 구해야한다.A,B,C,D,E 라는 5 x 5 크기의 판이 5개 있을 때, 이 판들을 바닥에서부터 쌓는 순서를 정해야한다. 3. 각각의 판을 쌓아올리는 경우에 대해서 1층부터 5층까지 자리잡은 판들을 각각 0회~3회씩 돌린 후 최단거리를 찾는다. [시계방향으로 돌리는 메소드] - prev[][][] 3차원 배열이 있을 때, prev[target][][]의 값들을 시계방향으로 한번 회전시키는 메소드이다. 123456789101112public static void rotate(int[][][] ..

[백준 1976번] 여행가자 URL 1. 전형적인 Union-Find 문제입니다.2. 각 여행지들의 부모노드를 저장하고, 모든 노드들의 부모노드가 같다면 어느 노드부터 시작하더라도 모든 노드들을 방문할 수 있기 때문에 YES, 하나의 노드라도 부모노드가 다르다면 NO를 출력합니다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.io.BufferedReader;import java.io.IOExceptio..

[백준 1717번] 집합의 표현 URL 기본적인 Union-Find 문제이므로 이전 포스팅 글을 참고하시기 바랍니다.2019/03/25 - [알고리즘 이론] - [알고리즘] 유니온 파인드 (Union-Find) :: 늦깎이 IT [소스 코드] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayL..

[백준 2146번] 다리 만들기 URL 1. 각 섬마다 번호를 매긴다 (2, 3, 4, ....) 2. 그리고 모든 섬들을 큐에 넣어주고 BFS를 돌린다. BFS를 돌릴 때 다음 칸이 0이라는 뜻은 바다라는 뜻이므로해당 섬의 번호로 땅을 확장한다. 3. 다음 칸이 0도 아니고, 현재 위치의 땅 번호와도 다르다면, 다른 땅이 그곳까지 확장됐다는 뜻이므로 거리를 계산한다. 4. 거리를 계산하는 방법은 dist라는 2차원 배열을 따로 만들고 BFS 탐색을 할 때 땅이 한 칸 확장되었다면 거리또한 1씩 증가시키는 것이다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354..

[백준 2573번] 빙산 URL 1. 빙산을 녹일 때 주의할 점이 있다. 왼쪽위부터 오른쪽아래까지 map을 탐색하면서 빙산을 녹일 때, 임의의 한 빙산을 녹일 때, 인접한 부분에 바다(0)가 있다고해서 무조건 녹이면 안되고, 바다로 된 자리가 현재 시점에 바다가 된건지 이전 시점에 바다가 된건지 확인해야한다. 2. melt() 메소드를 보면, 같은 시간내에 바다가된 경우 curMelt라는 boolean 배열에 체크를 해준다. 3. 빙산을 한 회 녹였다면, BFS탐색을 시작해서 빙산이 두 덩어리 이상이 되는지 확인한다. 4. BFS 탐색 후에, 빙산이 두 덩어리가 안되었다면 map을 전체탐색하며 빙산이 모두 녹았는지 확인한다.빙산이 모두 녹아버렸다면 0을 출력한다. [소스 코드] 12345678910111..

[백준 2468번] 안전 영역 URL 1. 비가 내리지 않을 경우, 안전지대는 1로 초기화한다. 2. 비는 안전지대의 최대 높이만큼만 내리면 된다. 최대 높이보다 비가 더 많이 내릴 경우는 어차피 안전지대는 0이되기 때문이다. 3. 비를 1씩 내릴때마다 Map의 값을 -1 해주며, BFS탐색을 하고 최대 값을 찾는다. [소스 코드] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061..

[백준 9466번] 텀 프로젝트 URL 1. 사이클에 들어가지 못한 노드들의 갯수를 묻는 문제이다. 2. 우선 1번부터 N번까지의 노드들을 순차적으로 탐색한다. 3. 어느 노드부터 시작해서 방문하지 않았거나 그룹에 속하지 않았을 경우 계속해서 탐색을 진행한다. 4. 이미 방문했거나 그룹에 들어간 노드를 만나면 탐색을 멈추고, 그 노드의 번호를 기억한다. 5. 아래와 같은 입력이 주어졌을 때를 생각해보자.1부터 탐색을 시작해서, 3에서 탐색을 끝낸다. 탐색을 하며 각 노드들을 list에 저장한다.3에서 탐색이 끝나면 cur 에는 3이 저장되어 있다.list를 돌면서 처음 시작점과 끝나는 점을 비교한다.시작점 == 끝점(cur)을 찾았으면 그때의 list 인덱스를 저장하고 break문으로 for문을 빠져나온..