전체 글

풀이 명백한 공식을 찾기는 어려워 보인다. 하지만 하위 개수 경우가 상위 개수에 영향을 끼치는 것 같다. 바로 생각이 나지 않을 때는, 한번 나열해 보자. N=2일 때: 11,00 2가지 경우가 있다. N=3일 때: 001, 100, 111 3가지 경우가 있다 N=4일 때: 0000,0011,1001,1100,1111 5가지 경우가 있다. N=5일 때: 00001,10000,00100,00111,10011,11001,11100,11111 7가지 경우가 있다. 피보나치수열처럼 이전 두 항의 합이 다음 항의 값이 되는 것처럼 보인다. 왜 그럴까? 길이가 N인 수열을 만든다고 가정하자. 이전 N-1번째나 N-2번째 수열은 그 사이에 숫자를 삽입하지 않고 뒤에만 숫자를 붙인다고 가정할 수 있다. 이는 N-1번째..

풀이 일단 2보다는 3으로 나누는게 더 숫자를 작게 만들 수 있어보인다. 그렇다면 일단 3의 배수가 될때 까지 1을 뺀후 3으로 나누면 되는 것일까? 하지만 그렇게 하면 8같은 경우 3으로 나누는 것만 추구하면: 8->7->6->2->1 로 5회 2로만 나누면: 8->4->2->1로 4회 로 2로만 나눈 값이 더 작다. 즉, 고정된 공식이 명백히 더 빠르다는 것을 보장해 줄 수 없다. 명백한 공식이 없다면 결국 경우를 빠르게 계산 해야 한다. 그 경우를 모두 빠르게 제시하는 과정에서 동적 프로그래밍을 사용한다. 이 문제는 동적 프로그래밍 문제다. 차근차근 낮은 값들을 바탕으로 높은 값을 추론해내면 되는 것이다. 정수를 받아 그 길이 보다 1만큼 큰 배열을 만든다. 배열에 배열의 인덱스가 1에 도달하는 연..

풀이 일단 출력할 수 없는 경우 먼저 생각하자. 사고의 순서를 써보자 1.가장 봉지수가 적은 경우를 찾아야 한다. 2.그러기 위해서는 가능한 5kg 봉투를 많이 사용해야 한다. 3.그렇다면 3kg 봉투는 최소로 사용해야 한다. 4.그렇다면 3kg 봉투는 5kg으로 나누어떨어지지 않을때 5kg로 나누어 떨어지게 만드는 용도로만 사용한다. 이걸 알고리즘으로 바꿔서 생각해보자 1. 우선 현재 무게가 5로 나누어 떨어지는 지 확인하고 그렇지 않으면 3kg를 챙긴다. 2. 무게가 5로 나누어 떨어지게 되었으면 그때부터는 모두 5kg을 가져가면 된다. 3. 빼는 과정에서 무게가 음수가 발생하면 -1을 출력한다. 해답 코드 #include #include int main(void){ int x=1; int count..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 count;//몇개의 답을 출력해야 하는지 count에 저장 for(int k=0;k>n>>m; for(int i=1;i

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 풀이 동적프로그래밍 문제로, 한 칸 한 칸에 들어가는 모든 값을 계산하면 너무 오랜 시간이 걸린다. 그래서 기존에 계산해 놓은 값을 바탕으로 더 빠르게 값을 찾아야 한다. 우선 각 층의 0층에는 호수만큼 산다고 했으니, 다음과 같다. 1호 2호 3호 4호 3층 2층 1층 0층 1 2 3 4 그리고 조건에 맞게 들어가야 되는 인원을 채우면 1호 2호 3호 4호 3층 1 5 15 35 2층 1 4 10 20 1층 1 3 6 10 0층 1 2..

자바스크립트로 테트리스를 만드는 게시글이다. 코린이를 위해 친절하게 설명했다. 클론코딩을 바탕으로 해서 버그들을 수정하고 새로운 기능들을 넣었다. 이 게시글에서는 이제 새로운 것들을 추가할 것이다. 이전 게시글 링크들! 2023.02.05 - [개발/클론코딩] - JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 출처: https://www.youtube.com/watch?v=1lNy2mhvLFk&list=WL&index=2 위의 유튜브 영상을 보고 클론코딩하였다. js를 사실상 이 영상으로 처음 하면서 배운것들, 헷갈렸던 것들, 각 코드의 설명과 전체적인 흐름을 juneforpay.tistory.com ..

자바스크립트로 테트리스를 만드는 게시글이다. 코린이를 위해 친절하게 설명하였다. 소스코드 역시 제공된다. 기존에 있었던 게시글에서는 클론코딩을 하고, 그 버그들을 수정했다. 이제는 새로운 기능들을 추가할 것이다. 이전 게시글들 링크! 2023.02.05 - [개발] - JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 출처: https://www.youtube.com/watch?v=1lNy2mhvLFk&list=WL&index=2 위의 유튜브 영상을 보고 클론코딩하였다. js를 사실상 이 영상으로 처음 하면서 배운것들, 헷갈렸던 것들, 각 코드의 설명과 전체적인 흐름을 juneforpay.tistory.c..

자바스크립트로 만드는 테트리스 강의다. 코린이를 위해 쉽게 서술하였다. 지난 게시글에 이어서 개발을 진행한다. 기존의 클론코딩에서 있었던 버그들을 수정하는 데 중점을 두었다. 지난 게시글 링크! 2023.02.05 - [코딩] - JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 JavaScript로 테트리스 만들기, 코린이가 코린이를 위한 A-Z 설명 출처: https://www.youtube.com/watch?v=1lNy2mhvLFk&list=WL&index=2 위의 유튜브 영상을 보고 클론코딩하였다. js를 사실상 이 영상으로 처음 하면서 배운것들, 헷갈렸던 것들, 각 코드의 설명과 전체적인 흐름을 juneforpay.tistory.com 지난 글에서 기존 테트리스에서 개선..