본문 바로가기

알고리즘 공부

 (207)
[백준 파이썬] #15650: N과 M(2) www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [정답] 1. 두 수를 입력받아 N,M을 정의한다. 2. 1부터 N까지의 자연수 중에서 고르는 문제니까 수 1~N을 list에 넣는다. 3. itertools 모듈의 combinations() 함수를 사용하여 중복을 제외한 순서 상관없는 조합을 구한다. 4. for문을 돌면서 중복을 제외한 순서 상관없는 조합을 차례대로 출력한다. 이 문제는 #15649:N과 M(1)의 연장선 문제이다. #15649:N과 M(..
[백준 파이썬] #15649: N과 M(1) www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [정답] 1. 두 수를 입력받아 N,M을 정의한다. 2. 1부터 N까지의 자연수 중에서 고르는 문제니까 수 1~N을 list에 넣는다. 3. itertools 모듈의 permutations() 함수를 사용하여 중복을 제외한 순열을 구한다. 4. for문을 돌면서 중복을 제외한 순열을 차례대로 출력한다. itertools 모듈 - product() : 중복 순열 ex) product('ABC',repeat=2)..
[백준 파이썬] #2752: 세수정렬 www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net [정답1] 1. 숫자 세 개를 입력받아 리스트형태로 a에 넣어준다. 2. a 중에서 가장 작은 수를 min()함수를 통해 min_num에 넣어준다. 3. a 중에서 가장 큰 수를 max()함수를 통해 max_num에 넣어준다. 4. a 에서 min_num과 max_num을 remove하면 가운데 수만 남는다. 5. 가운데 수를 mid_num에 넣어준다. 6. min_num, mid_num, max_num을 출력한다. 너무 지저분하게 푼 것 같아 더 생각을 해보았다. [정답2] 1. 숫자 ..
[백준 파이썬] #2167: 2차원 배열의 합 www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net [오답] → 시간초과 우선 배열의 크기가 최대 300*300이므로 최대 90000개의 index를 가진다. 이 때 총 K번의 반복문을 실행해야 하는데, K의 범위는 1 ≤ K ≤ 10,000 이므로 최대 9억번의 연산을 해야한다. 그러므로 Python3는 시간초과가 발생한다. (Pypy3는 통과한다고 한다.) 시간초과가 되지 않으려면 dp를 이용하는 방법이 있다. dp는 아직 배우지..
[백준 파이썬] #1834: 나머지와 몫이 같은 수 www.acmicpc.net/problem/1834 1834번: 나머지와 몫이 같은 수 N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다. www.acmicpc.net [정답] 1. 구하고자 하는 수 N을 입력받는다. 2. N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합 ans을 정의한다. ex) N=5, 나머지와 몫이 같은 수는 5*1+1, 5*2+2, 5*3+3, 5*4+4. 즉 for문을 돌면서 N*i+i를 해주면 된다. 3. 1~N-1까지 for문을 돌면서 ans에 N*i+i을 더해준다. 4. ans을 출력한다.
[백준 파이썬] #1453: 피시방 알바 www.acmicpc.net/problem/1453 1453번: 피시방 알바 첫째 줄에 손님의 수 N이 주어진다. N은 100보다 작거나 같다. 둘째 줄에 손님이 들어오는 순서대로 각 손님이 앉고 싶어하는 자리가 입력으로 주어진다. www.acmicpc.net [정답] 1. 손님의 수를 N에 넣어준다. 2. 차있는 자리를 기록하기 위한 리스트 list와 거절당한 사람의 수 num을 정의한다. 3. 손님들이 원하는 자리를 입력받아 리스트 cus에 넣어준다. 4. 0~N-1만큼 for문을 돌면서 cus[i] 즉 손님이 원하는 자리가 list에 없을 경우 자리를 배정해주고 cus[i]를 list에 넣어준다. cus[i] 즉 손님이 원하는 자리가 list에 있을 경우 자리에 사람이 있어서 거절당하므로 num에 ..
[백준 파이썬] #1357: 뒤집힌 덧셈 https://www.acmicpc.net/problem/1357 1357번: 뒤집힌 덧셈 어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만드는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev( www.acmicpc.net [정답] 1. input().split()으로 숫자를 받아 list의 형태로 X,Y에 넣어준다. 2. X의 모든 자리수를 역순으로 만드는 함수인 Rev(X)를 정의한다. 3. 리턴할 문자 ans를 정의한다. 4. reverse()함수를 통해 X를 역순으로 바꾸어준다. 5. 그런다음 for문을 사용하여 리스트 X의 값을 문자열 ans에 차례대로 넣어준..
[백준 파이썬] #11653: 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net [정답] 1. 소인수분해할 대상을 입력받아 정수형으로 N에 넣는다. 2, N을 나눌 수인 a를 정의한다. 3. a가 N보다 커질 때까지 while문을 돌면서 만약 N이 a로 나누어떨어지면 a를 출력하고 N을 N/a로 업데이트한다. 4. 만약 N이 a로 나누어떨어지지 않으면 a에 1을 더해 다시 while문을 돈다. 이렇게 풀면 문제의 "결과를 오름차순으로 출력한다."를 신경쓰지 않고 코딩을 진행하면 된다.

티스토리툴바