컴공과고씨

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해결 방법은 2차원 배열을 이용해서 map을 만들어주고 사과가 있는 칸에는 1을 넣어준다. 입력으로 시간과 방향 정보를 받아 준다. 방향을 바꾸기 전까지 반복문을 돌아줄건데 다음 x좌표와 다음 y 좌표를 구해주고 맵을 벗어나는지 확인해주고 visit을 체크해줄건데 visit은 몸이 있는 좌표에 true를 넣어주는 것이다. 뱀이 사과를 먹는 경우에 몸의 길이가 늘어나는데 이때 큐에 좌표를 넣어주고 v..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 n이 되도록 찾는 식으로 풀어 주었다. 배열에 저장하지 않고 연산을 계속하면서 찾을 경우 당연히 연산 시간이 오래걸려 시간초과가 난다. 합이 n이 되도록 할 때 최소 개수의 수로 만들어야 ..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 일단 규칙을 파악해보면 n = 7, k=3 일 때 12[3]45[6]7 12[4]57 [1]25[7] 이런식으로 []안에 있는 것을 출력할 것이다. 쉽게 생각해보면 자기 차례가 아닌 것을 뒤로 보내주면 연결이 된다. 12[3]45[6]712[4] 이런식으로 말이다. 바로 queue를 쓰면 쉽게 이 방식을 구현할 수 있다. 자기 차례가 아니면 뒤로 옮겨주고 자기 차례인 경우 pop을 해주면 된다. ps. 출력 형식이 안에 있으니 주의 하도록 하자. 단계별 풀이 1. 정답을 저장할 vecto..

https://www.acmicpc.net/problem/23284 23284번: 모든 스택 수열 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 www.acmicpc.net 문제를 보고 일단 구해보려고 직접 써보았다. 그러다 보니 떠오른생각이 N-Queen하고 비슷한 문제인 것을 느껴서 백트래킹 쪽으로 생각하게 되었다. 왜 비슷하면 각 자리마다 숫자를 넣을 때 이 숫자를 넣으면 수열이 가능한지 아닌지를 판단 한 후 아니면 다른 수를 넣는식으로 가기 때문에 n-queen도 각 자리에 퀸이 들어갈지 아닐지를 판단하는 문제였어서 비슷하다고 느꼈다. 이..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다. 각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다. 표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 ..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 문제를 읽고 bfs를 떠올렸다. 아이디어 백신 놓기 전과 결과를 비교한다. 여기서 만약 다른게 나오면 bfs를 돌려서 숫자를 결과의 값으로 바꾸어 주고 백신은 한번만 놓을 수 있기 때문에 비교를 멈춘다. 그 후 바뀐 값과 주어진 결과를 비교해서 하나라도 다른 값이 있다면 no를 다 똑같다면 yes를 출력해주면 된다. 단계별 풀이 1. 입력값 받을 두 개의..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이런 문제의 경우 각 경우 마다 최적의 경우의 수를 선택하면서 가면 된다. 저런식으로 각 자리를 늘려가면서 A에서 C가 들어갔을 때 LCS의 경우 0 AC와 C의 LCS = 1 이런식으로 표를 채워가준다. 중요한 것은 LCS가 하나 더 늘어나는 경우는 문자가 들어갈 수 있을 때 예를 들면 ACAYK 와 CAP 다음 순서에 ACAYKP 와 CAP가 나온다..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 직접 도형을 그려보면서 어떤 규칙이 있는지 보았지만 도형 모양안에서 규칙을 찾기는 힘들었다. 그래서 고민하다가 도형 개수에 대한 규칙을 찾아서 풀었다. 도형의 개수 1 -> 1개 2 -> 2개 3 -> 3개 4 -> 5개 5 -> 8개 6 -> 13개 직접 그려보면 이렇게 개수가 나온다. 그럼 점화식이 보인다. n = (n-1) + (n-2) 근데 중요한 것은 문제에 보면 10007로 나눈 나머지를 구하는 것이다. 해..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제를 보고 규칙이 있을 것 같아서 쭉 써보았다. 1 -> 1개 2 -> 2개 3 -> 4개 4 -> 7개 5 -> 13개 여기서 점화식을 알아낼 수 있는데 n = (n-1) + (n-2) + (n-3)번째 라는 점화식을 볼 수 있었다. 점화식은 다이나믹 프로그래밍으로 풀면 쉽게 풀 수 있어 다이나믹 프로그래밍을 이용하여서 문제를 풀었다. 단계별 문제 풀이 1. dp 배열 선언 2. 초기값 dp[1], dp[2], dp[3] 값 입력 3. 점화식을 이용해서 풀어줌 전체코드 1 2 3 4 5 6 ..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 떠올린 방법은 정렬하지 않고 일단 unique 함수를 사용해서 연속되는 수를 제거한다. (unique, erase를 잘 모른다면 https://hagisilecoding.tistory.com/53 여기서 공부하고 오면 편함) aabbbccb가있다면 unique함수를 정렬을 하고 써주면 연속되는 값이 쓰레기 값으로 가고 이것을 erase를 통해 지워주면 abcb가된다..