https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 2차원 배열 구현 기술을 키우기 위해 도전한 문제이다. 실버3임에도 불구하고 너무 오래 걸렸다..ㅠ 참고로 현재 회사의 면접 내 라이브 코딩테스트에서도 이와 유사한 문제를 풀었는데, 그때는 실패했기 때문에 더욱 절치부심하면서 풀고 있다. 이런 문제는 말그대로 작은 숫자부터 시작해서 점화식을 잘 만들면 아무리 큰 숫자가 와도 금방 풀기에 좋다. 여기서 나는 n 바퀴마다 한 바퀴의 길이, 시작점을 기준..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 다이나믹 프로그래밍의 진행방향을 확실히 하였기에 풀기에 쉬운 문제였다. 좌에서 우로, 상에서 하로 이동하기 때문에 행, 열 우선으로 이동하며 2차원 메모이제이션을 수행한다. 여기서 중요한 점은 어떻게 메모이제이션을 쓰면 될까?? 다이나믹 프로그래밍 시에 접근하는 칸의 숫자에 따라 경로가 정해지는 것이 아니라, 이전 경로의 숫자로 해당 칸의 접근 가능 여부가 정해진다. 따라서 이전 경로의..

https://tibyte.kr/247 이차원배열을 쓰지 않고 달팽이 배열(spiral matrix) 출력하기 01. 샌드박스 카페에서 이야기 중에 달팽이 배열(나선형 이차원 배열)에 대한 주제가 나왔다. 이 달팽이 배열을 출력하기 위해서는 프로그래밍 언어에서 제공하는 형태의 이차원 배열에, 수의 tibyte.kr 항상 2차원 배열에 약한 모습을 보였고, 특히 이런 회전 문제에 약했기에 학습용으로 들고 와봤다. 적용하기 넘나 간단하면서 용이한 공식이다! 크게 각 구간의 패턴을 구한 뒤, 첫 시작 숫자를 더해주는 방식으로 패턴화한다. 나도 배워야지,,, 줍줍

https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 예외 처리가 까다로웠는데, 보다 쉽게 푸는 방법이 있어서 그것도 같이 알아보았다. 최대 2자리의 수까지만 결합이 가능하기 때문에 i번째 자리까지의 최대 경우의 수를 다이나믹 프로그래밍으로 구할 때, 마지막 수가 두자리로 구했는지, 1개로 구했는지 구분해서 기록하였다. 처음에는 앞자리와 현재 숫자의 결합이 26을 기준으로 구분만 하였는데, 0 처리를 따로 해줘야 하더라.. i) 만약 해당 숫자가 0이라면 덧붙이기만 ..

너무나도 중요한 문제이기에 두고두고 다시 풀어보면 좋은 문제이다. 처음에는 시간을 기준으로 배열을 만들어야 하나 싶었지만 1e9로 지나치게 범위가 크다. 따라서 그런 생각은 버리고 두더지 배열로 두더지를 고르냐 마냐로 선택해서 최대 개수를 구하는 방식을 고려했다. 두더지는 개수가 최대 6666개이므로 해 볼만 하다는 생각이 든다. 대신 시간에 따라 두더지를 잡을 수 있기 때문에 시간 순으로 두더지를 정렬해야 한다. 여기서 막혔던 점은 그렇다면 어떻게 두더지 배열을 세울까, 즉 점화식에서 다시 막혔다. 여기서는 해당 두더지를 방문한다는 전제 하에 그 이후의 최대 두더지 수를 기록하기로 한다. 그리고 이전까지는 다이나믹 프로그래밍에서는 뭔가 간격이 정해져있어서 바로 비교해야한다는 편견이 있었다. 하지만 다이..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 아래 블로그글이 매우 유용했다. https://yabmoons.tistory.com/536 [ 백준 2133 ] 타일 채우기 (C++) 백준의 타일채우기(2133) 문제이다. [ 문제 바로가기 ] [ 문제풀이 ] 3 x N 크기의 벽을 2 x 1 , 1 x 2 타일들로만 채울 때, 그 경우의 수를 구해야 하는 문제이다. 작은 수들부터 차근차근 만들어보면서 yabmoons.tistory.com