컴퓨터하는 kimmessi

www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 해결 알고리즘 문제의 다리 놓기의 경우의 수는 사실 조합과 같다. 그렇기 때문에 $_{1}C_{1}$부터 $_{30}C_{30}$의 값을 배열에 넣고 입력 값에 대한 조합 값을 출력해주면 된다. 1. 우선 배열에 모든 조합 값을 다 넣어준다. 이때 입력 값이 너무 크면 오버플로우가 생길 수 있으므로 배열은 long long 으로 선언해주어야한다. 또, 동쪽과 서쪽의 사이트가 바뀌어도 경우의 수가 같으므로 ..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해결 알고리즘 1. 큐(q)에 1부터 N까지의 숫자들을 순서대로 push해준다. 2. 큐(q)안에 숫자들이 모두 없어질 때까지 K번 옆으로 갈 때 과정에서 지나치는 숫자들은 큐의 맨 앞에서 맨 뒤로 보내고, K번 가서 도착한 그 숫자는 출력하고 큐(q)에서 pop한다. 여기서 큐의 사이즈가 1이 아니면 뒤에 쉼표(,)를 출력한 후 pop한다. 소스 코드 #include using namespace std; int main(){ int N, K; cin >> N >> K; queue q; cout

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 알고리즘 1. 배열(v)과, 수열 저장 배열(dp)를 선언한다. 2. 수열 저장 배열(dp)에 처음(first)에는 처음부터의 가장 긴 증가하는 부분 수열의 원소 개수를 저장하고, 두 번째(second)에는 바로 전의 원소의 인덱스를 저장하도록 설정한다. 수열의 전에 아무 원소도 없는 원소에는 second..

https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거� www.acmicpc.net 문제 해결 알고리즘 1. 리스트(lt)를 선언하고, 그 리스트의 iterator(lt_iter)의 위치를 리스트가 시작하는 부분(lt.begin())으로 선언해준다. 2. 입력 받은 string(str)의 길이(str_len)만큼 현재 위치(str_idx)가 도달하면 키로거 탐색을 끝내는 식으로 구현한다. string에서의 현재 위치(str[str_idx])에 2-1 ''가 존재하면, iterator가 리스트의 ..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 문제 해결 알고리즘 1. 물고기 배열(arr)에 모든 입력을 받은 후, 큐(q)에 물고기가 있는 위치를 전부 저장한다. 2. 큐에 있는 위치들을 차례로 방문 확인 배열(visited)에서 탐색(bfs)한 후, 각 위치마다 가장 가까운 물고기와의 거리를 기록한다. 3. 탐색을 다 끝낸후, 물고기 방문 확인 배열(visited)에서 위치 중 가장 큰 숫자를 찾아서 출력(r..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 해결 알고리즘 1. 우선 물고기 배열(arr)에 입력 값들을 받으면서, 현재 아기 상어가 있는 위치를(start_x, start_y) 저장한다. 2. 아기 상어가 있는 위치에서 시작하여, 물고기 배열(arr)에 모든 위치에 몇 초만에 도착할 수 있는지 방문 확인 배열(visited)에 저장한다(자기 자신의 크기보다 큰 물고기가 있는 위치는 제외). 3. 그 중, 물고기 배열(arr..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로�� www.acmicpc.net 문제 해결 알고리즘 1. 배열에 방문 하지 않았고, 배열 값이 1인 배열들을 탐색한다(bfs). 탐색이 전부 끝난 상황이면 (3번으로) 2. 탐색(bfs)를 하다가 더 이상 1이 나오지 않으면, 그림의 넓이(cnt)를 벡터(v)에 저장하고, 그림의 개수(num)을 1 더해준다. (1번으로) 3. 마지막으로, 그림의 개수(num)과 vector v에서 최댓값을 출력해준다. 소스코드 #include #..

https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 이 문제를 처음에 풀 때는 간단하게 while문을 이용해 풀려고 했지만, 시간초과가 나는 것이다. #include using namespace std; int main() { int a, b, v, sum = 0, cnt = 0; cin >> a >> b >> v; while (true) { cnt++; sum += a; if (sum >= v) break; sum -= b; ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 우선 피보나치 함수를 구현할 때는 두 가지 방식으로 구현을 할 수 있다. 첫번째 방식 - 재귀 문제의 코드처럼 계속해서 재귀적으로 함수를 호출해서 1 또는 0이 되게 만드는 방식이다. 그렇게 되면 만약 5라는 값이 함수에 들어오게 되면 fib(3)과 fib(4)로 나뉘게 되고 또 그 두 함수들도 계속 쪼개지다가 0과 1이 될 때, 함수 호출을 멈추게 된다. 그렇게 되면 했던 계산을 계속 되풀이할 뿐만 아니라 시간적으로도 엄청난 손해를 보게되는 방식이다. 두 번째 방식 (정답 코드) - DP 두..