본문 바로가기

분류 전체보기

 (191)
K번째 수( BOJ 1300 ) 문제 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 파악하기 2차원 배열 A[i][j]의 값을 정렬하여 1차원 배열 B[i]로 변환한 다음, K번째 숫자를 출력하는 문제입니다. 가장 쉬운 방법이라면 1차원 배열 B를 만든 다음, 2차원 배열 A에 있는 모든 값을 저장한 후 정렬하여 B[K]를 출력하면 됩니다. 하지만 이 문제는 배열의 크기가 최대 100,000*100,000 = 10,000,000,000..
습격자 초라기( BOJ 1006 ) 문제 : https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 문제 파악하기 원형으로 생긴 구역에 특수 소대를 효율적으로 배치하는 문제입니다. 구역이 원형으로 생겼다는 점에 초점을 맞춰서 탐색을 시작해야 합니다. 우선, 시작 구역과 종료 구역이 겹치는 경우를 파악한 다음 해당 케이스마다 탐색을 진행하여 배치하는 특수 소대의 최솟값을 구하면 문제를 해결할 수 있습니다. 문제 해결하기 그렇다면 우선 첫 번째로..
배수( BOJ 2595 ) 문제 : https://www.acmicpc.net/problem/2595 2595번: 배수 N은 30,000이하의 자연수이다. www.acmicpc.net 문제 파악하기 30,000 이하의 자연수인 N의 배수 중 가장 적은 개수의 숫자로 이루어진 가장 작은 배수를 찾는 문제입니다. 예를 들어 125의 배수는 무한히 많은 숫자가 있지만, 그 중에서 가장 적은 개수의 숫자로 이루어진 가장 작은 배수는 500을 의미합니다. 이 문제는 결국 1개 또는 2개의 숫자로 이루어진 N의 배수가 있는지, 그리고 그 중에서 가장 작은 숫자가 무엇인지 구하는 문제입니다. 참고로 모든 정수는 1개 혹은 2개의 숫자로 이루어진 배수를 무조건 가지고 있습니다. 문제 해결하기 우리는 그렇다면 0~9까지 숫자 중 2가지를 뽑아서 ..
재미있는 숫자 게임( BOJ 16876 ) 문제 : https://www.acmicpc.net/problem/16876 16876번: 재미있는 숫자 게임 구사과가 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다. www.acmicpc.net 문제 파악하기 4자리 숫자를 M번의 행동으로 N보다 크게 만들 수 있는지 없는지 판단하는 문제입니다. 설명 중 2명의 플레이어가 항상 최적의 방법으로 게임을 한다고 했습니다. 이는 자신의 차례에서 이기는 경우가 한 번이라도 있는 경우 해당 방법을 사용하겠다는 의미이며, 이는 나중에 탐색을 할 때 중요한 포인트가 됩니다. 이 문제의 경우, 최대 9999까지의 숫자가 나올 수 있으며, 게임을 진행하는 횟수(턴의 수) 또한 100이하이기 때문에 재귀함수와 메모이제이션을..
체스판( BOJ 12960 ) 문제 : https://www.acmicpc.net/problem/12960 12960번: 체스판 동혁이는 직사각형 체스판을 가지고 있다. 체스판의 행과 열은 0번부터 시작한다. i행 j열의 색은 i+j가 짝수이면 검정색, 홀수이면 흰색이다. 체스판의 일부 칸에는 말이 놓여져 있다. 윤호는 L- www.acmicpc.net 문제 파악하기 체스판 위에 놓을 수 있는 L-모양 타일의 최대 개수를 찾는 문제입니다. 단순히 놓는 것이 아닌, 몇 가지 규칙이 있는데 그 중 가장 중요한 규칙은 다음 2가지 입니다. 우선, 'X' 표시에는 이미 체스말이 놓여있기 때문에 L-모양 타일을 놓을 수 없습니다. 그리고 타일의 꼭지점 칸(두 정사각형과 붙어있는 칸)은 항상 체스판의 검은 칸 위에 놓아야 합니다. 이 2가지 조..
같은 탑( BOJ 1126 ) 문제 : https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 문제 파악하기 N개의 블럭이 있습니다. N개의 블럭을 적절하게 쌓아서 높이가 동일한 2개의 탑을 최대한 높게 만드는 것이 목표입니다. 단순히 재귀함수 sv( idx, left, right) 를 만들기에는 left와 right에 최대 250,000까지 들어갈 수 있기에 메모리/시간 모두 부족합니다. 그렇다면 문제를 어떻게 추상화시킬 수 있을까요? 문제 해결하기 그렇다면 le..
자물쇠( BOJ 1514 ) 1514. 자물쇠 : https://www.acmicpc.net/problem/1514 1514번: 자물쇠 세준이는 노트북을 누가 가져갈까봐 자물쇠로 잠가놓는다. 자물쇠는 동그란 디스크 N개로 구성되어 있다. 각 디스크에는 숫자가 0부터 9까지 숫자가 표시되어 있다. 디스크는 원형이기 때문에, 0 www.acmicpc.net 1. 문제 파악하기 자물쇠는 0~9까지 숫자가 있으며, 총 N개의 디스크로 구성되어 있습니다. 세준이는 한 번에 최대 3개의 디스크를 최대 3칸까지 돌릴 수 있습니다. 이 때, 세준이가 돌려야 할 최소 횟수를 구해야 합니다. 단순히 왼쪽부터 가까운 방향으로 회전해서는 최소 횟수를 구한다는 보장이 없기에 효율적인 탐색 알고리즘이 필요합니다. 2. 문제 해결하기 우선, 현재 가장 왼쪽의..
선물 전달( BOJ 1947 ) 1947. 선물 전달 : https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 1. 문제 파악하기 N명의 사람이 선물을 교환해야 합니다. 단, 다른 사람에게 꼭 자신의 선물을 건네야 합니다. 또한, N의 값이 1,000,000까지 커질 수 있으므로 long long int형을 사용해야 한다는 사실을 유념해야 합니다. 2. 문제 해결하기 DP[N]을 N명의 사람이 선물을 교환하는 방법이라고 정의하겠습니다. 만약 1번 사람이 K번 사람과 선물을 교환했다고 가정해봅시다. 그렇다면 위 상황은 (N-2)명의 사람들만 서로 선물을 교환해야 하는 상황으로 바뀌며, 이 때 방법의..

티스토리툴바