본문 바로가기

분류 전체보기

 (191)
카드 바꾸기( BOJ 25401 ) 문제 : https://www.acmicpc.net/problem/25401 25401번: 카드 바꾸기 $N$개의 카드가 놓여있다. 편의상 가장 왼쪽에 있는 카드를 $1$번 카드, 그 다음에 있는 카드를 $2$번 카드 $\dots$, 가장 오른쪽에 있는 카드가 $N$번 카드라고 하자. $N$개의 카드에는 각각 정수가 하 www.acmicpc.net 문제 파악하기 N개의 카드를 등차수열로 만드는 문제입니다. 공차는 음수, 0, 양수 모두 될 수 있으며, 주어진 N개의 숫자 중 일부분을 바꿔 등차수열로 만들었을 때, 바꾼 카드 수의 최솟값을 구해야 합니다. 등차 수열을 만드는 가장 간단한 방법은 모든 숫자를 하나의 숫자로 통일하는 것입니다. 하지만 이 방법은 비효율적이기에 조금 더 효율적인 방법이 필요하며,..
조약돌( BOJ 25378 ) 문제 : https://www.acmicpc.net/problem/25378 25378번: 조약돌 좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다. 철수가 할 수 있는 작업의 종류는 아래 두 가지이다. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기 한 장소에 www.acmicpc.net 문제 파악하기 N개의 장소에 놓여진 조약돌을 2개의 작업으로 모두 가져오는 최소 횟수를 구하는 문제입니다. 두 작업은 임의의 개수를 가져올 수 있다고 했으나, 작업의 횟수를 최소로 해야하기 때문에 보통 하나 이상의 장소에 있는 모든 조약돌을 가져오는 작업이라고 할 수 있습니다. 아쉽게도 각 장소에 놓인 조약돌의 개수가 최대 108개이기 때문에 단순한 재귀함수 및 메모이제이션으로 해결할 수 ..
네온 사인( BOJ 8907 ) 문제 : https://www.acmicpc.net/problem/8907 8907번: 네온 사인 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭 www.acmicpc.net 문제 파악하기 N개의 꼭지점 중 3개의 꼭지점을 골라 삼각형을 만들었을 때, 모든 간선의 색이 동일한 경우의 수를 구하는 문제입니다. N이 최대 1,000이기 때문에 처음 보면 크지 않아 보이지만, 1000개의 정점 중 3개의 정점을 선택할 수 있는 경우의 수는 대략 1.6억 가지 경우의 수가 있습니다. 어마어마한 경우의 수이며, 이정도 규모라면 컴퓨터도 1초 안에 모든..
전구와 스위치( BOJ 2138 ) 문제 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 파악하기 입력된 N개의 스위치를 적절하게 눌러서 우리가 원하는 상태로 바꿀 수 있는지, 만약 바꿀 수 있다면 눌러야 하는 스위치의 최소 횟수를 구하는 문제입니다. 만약 N의 값이 작다면 직접 모든 경우의 수를 확인할 수 있지만 N이 최대 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 다행히 스위치는 항상 바로 왼쪽과 오른쪽에 위치한 전구..
RPG( BOJ 1315 ) 문제 : https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net 문제 파악하기 경험치를 힘(STR)과 지력(INT)에 적절히 투자해서 클리어할 수 있는 퀘스트의 최댓값을 구하는 문제입니다. 각각의 퀘스트는 클리어를 할 수 있는 힘과 지력의 제한이 있으며, 캐릭터의 힘과 지력 중 어느 한 곳의 능력치가 특정 퀘스트의 힘과 지력 제한보다 크거나 같다면 해당 퀘스트를 클리어하고 경험치를 얻을 수 있습니다. 문제를 해결할 수 있는 가장 단순한 알..
KMP 알고리즘 개요 KMP 알고리즘은 3명의 학자(Knuth-Morris-Pratt)가 만든 문자열 탐색 알고리즘입니다. 문자열(S)에서 문자(W)를 찾을 때 사용하는 알고리즘으로, O(|S| + |W|)의 시간복잡도를 가지는 어마어마한 알고리즘입니다. |S|와 |W|는 각각 문자열의 길이를 의미하며, 전체 시간 복잡도가 문자열과 문자 길이의 합이라는 건 단 1번의 탐색으로 문자열 속 문자를 모두 찾을 수 있다는 의미로, 매우 효율적인 탐색 알고리즘 중 하나입니다. 그럼 도대체 어떤 방식으로 탐색해서 이렇게 효율적인지 한번 알아봅시다. 알고리즘 영문 위키피디아의 예시를 통해 기본적인 알고리즘 구조를 살펴보겠습니다. 우선 문자열 S = "ABC ABCDAB ABCDABCDABDE"에서 문자 T = "ABCDABD" 를 ..
복구( BOJ 15908 ) 문제 : https://www.acmicpc.net/problem/15908 15908번: 복구 예제 1에 대해, 3번째 수와 6번째 수를 지우면 {3, 1, 2}, {2, 1}, {3, 1, 3}이 된다. 예제 2에 대해, 1번째, 8번째, 9번째, 11번째, 16번째, 17번째, 19번째 수를 지우면 {4, 2, 5, 5}, {5, 1, 4, 5, 1}, {4, 2, 5, 2}가 된다 www.acmicpc.net 문제 파악하기 N개의 숫자(사용자 데이터)를 적절하게 지워서 조건에 맞는 사용자 데이터를 만드는 경우의 수 중, 지운 숫자들이 가진 가능성의 최댓값을 가장 작게 만드는 경우를 구하는 문제입니다. 단순히 숫자를 지우기에는 100,000개의 데이터가 너무 많기에 문제를 좀 더 단순화 시킬 필요가..
창고 다각형( BOJ 2304 ) 문제 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 파악하기 주어진 막대 기둥을 둘러싸는 가장 작은 창고 다각형의 크기를 구하는 문제입니다. 주어진 입력의 범위가 크지 않기 때문에 어렵지 않게 해결할 수 있는 문제입니다. 이 문제에서 가장 중요한 점은 가장 높은 막대의 위치입니다. 가장 높은 막대의 위치를 기준으로 나눠서 생각해보면 쉽게 해결할 수 있습니다. 문제 해결하기 지붕을 오목하게 만들지 않으면서 창고 다각형의..

티스토리툴바