https://www.acmicpc.net/problem/14718 난이도 : 골드 4 알고리즘 유형 : 브루트포스 풀이 시간 : 39분 문제 풀이 N명의 적 병사가 있다. 적 병사는 힘, 민첩, 지능 세가지 스텟을 보유하고 있고 진수가 적의 세가지 스텟보다 높은 스텟을 갖고있다면 그 적 병사를 이길 수 있다.적어도 K명의 병사를 이길 수 있게 하는 최소한의 스탯 포인트를 구하여라. 먼저, 해당 문제를 재귀함수로 접근하게 된다면 $O(100^{100})$으로 시간초과가 발생하게 된다. 그러면 어떻게 완전탐색으로 문제를 풀어낼 수 있을까 ?? 정답은 세가지 스탯에 대한 모든 조합을 기준으로 판별하면 된다. $병사의 수 ≤ 100$이기 때문에 병사의 모든 스탯 조합을 짜게 된다면 3중 for문으로 $O(10..

https://www.acmicpc.net/problem/17136 난이도 : 골드 2 알고리즘 유형 : 백트래킹  풀이 시간 : 47분 문제 풀이 색종이는 1 ~ 5 사이즈의 정사각형 크기를 갖고 있고, 크기마다 5장씩 보유하고 있다. 10 x 10 격자에 1이 적힌 모든 칸을 붙이는데 필요한 색종이 최소 개수를 구하자. 해당 문제는 큰 부분부터 가리면 될 것이다라는 그리디 사고 + 백트래킹 알고리즘을 사용하면 된다.시간복잡도를 계산해 보았을 때, 이론적으로는 최대 1의 개수는 100개이기 때문에 최악의 경우 $O(5^100)$이지만, 실제로는 문제 내에서 가지치기가 많이 일어나기 때문에 결과론적으로는 시간 내에 수행이 가능하다. (시간복잡도 정확한 계산을 아시는 분이 있으시다면 .. 도움을 ....)..

https://www.acmicpc.net/problem/2342 난이도 : 골드 3 알고리즘 유형 : DP 풀이 시간 : 51분 문제 풀이 DDR의 입력이 지시 사항으로 주어질 때, 승환이가 사용하는 최소 힘을 출력하라. DDR을 하는 데 사용되는 힘은 다음과 같다.중앙 -> 다른 지점 : 2 인접 지점 (왼쪽 -> 위 / 아래) : 3 반대편 (왼쪽 -> 오른쪽) : 4 해당 문제를 마주하면 그리디로 문제를 해결해야 할 지, DP로 문제를 해결해야 할 지 머리가 매우 뜨거워진다. 이럴 땐, 각 알고리즘의 정의를 다시 한 번 떠올리자.그리디 알고리즘의 경우, 항상 최적의 값을 갖는 경우로만 이동하고자 하는 알고리즘이다.DP의 경우, 이전 결과가 현재 결과에 영향을 미치지 않고, 단순히 이전 결과를 사용..

https://www.acmicpc.net/problem/4811 난이도 : 골드 5 알고리즘 유형 : DP 풀이 시간 : 29분 문제 풀이 종수 할아버지는 매일 약 반 알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.종수는 2N일동안 약을 먹을 수 있는데, 약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H를 보낸다. 총 2N일이 지난 뒤, 만들어질 수 있는 서로 다른 문자열의 개수를 구하여라 해당 문제는 경우의 수를 구하는 문제이다. 문제를 읽어보면 알약 한 개를 꺼내서 먹거나, 반 개를 꺼내서 먹거나의 경우가 존재한다. 또한, 문자열의 개수를 구하는 문제이기 때문에, 굳이 문자열..

https://www.acmicpc.net/problem/1406 난이도 : 실버 2 알고리즘 유형 : 자료구조, 덱  풀이 시간 : 17분 문제 풀이 에디터를 구현하려고 한다. 에디터에는 커서가 존재하는데, 각 명령어에 따라 문장을 수정할 수 있다. 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하자.L커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)B커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임P $$라는 문자를 커서 왼쪽에 추가함 문제를 읽고 바로 생각날 수 있는 알고리즘은 단..

https://www.acmicpc.net/problem/2573 난이도 : 골드 4 알고리즘 유형 : 구현, BFS 풀이 시간 : 32분 문제 풀이 빙산의 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하자. 문제는 매 해마다 두가지 동작을 반복한다.1. 빙산이 두 덩어리로 분리되었는지 체크(BFS)2. 빙산의 녹는 정도 계산(구현) 먼저, 빙산이 두 덩어리로 분리되었는지 체크하기 위해서는 BFS를 사용할 것이다. 빙산이 아직 떨어지지 않았다면 BFS는 한 번만 실행하고 끝날 것이다. 하지만, 만약 BFS를 한 번 실행했는데도 불구하고 또다른 BFS..

https://www.acmicpc.net/problem/20166 난이도 : 골드 4 알고리즘 유형 : DP, DFS, 문자열 풀이 시간 : 35분 문제 풀이 알파벳 소문자가 들어간 격자의 정보와 k개의 문자열이 주어졌을 때, 각 문자열마다 만들 수 있는 경우의 수를 출력하는 문제이다. 문제를 풀기에 앞서 제약 사항들이 주어진다. - 상하좌우 대각선 방향으로 한 칸씩 이동하여 문자열을 이어붙일 수 있다.- 이미 지나왔던 칸들을 다시 방문할 수 있다.- 격자의 좌표를 벗어난 경우, 반대편으로 이동한다. (ex. (1, 1)에서 위로 이동하면 (n, 1))- 중복된 문자열이 입력으로 주어질 수 있다. 해당 문제를 대략적으로 살펴봤을 땐, DFS 알고리즘을 사용해 가능한 경우의 수를 모두 찾아보는 방법이 있..

https://www.acmicpc.net/problem/16985 난이도 : 골드 2 알고리즘 유형 : 완전탐색, BFS 풀이 시간 : 1시간 28분 문제 풀이 문제가 매우 길기 때문에 간략히 요약해보자5 x 5 x 5 사이즈의 미로가 존재한다.주어진 판들은 시계 or 반시계 방향으로 회전이 가능하다.참가자는 판 5개를 무작위로 쌓는다.입구에서 입구와 면을 공유하지 않는 꼭짓점인 출구까지 가는 데 걸리는 이동거리의 최솟값을 구하자.이 문제를 처음 접할 때는 매우 고려해야 할 사항이 많지만, 일단 천천히 생각해보자.우리가 고려해야 할 부분은 다음과 같다. 1. 시계 방향 혹은 반시계 방향으로 회전이 가능하다.; 위 이슈의 경우, 어떤 방향으로 회전하든지 한 방향만 택해서 회전하면 된다. 어차피 어느 쪽을..

https://www.acmicpc.net/problem/14658 난이도 : 골드 3 알고리즘 유형 : 브루트포스, 완전탐색 풀이 시간 : 1시간 3분 문제 풀이 욱제는 커다란 네모난 $L * L$ 크기의 트램펄린을 준비했다. 이 트램펄린을 사용하여 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 최소 개수를 구하자. 문제의 조건을 먼저 살펴보면, 지구의 크기를 나타내는 $0 ≤ N, M ≤ 500000$, 트램펄린의 크기를 나타내는 $1 ≤ L ≤ 100000$이 주어진다. 모든 지구를 탐색하는 방법을 사용한다면, 최악의 경우, $O(n^2)$로 시간초과가 날 것이다. 문제에서는 별똥별의 개수도 주어졌다($1 ≤ K ≤ 100$). 별똥별의 위치 정보를 활용한다면 조건 안에 문제를 해결할 ..

https://www.acmicpc.net/problem/1806 난이도 : 골드 4 알고리즘 유형 : 투 포인터 풀이 시간 : 24분 문제 풀이 길이 $N$인 수열에서 연속된 수들의 부분합 중에 그 합이 $S$ 이상이 되는 것 중 가장 짧은 길이를 구하자. 연속된 수들의 부분합을 구하는 문제이기 때문에, 정렬을 사용할 수 없다. 또한, 특정 구간이기 때문에 누적합을 사용할 수 없다. 따라서 본 문제는 투 포인터를 활용해 문제를 풀어나갈 수 있다. 먼저, 배열의 위치를 제공해줄 포인터 두 개 `left`, `right`를 생성하고, 수열의 0번 주소의 값으로 초기화를 진행해준다.이후, 반복문을 통해 배열을 순회할 것인데, while 문을 사용하여 `left` 인덱스 번호가 `right` 인덱스 번호보다 ..