파이톨치

[문제 및 출처] 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..

[문제] [출처 및 링크] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net [어떻게 풀까?] 나는 어제 이 문제를 풀어 보았다가 실패하였다. 구현 자체는 그렇게 어렵지 않다고 생각한다. 하지만 백준에서 요구하는 시간을 초과하였고 나는 문제 풀이에 실패하였다. 왜 실패하였을까? 어떻게 해결할까? 하다가 아직 안 푼 문제중 소수 찾기라는 문제를 보게 되었다. 소수 찾기 라는 문제를 풀면서 더 효과적인 방법을 생각했고 이를 적용해..

[문제] [출처 및 링크] 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