KidCat

아이디어는 금방 떠올렸는데 확신하는데 좀 시간이 걸렸던 문제였다. https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 수학적 증명말고 좀 더 쉽게 이해 해두려고 글을 남기기로 했다. 저울추 배열을 정렬했다고 가정하고 내가 X번째 저울추를 살펴보고 있다고 하자. 이 때 추의 무게를 m이라고 둔다. 내가 X번째 저울추를 꺼내기 전까지 모든 저울추의 무게합을 Z라고 생각해보자. 즉, 1번째....X-1번째 저울추까지의 무게의 합이 Z이다. 1) 만약 여기서 X번 ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제를 처음 풀고나서 위상정렬 푼 것이 조금 마음에 들지 않아서 구글링을 했었다. 검색한 블로그들을 읽어보니 DFS를 이용한 좋은 풀이 방법이 존재했다. 대부분의 블로그들이 다 똑같은 풀이 방법만 적혀 있었기 때문에, 내가 푼 다른 풀이를 적어놓기로 했다. 개인적으로 문제를 풀 때 다양한 풀이 방법을 접해보는 것이 좋다고 생각하기 때문이다. 문제를 읽었을 때 다음과 같은 풀이들을 생각했다. 모든 정..

https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 블로그에 풀이가 중복되면 리뷰하지 않는데, 다른 블로그 풀이를 봐도 이해하기 좀 힘들었다 이해하기 힘들었던 이유는 이 문제가 반복문 5개를 만들어야 되서 그렇다. 내 머리로는 범위 설정이 너무 헷갈렸다. 풀이는 바로 떠올랐는데, 반복문을 못 만들어서 한참걸렸다. 문제 풀이방법은 배열의 각 값마다 행,열로 등차수열 할 수 있는 최대치까지 붙여가면서 제곱수인지 판단하는 방법이다. 예를 들자면..

N-Queen 문제는 백트래킹을 이용한 웰노운 문제 중 하나이다. 내 풀이가 다른 블로그들의 풀이와 차이가 좀 있어서 글을 작성하게 되었다. 웰노운 문제이고 풀이방법이 존재하는 이상 내 풀이가 다른 풀이보다 더 좋은 풀이가 아니다. 실제로 백준의 N-Queen 문제에서 돌려본 결과, 내 풀이가 시간이 더 오래걸리는 것을 확인했다. 내 풀이를 설명하기 위해 체스판을 위에서 부터 1행, 2행 .. n행이라고 하고, 가장 왼쪽 열부터 1열,2열 .. n열이라고 하겠다. 여담으로 처음에는 DP로도 될것 같았다. 2*2 에 체스판이 있다고 하면, 왼쪽, 중간, 오른쪽 3군데에 체스판 열을 끼워넣으면 3*3 체스판이 된다. 2*2 체스판에는 끼워넣을 수 있는 곳이 3군데, 3*3 체스판은 4군데 .. 해서 N*N ..