본문 바로가기

알고리즘

 (151)
[백준 / BOJ] 20921 그렇고 그런 사이 문제 출처 : https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 환주는 두명을 그렇고 그런 사이로 만드는데 전문가이다. 그렇고 그런 사이가 될려면, 다음 조건을 만족해야한다. (P(i)가 갖고있는 숫자가 P(i+a)보다 커야함) (단, a>0) 환주의 친구의수 N, 그렇고 그런 사이로 만들어야하는 쌍의수 K가 주어졌을때, 그렇고 그런 사이를 만드는 경우를 출력하는 문제다. 풀이 재밌는..? 문제였다. 문제를 처음 봤을때는 감이 잘 안잡혔는데,(dp라고 예상했었음) 문제의 예제를 직접 해보니..
[백준 / BOJ] 20920 영단어 암기는 괴로워 문제 출처 : https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 영어 단어장에 N개의 단어가 적혀있다. 화은이는 단어장에있는 N개의 단어들중 K개의 길이 이상의 단어를 다음 순서에따라 정렬할려고한다. 1. 자주 나오는 단어순으로 정렬한다. 2. 단어의 길이가 길수록 앞으로 배치한다. 3. 알파벳 사전 순으로 앞에있는 단어일수록 앞에 배치한다. N과 K, N개의 단어가 주어졌을때,..
[백준 / BOJ] 8972 미친 아두이노 문제 출처 : https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 종수는 R*C의 그리드에서 아두이노를 움직이는 게임을 진행한다. 이 게임에는, 종수의 아두이노와 미친 아두이노가 있으며, 미친아두이노는 항상 종수의 아두이노와 가장 가까워지는 방향으로 움직인다. 미친아두이노의 위치, 종수의 아두이노의 위치, 종수의 아두이노가 움직이는 방향이 주어졌을때, 그리드의 최종상태를 출력하는 문제다. (단, 종수의 아두이노가 미친아두이노를 만난다면 즉시 종료..
[백준 / BOJ] 16967 배열 복원하기 문제 출처 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자. (배열이 겹쳐지면 같은 위치의 수가 합쳐진다.) 배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다. 풀이 수학? 구현? 문제다. 배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같..
[백준 / BOJ] 9944 N*M 보드 완주하기 문제 출처 : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net N*M크기의 보드에 장애물(*) 빈칸(.)이 있다 보드의 빈칸위에 놓인 공은 다음 규칙에따라 움직인다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다. 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다. 게임은 공이 더 이상 이동할 수 없을때 끝난다. 모든 빈칸을 방문하기위한 이동횟수의 최솟..
[백준 / BOJ] 11049 행렬 곱셈 순서 문제 출처 : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어진다. 행렬 A의 크기를 N*M, 행렬 B의 크기를 M*K라고 할때, 각 행렬을 곱할때 필요한 곱셈 연산 수는 N*M*K이다. 모든 행렬을 곱하는데 필요한 최소 연산횟수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 풀리는 문제다. 처음엔 그리디로 생각했지만, 현재 최적값이 나중에도 최적이라는 보장이없기때문에 그리디로는 풀기 힘들어보인다. 이 문제처럼 ..
[백준 / BOJ] 1498 주기문 문제 출처 : https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 어떤 문자열 X를 n번 연달아 쓴 것을 X^n으로 나타낸다. 예를들어, 문자열, ababab는 ab^3이 된다. 문자열 X를 앞에서부터 i번째까지 주기문을 이룬다고 했을때, 해당 주기문의 n(n은 가능한 가장 크게)을 구하는 문제다. 예를들어, 문자열 abababab는 4 2 6 3 8 4 가 출력된다. 풀이 kmp로 푸는 문제였다. 주기를 찾는다는것은 ..
[백준 / BOJ] 1097 마법의 단어 문제 출처 : https://www.acmicpc.net/problem/1097 1097번: 마법의 단어 첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마 www.acmicpc.net N개의 단어가 있다. N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다. 문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. (문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.) 이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의..

티스토리툴바