파이톨치

[문제 및 출처] 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/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net [어떻게 풀까?] 이 문제는 에라스토테네스의 체를 이용해야 풀 수 있다. 이것을 써야 시간 복잡도가 작아지기 때문이다. 에레스토테네스의 체에 대한 개념은 다음 그림과 같다. 만약 2가 소수라면 2의 배수에 해당하는 수들을 모두 지워준다. 만약 3이 소수라면 3의 배수에 해당하는 수들을 모두 지워준다. 그렇게 되면 남은 수들은 모두 소수라는 이야기 이다. 이것을 코드로 구현하기 위해서는 수의 범위가 정해..

[문제 설명] [링크] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net [코드] import sys def isPrime(a): if(a

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 규칙을 찾기 위해서 일단 거리에 따른 최단 거리를 적어보자. 거리 최단 거리로 가는 방법 1 1 2 1, 1 3 1, 1, 1 4 1, 2, 1 5 1, 2, 1, 1 6 1, 2, 2, 1 7 1, 2, 2, 1, 1 8 1, 2, 2, 2, 1 9 1, 2, 3, 2, 1 이런식으로 구성이 된다. 이것만 봐도 간단한 규칙을 찾을 수 있다. 아직 못 ..