끄적끄적 개발로그

📖 문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 👩‍💻 문제풀이 처음엔 DP문제라고 생각하고 풀었는데, 가뜩이나 잘 못하는 DP인 데다 정답도 나오지 않았다. 찾아보니 BFS 활용문제.... BFS는 더 못해서 산 넘어 산^^.. 각종 블로그를 통해 정답코드를 분석해봐도 너무나도 방대한 양으로 진행되어 파악 불가...... 그래서 BFS 기본코드를 디버깅하면서 돌아가는 모습을 확인했다. # bfs 기본 ..

📖 문제 링크 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 👩‍💻 문제풀이 백준 2630 - 색종이 만들기 문제를 먼저 풀면 쉽게 해결할 수 있다. 2630번은 각 변을 2개로 나눠가는 문제였다면, 본 문제는 3개로 나눈다. 9사분면을 만들 수 있도록 행렬을 나눠주면 쉽게 해결 가능! ✅ 최종 코드 import sys input = sys.stdin.readline n = int(input()) paper = [list(map(i..

📖 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 👩‍💻 문제풀이 이분 그래프란 간단히 말해서, 한 간선의 양쪽 정점이 각각 다른 색(그룹) 이어야 한다는 것! 아래의 두 그래프를 보자. 왼쪽 그래프는 한 간선에 빨강, 파랑 점이 하나씩 연결된 반면(이분그래프), 오른쪽 그래프는 주황색 화살표가 가리키는 간선이 빨강-빨강 점으로 연결된 것을 알 수 있다(이분 그래프가 아님). 이러한 특징을 염두에 두고 DFS로 풀이를 시작했지만 도..

📖 문제 링크 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 👩‍💻 문제풀이 DP문제 로드맵의 거의 마지막 문제인데 도저히 규칙도 안 찾아져서...^^ 이러한 유형의 문제를 익힌다는 생각으로 아래의 블로그를 따라 작성하였다. https://archive-me-0329.tistory.com/23?category=965963 백준 2011 파이썬 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 정말 단순하게도 '제곱수들을 N번째 숫자까지 모두 저장해놓고 큰 수부터 빼면 구해지지 않을까?'라고 생각했다. 하지만 곧 반례를 찾았고, 이미 위와같은 생각에 사로잡혀 다른 방법이 도저히 떠오르지 않았다. 심지어 백준님의 강의로 해설을 듣고 나서도 대체 이것이 어떻게 구현된다는 말인지 아직까지도 이해가 안 되고 있다....... 대충 50% 정도의 현 이해력..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 증가 부분 수열과 가장 긴 감소 부분 수열을 적용하여, 그 결과를 합하면 해결이 될 것이라 생각했다! 하지만 백준 반례를 도입해서 고민해봐도 도저히 답이 찾아지지 않아 해답을 찾아보았다. 내가 실수했던 것은, 그저 증가수열과 감소수열의 결과에서 각각의 최댓값을 더하면 된다고 생각한 것이었다. 바이토닉 부분 수열이란, 계속 증가되던 부분 수열의 최댓값에서 -> 다시 감소되기 시작하는 수열을 말하는 것! 이해가..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 처음 세운 규칙은 1. 현재 잔(w4)+이전 잔(-1)+전전 잔(-3) 2. 현재 잔(w4)+전전 잔(-2)+그이전 잔(-3) 이렇게 두가지 경우로 식을 세워서 풀어보았지만 실패! 그래서 다른 분들의 백준 풀이를 찾아보니, 현재 잔을 마시지 않는 경우를 포함해야한다는 것을 깨달았다. 1. 현재 잔(w4)+이전 잔(w3)+전전 잔(w1) 2. 현재 잔(w4)+전전 잔(w2)+그이전 잔(w1) 3. 현..