https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 평범한 그래프 탐색문제이다. DFS를 사용해도 좋고, BFS를 사용해도 좋다. 본인은 BFS를 사용하여 각 섬의 개수를 탐색하였다. 차이점라고 하기에도 뭐하지만 굳이 뽑자면, 대각선에 있는 섬도 연결되어있는 섬으로 보기 때문에 현재 좌표를 기준으로 주위에 있는 모든 방향(8방향)을 모두 탐색해야한다. 그래프 문제 푼지 오래된거 같아서 오랜만에 간단히 하나 풀었다. 코드는 다음과 같다. imp..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사를 하기 전까지 최대 수익을 내야하는 문제이다. 실버3이지만 앞에서 미리 포스팅했던 포도주 시식이나 RGB거리 등 다른 Dp문제보다 더 애먹었다. Dp 문제를 접하는 마인드로 일단 어떻게든 다 훑어야지 라고 생각하며 접근했는데...처음 2중for문으로 점화식을 짰는데...예외 상황이 너무 많아서 하나씩 예외처리를 하다보니까 코드가 Greedy하게 변했다. 결국 풀다가 시간이 너무 지나서 작성했던 코드 다지우고 담날에 새로 하자는 마인드로 그냥 잤다 ㅋㅋ 담날에 수업시간에 잠깐 봤는데 어떻게 탐색해야할지 새로운 아이디어가 떠올라서 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 처음 봤을때 DFS 쓰는 문제인가? 했는데 DFS를 사용해도 답은 나오겠지만 너무 가짓수가 많아서 시간초과에 걸릴게 뻔했다. 숫자들이 규칙이 없는것이 아니라 1차이라는 규칙이 있으므로 그냥 Dp썼다. Dp를 점점 하면서 느낀거지만 문제가 다 똑같다. 물론 아직 Dp애기 수준이라 실버1 언저리 문제만 풀지만, 현재까지 느낀바로는 그렇다. 문제 풀이는 각 자릿수를 정해야하는데 첫번째 자릿수에는 0이 올수 없고, 앞자릿수에 영향을 받지 않으므로 미리 세팅을 해준다. dp[0][0]을 제외하고 나머지를 모두 1..

It's a one of the assignments of the Data Structure. There are several condition of assignment. 1. Stack must be implemented using an Array. 2. Finding maze program must be implimented using stack that I implement Actually I've implemented finding maze and similar things on baekjoon site that is famous online judge site of korean. So, these assignments are very easy to me. To implement Finding m..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제는 3연속 연결되어 있는 포도주를 마실수 없다는 것이다. 따라서 가능한 경우를 생각해보면 현재 위치를 i라고 했을 때 1. 앞 최댓값(dp[i-1])을 그대로 가져가는 경우 2. 앞앞 위치의 최댓값에 현재 포도주를 더하는 경우(dp[i-2] + wine[i]) 3. 앞앞앞 위치의 최댓값에 이전 포도주와 현재 포도주를 더하는 경우(dp[i-3] + wine[i-1] + wine[i]) 위의 세가지..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 유형은 Dp라고 되어있지만 내가 아직 Dp를 잘 몰라서 그런지 내가 Dp로 풀었는지 잘 모르겠다. 문제를 읽으면 Dp냄새가 술술 나긴 하는데 그냥 문제 읽고 구현했는데 풀렸다. 코드를 보면 배열 앞에서부터 합을 저장해 나가다가 음수로 빠지면 합을 0으로 바꾼다. 그리고 합이 최대값보다 커지면 최대값을 합으로 바꿔준다. 위의 과정을 배열을 한번 훑으면서 진행하면 연속합중에서 가장 큰 합이 나온다. 코드는..