파이톨치

[내용] 그리디 알고리즘의 개념은 지금 현재 가장 욕심이 나는 것을 선택하는 것이라고 한다. 가령 이런 것이다. 지금 내가 가장 하고 싶은 것은 게임이다. 내가 현재 게임을 하게 된다면 나는 행복할 것이다. 하지만 이것이 나의 미래에 긍정적인 발적을 만들어주지는 못한다. 이것이 그리디 알고리즘의 단점이라고 한다. [백준 문제] https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 정말 ..

[문제 및 출처] https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [어떻게 풀까?] 이 문제는 오래 전부터 풀고 싶었다. 하지만 내 실력이 부족하여 나는 이전에 풀지 못하였고 지금에 와서야 구글링과 여러 경험치들을 쌓아 다시 도전했다. 이 전에는 남들이 쓴 코드를 보고도 이게 뭔 소린가 싶었다. 하지만 지금은 코드를 보고 제대로 이해하고 있다. 스스로의 성장이 느껴지는 문제라 감회가 새롭다. 나는 프로그래밍을 시작한지 반년도 되지 않아서 사실 이 문제가 많이 ..

[문제 및 출처] https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [어떻게 풀까?] 조건은 다음과 같다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 앞에서 나온 문제들을 차근차근 풀었다면 굉장히 쉽게 풀 수 있을 것이다. [코드] N, M = map(int, inpu..

[문제 및 출처] https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [어떻게 풀까?] 사실 이 문제는 N과 M(1)문제를 풀다가 실수로 풀어버렸다. 문제의 조건은 다음과 같다. 이 문제는 중복을 허용하는 문제이다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 코드는 다음과 같다. [코드] N, M = map(int, input().split()) used = [False] * (N+1) answer = [] ..

[문제 및 출처] https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [어떻게 풀까?] 문제의 조건은 다음과 같다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 아! 그렇다면 내가 진행하고 있는 수보다 큰 수를 다음에 진행하면 되지 않을까? 이런식으로 말이다. [코드] N, M = map(int, input().split()) used = [False] * (N+1) answer = [] def df..

[문제 및 출처] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [어떻게 풀까?] 이 문제는 백트래킹 문제라고 한다. 사실 나는 백트래킹이고 뭐고 다 재귀 같다. 내가 초보자라서 그런지는 몰라도 비슷비슷한 것 같다. 그래서 카테고리도 그냥 재귀에 넣었다. 아무튼 이 문제를 풀다 열심히 고민을 하다 잘 풀리지 않아서, 여러 유튜브와 블로그들을 찾아보았다. 많이 사람들이 Bool형 배열을 이용하여 이를 푸는 것을 보았다. 변수의 이름은 마치 동..

[문제 및 출처] https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net [어떻게 풀까?] 이 문제는 카운팅 정렬을 이용해서 풀라는 설명에 따라서 카운팅 정렬이 무엇인지 찾아보았다. 간단하게 생각해서 list를 만들어서 그 list의 인덱스에 해당하는 값에 +1을 해주면 된다. 예를 들어 list가 array = [1, 1, 3, 7, 10] 이라고 한다면 1 2 3 4 5 6 7 8 9 10 2 0 1 0 0 0 1 0 0 1 이런식으로 작동하게 된다. 그래서 간단하..

[문제] [출처 및 링크] https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net [어떻게 풀까?] 이 문제를 풀기 위해서는 원의 접점에 대한 개념이 있어야 한다. 고등학생 때 다들 많이 풀어보았을 것이라고 생각한다. 이 문제에서 output으로 나올 수 있는 값은 한정되어 있다. -1, 0 ,1, 2로 말이다 output이 -1인 경우는 원이 완전히 겹치는 경우이다. 이때는 문제 조건에 따라서 -1이 출력된다. 이 값이 나올 수 있는 조건은 굉장히 한정적이어서 따로 처리해 주면 될 듯 하다. outpu..