알고리즘300 35

[백준] 10872 팩토리얼, 10870 피보나치 수 5

10872번: 팩토리얼 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 팩토리얼은 3가지 방법으로 풀었다. 재귀 함수로 한번, 반복문을 이용해 한번, 파이썬 자체적인 내장함수를 이용해 한번. 내장함수를 쓰는 방법이 제일 오래 걸렸다. # 10872 팩토리얼 # 첫 번째 방법: 재귀함수 def fact(N): if N > 0: return N * fact(N-1) else: return 1 N = int(input()) ret = fact(N) print(ret) # 두 번째 방법 : 반복문 활용 N = int(input()) sum = 1 for i in range(N, 0, -1): sum *= i prin..

[백준] 1929. 소수 구하기

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 첫번째 시도: 이전처럼 2부터 n-1까지 모든 수로 n을 나누며 소수를 판별하는 방법을 사용했는데 시간초과가 났다. 두번째 시도: 아래 블로그 글을 참고해 제곱근을 활용하여 2부터 n-1이 아니라 2부터 제곱근까지로 나누어 소수를 판별하도록 알고리즘을 짰다. [백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python) 츄르사려고 코딩하는 코집사입니다. 1. [백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python) 1) 문제번호 : 1929번 2) 문제 출처 https://ww..

[백준] 1978. 소수 찾기

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net flag를 사용해서 주어진 숫자들이 소수인지 여부를 확인하면 되는 문제였다. 테스트케이스가 많지 않아서 그냥 2부터 a까지 모든 숫자들로 다 나눠보아도 시간이 그렇게 많이 들지 않았다. (하지만 뒤로 갈수록 테스트 케이스가 많아져서 이 방법대로 풀 수는 없었다. 그래서 제곱근이나 에라토스테네스의 체를 찾아보고 적용해야만 했다.) # 1978 소수 찾기 N = int(input()) arr = list(map(int, input().split())) cnt = 0 for a in arr: flag = False if a == 1: ..

[백준] 2775. 부녀회장이 될테야

2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 이 문제는 n과 k가 1부터 14 사이의 작은 수여서 O(n2)의 시간복잡도가 나오더라도 이중 반복문을 사용해 풀었다. # 2775 부녀회장이 될테야 T = int(input()) for tc in range(1, T+1): k = int(input()) n = int(input()) house = [[0 for _ in range(n+1)] for z in range(k+1)] # 0층의 room들은 1, 2, 3 순으로 사람이 들어가 있다. for r in range(n+1): house[0][r]..

[백준] 10250. ACM 호텔

10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 이 문제는 쉽게 접근해서 풀었지만, 중간에 미처 찾지 못한 반례때문에 계속 틀리다가 반례를 알아내서 맞춘 문제이다. 처음에는 이렇게 flag 없이 풀었다. # 10250 ACM호텔 T = int(input()) for tc in range(1, T+1): H, W, N = map(int, input().split()) cnt = 1 for w in range(1, W+1): for h in range(1, H+1): if cnt == N: print(..

[백준] 1193. 분수찾기

1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 이 문제는 처음에 dfs로 방향 이동하는 걸로 풀었다가 시간 초과가 나서 인터넷으로 더 간단한 풀이방법을 검색해서 다시 풀었다. 우선 아래가 내가 처음에 dfs 활용해서 푼 버전. 정답은 잘 나왔는데, 재귀를 사용하는 이상 어떻게 해도 시간 초과가 나올 수밖에 없는 구조였다. return을 조건문과 반복문 중간중간에 넣어 빠르게 빠져나오게 해도 어쩔 수 없었다. # 1193 분수 찾기 def find_num(y, x, cnt, str): dy = [1, -1] dx = [-1, 1] if cnt == N: print(arr[y][x], end='') return # case [0] 좌하향 # ..

[백준] 2292. 벌집

2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 이 문제는 총 3번 시도했다. 1차 시도는 재귀함수로 풀었다가, RecursionError가 났고 2차 시도는 시간오류라고 표시됐는데, 다시 뜯어보니 아예 잘못 짠 거였다. 그렇게 3차 시도에서 통과했다. 우선, 1차 시도는 이렇게 재귀 함수로 짜보았다. 예시 입출력은 통과했는데, Recursion Error가 나버렸다. # 2292 벌집 # 규칙성을 따져보면 벌집의 숫자는 6의 배수로 늘어난다. # 가령 1은 6의 0제곱, 1을 둘러싼 원은 2-7(6개), 그 다음 원..

[백준] 1712. 손익분기점

1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 이 문제를 푸는 데 2번을 틀려서, 3번 코드를 짰다! 각각 다른 이유로 틀렸기 때문에, '아, 이런 것도 미리 생각하고 짰어야 했는데' 라는 생각의 연속을 겪었다. (하지만 나는 AI가 아니라 인간이기에... 디버거를 돌리지 않으면 잘 모른다...ㅋㅋㅋㅋㅋ) 우선 첫번째 시도는 이러했다. 판매대수를 n이라고 설정해두고, 문제를 풀었는데 '손익분기점이 나지 않을 때는 -1을 출력해야 한다.'는 부분을 읽으며 어떻게 하면 반복문을 돌리기 전에 손익분기점을 도달할 수 있..

[백준] 1316. 그룹 단어 체커

1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 오늘은 너무 코앞으로 다가온 정처기 시험 준비때문에 2문제만 풀었는데, 이 문제가 시간을 많이 잡아먹었다. 먼저 풀었던 '2941.크로아티아 알파벳' 문제와 비슷한데, 미리 길이가 정해져있지 않아서 슬라이싱은 활용할 수 없었다. 그래서 연속된 숫자가 어디까지 이어지나 확인해보고자, 투 포인터 알고리즘을 이용해서 풀어보려고 했다. # 1316 그룹 단어 체커 # 이거 dfs로도 풀 수 있을 것 같긴 한데, # 투 포인터로 풀어보자...