늦깎이 IT

[알고스팟] 고대어사전 URL 1. 입력으로 주어지는 단어의 순서가 사전 순서로 배치되어 있다. 2. 각 단어들마다 비교를 통해 각 문자들간의 우선순위를 비교해주는 연산이 필요하다. 3. 예를 들어, acb와 abb가 입력되었을 경우 맨 앞자리 알파벳은 같으므로 패스하고 두 번째 자리인 c가 b보다우선한다는 것을 표시해야한다. 4. 각 단어들간의 우선순위는 26 X 26 인접행렬로 표현해도되고 연결리스트로 표현해도된다. 5. a~z 까지의 알파벳을 순차적으로 탐색하되 연결되어 있는 알파벳이 있다면 다시 그 알파벳부터 DFS탐색을시작한다. 6. 순서가 정해져있는 경우이므로, 위상정렬을 한다고 생각하면 된다. 1234567891011121314151617181920212223242526272829303132..

[알고스팟] 울타리 잘라내기 URL 1. 울타리의 최대 넓이를 찾는 방법은 아래와 같다. 1) 울타리를 N/2등분 하여, 왼쪽 울타리에서 최대 넓이를 찾는다.2) 울타리를 N/2등분 하여, 오른쪽 울타리에서 최대 넓이를 찾는다.3) 울타리의 N/2등분한 위치를 기점으로 왼쪽과 오른쪽을 탐색하며 최대 넓이를 찾는다. 반드시 N/2 위치가 포함되어야 한다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import java.io.BufferedReader;import java.io.IOException;import java.io.InputStr..

[알고스팟] 쿼드 트리 뒤집기 URL 1. 분할정복을 사용한다. 2. 예를 들어, N x N칸이 모두 흰색 혹은 검은색으로 칠해져 있는 경우 뒤집어도 똑같은 색이다. 3. 이 아이디어에서부터 1x1 칸에는 한 가지 색만 칠해져 있으므로, 뒤집어도 똑같기 때문에 기저조건을1x1칸으로 정한다. 4. 입력으로부터 input 문자열을 받고, 이 문자열의 인덱스를 가리키는 pointer를 선언한다. 5. recursive() 메소드를 호출하면, input 문자열의 처음부터 확인한다. input 문자열의 첫글자가 w 혹은 b라면N x N칸 모두 하나의 색으로 칠해져있다는 뜻이므로, input 그대로 정답을 출력한다. 6. input 문자열의 첫 글자가 x라면 이것을 4등분으로 나누어야 한다. 4등분으로 나누는 기준..

[알고스팟 TSP1 URL] 1. 이 문제는 완전탐색으로 풀었습니다. N개의 도시가 있을 때, 출발 도시를 제외한 나머지 도시들을 방문하는경우의 수는 (N-1)!입니다. 문제에서 N의 입력이 8이하이므로 완전탐색으로 풀어도 시간초과가 나지 않습니다. 2. 시작 도시를 정한 후, 그 도시로부터 순회를 시작합니다. 모든 도시를 돌았다면 최소 값을 갱신해줍니다. [소스 코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import java.io.BufferedReader;i..

[알고스팟 게임판 덮기 링크] 1. L자 모양의 블럭으로 게임판을 덮는 경우의 수를 구하는 문제인데, 이는 L자 모양의 블럭으로 게임판을덮는 순서와는 상관이 없다. 즉, 순서가 어떻게 되든지간에 게임판을 덮는 모양이 같다면 하나의 경우로 취급한다. 2. 맨 위쪽, 맨 왼쪽부터 게임판이 덮이지 않은 위치를 찾는다. 그리고 그 위치에서 부터 L자 모양의 블럭을 놓는다. - 여기서, 이전의 칸들은 이미 블럭이 덮여있다고 가정해야한다. 즉, L자 모양의 블럭을 해당 위치에 놓을 때,아래쪽 혹은 오른쪽으로만 뻗어나가게 해야한다. - 소스 코드에서, coverDir[][][] 배열을 참고하기 바란다. 3. 해당 위치에서, L자 모양의 블럭을 둘 수 있는지 없는지를 따로 확인하지 않는다. Map의 범위를 벗어나지 않..

[알고스팟 소풍 URL] 완전 탐색 문제입니다. 1. 아직 짝을 이루지 못한 기준 학생을 찾는다. 학생을 찾을 때에는 맨 앞쪽의 학생부터 찾는다. - (0, 1) 학생과 (1, 0) 학생이 짝을 이루는 경우는 같은 상황이기 때문에, 중복을 피해야 한다. 2. 짝을 이루지 못한 기준이 되는 학생을 찾았으면, 그 학생과 짝을 이룰 다른 학생을 찾는다.3. 두 명의 학생이 짝을 이뤘으면, count(짝을 이룬 학생 수)를 2 증가시켜 다시 DFS 탐색을 시작한다. [소스코드] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667import ..

[알고스팟 RUNNINGMEDIAN URL] [참고할만한 알고리즘 이론]2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬 이 문제를 풀기 위해서 다음과 같은 조건을 수립합니다.1) 입력받는 데이터들을 두 개의 힙으로 나누되 하나는 최소힙, 나머지 하나는 최대힙으로 구성한다.2) 최대힙의 크기는 최소힙과 같거나 1만큼 크다.3) 최대힙의 루트는 최소힙의 루트보다 작거나 같다. 예를 들어, 3, 1, 5, 4, 2의 순서로 데이터가 입력된다고 가정합니다. 1. 데이터 3이 입력되었을 때1) maxHeap과 minHeap 크기가 같으므로 maxHeap에 저장합니다. 2. 데이터 1이 입력되었을 때1) maxHeap의 크기와 minHeap..