코딩스토리

www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 실버 5의 구현 문제여서 쉬울 것이라고 생각하고 접근했다가 엄청 애먹었다... 문제를 보면 다들 큰 사각형에서 작은 사각형 빼면 되겠다!라고 생각할 것이다. 근데 어떻게 작은 사각형을 구하지...? 이 고민만 30분 넘게 했다. 다양한 방법이 생각났지만 아무리 봐도 실버5에 쓸만한 구현들이 아니었다. 분명 더 쉬운 풀이법이 있을 것 같은데... 결국 내가 마지막으로 생각해 낸 방법은 4가지 도형으로 나누어서 각..

백준 1043번 - 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 골드 4 치고는 문제가 짧아 보여서 풀었다. 먼저 문제를 이해해보자. 아래는 내가 분석한 문제이다. 1. 진실을 아는 사람이 있는 Party에서는 무조건 거짓말 불가! 2. Party는 (진실을 말함, 거짓을 말함) 두 가지로 나뉜다. 이때 두 가지를 동시에 겪은 사람은 없어야 된다 -> 즉, 어떤 사람이 진실을 들었다면 그 사람이 간 모든 파티에서 진실을 들어야 한다. 3. 만약 진실을 아..

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 23장 우선순위 큐와 힙에 나온 내용을 바탕으로 작성하였습니다. 개요 우리는 기존에 "큐(Queue)"라는 자료구조를 배웠었다. 큐는 스택과 비슷한 자료구조로 '선입선출'이라는 형태를 갖추고 있다. 그렇다면 우선순위 큐와 큐의 차이점은 무엇일까? 바로 '우선순위', 즉 선입선출 구조이나 '우선순위'대로 원소를 꺼낼 수 있다는 점이다. 우선순위를 만족하게 정렬하려면 여러가지 방법이 있다. 가장 단순한 방법은 O(n)이라는 시간에 모든 원소를 비교해서 정렬할 수 있다. 하지만 당연히 이 방법은 사용하지 않을 것이다. 이진 탐색 트리(Binary Search Tree)를 사용하면 O(logn)의 시간에 정렬할 수 있지만 이는 책의 표현을 빌려 쓰자면 "닭 ..

백준 16900번 - 이름 정하기 www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net KMP 알고리즘 문제이다. 사실 KMP라 하기도 조금 아쉽지만 어쨌든 Pi (접두사 == 접미사 인 최장길이)만 사용하면 해결 가능하다. 계속해서 더해갈 건데 이때 pi가 중요하다. 이유는 접두사==접미사 라면 그만큼의 길이를 빼고 더해줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..

백준 9248번 - Suffix Array www.acmicpc.net/problem/9248 9248번: Suffix Array Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정 www.acmicpc.net 이 문제는 접미사 배열 문제이다. 오전에 맨버 마이어스 알고리즘을 공부해서 쉽게 풀 수 있을 것 같아서 풀어보았다. 테스트 케이스도 다 정확히 나오길래 드디어 플래 문제를 풀어보는구나 했는데 시간 초과.. 도저히 어디가 문젠 지도 모르겠고.. 구글링은 귀찮고.. 뭔가 이상해서..