Coding Test/Baekjoon
-
[파이썬/Python] 백준 2805번: 나무 자르기 풀이Coding Test/Baekjoon 2022. 8. 29. 14:33
문제 출처: https://www.acmicpc.net/problem/2805 풀이 방법 시간 초과를 막기 위해 효율적으로 코드를 짜야 한다. 나는 다음 세 방법을 모두 사용하였다. 1. 이진탐색 2. input 함수 대신 sys.stdin.readin 사용 3. 얻을 수 있는 나무 높이를 구할 때 불필요한 덧셈 제외 3의 경우, for문을 돌면서 나무 높이를 구할 때 기준높이 이하의 나무가 나오는 순간 반복문을 종료하면 된다. for문 없이 sum으로 계산하도록 했을 때에는 시간초과가 되었다. 코드
-
[백준/파이썬] 1874번: 스택 수열 풀이Coding Test/Baekjoon 2022. 8. 26. 20:30
문제 풀이 문제 내용을 이해를 못해서 다른 분들의 풀이를 보고 이해했다. 아래의 글에 매우 친절하게 설명되어 있다. https://assaeunji.github.io/python/2020-05-04-bj1874/ [백준] 1874번 스택 수열 파이썬 풀이 난이도: 하 풀이시간: 20분 분류: 스택 링크: [link] assaeunji.github.io 코드 나는 반복문 변수 업데이트나 출력 방식만 조금 더 간단하게 바꾸었는데 이건 코드 취향 차이일 뿐 중요한 변경은 아니다.
-
[백준/파이썬] 1920번: 수 찾기Coding Test/Baekjoon 2022. 8. 26. 16:19
풀이 방법 binary search를 구현했는데 index slicing한 리스트를 넘기다보니 부분부분 계속 복사해서 그런지 시간초과가 났다. 그런데 dict, set 자료형은 시간복잡도O(1)이라는 걸 알게 되었다! 리스트를 dict 또는 set에 넣어서 검색결과를 출력하도록 하면 된다. 코드 참고 https://chancoding.tistory.com/44 [Python] 백준 1920번 수 찾기 - 두가지 풀이:이분탐색과 자료형 수 찾기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 47591 13352 8683 28.370% 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로. chancoding.t..
-
[백준/파이썬] 2164번: 카드2 풀이Coding Test/Baekjoon 2022. 8. 25. 13:05
풀이 방법 1 ... 1 2 ... 2 = (2-1)*2 3 ... 2 = (3-2)*2 4 ... 4 = (4-2)*2 5 ... 2 = (5-2*2)*2 6 ... 4 = (6-2*2)*2 7 ... 6 = (7-2*2)*2 8 ... 8 = (8-2*2)*2 9 ... 2 = (9-2*2*2)*2 10 ... 4 = (10-2*2*2)*2 n>1이 입력으로 주어졌을 때, (n - n보다 작은 2의 거듭제곱)*2를 출력하면 된다. n=1의 경우 n을 출력한다. 일반 list에서 pop&append 사용 시 시간초과가 난다. 코드
-
[백준/Python] 1676번: 팩토리얼 0의 개수 풀이Coding Test/Baekjoon 2022. 8. 23. 10:04
풀이 방법 10! = 3,628,800 -> 2 3! = 6 -> 0 반복적으로 5로 나누어서 인자들이 가진 5의 개수의 총합을 구한다. ex) 1000 // 5 = 200 200 // 5 = 40 40 // 5 = 8 8 // 5 = 1 1 // 5 = 0 (종료) 200 + 40 + 8 + 1 + 0 = 249 코드 참고: https://mococoding.tistory.com/14 [파이썬] 백준 1676번: 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 방법1: math.factorial을 통.. mo..
-
[백준/Python] 9375번: 패션왕 신해빈 풀이Coding Test/Baekjoon 2022. 8. 22. 19:05
풀이 방법 face eyewear ... type k X(안 입음) X ... X 1번 1번 ... 1번 2번 2번 ... 2번 ... ... ... ... y1번 y2번 ... yk번 위에서 옷의 종류별로 입지 않거나 1, 2, 3, ..., yk번 중에서 선택할 수 있다. face의 경우 1 + y1가지 선택지가 있다. 따라서 각 종류별로 가능한 모든 경우의 수를 구한 뒤 알몸 상태인(모두 X) 경우의 수 1을 제외하면 된다: (1 + y1) * (1 + y2) * ... * (1 + yk) - 1 코드
-
[백준/Python] 1934번: 최소공배수 풀이Coding Test/Baekjoon 2022. 8. 21. 11:36
풀이 방법 방법 1) a*i (i = 1,2,3,4, ...)%b == 0 인지 검사한다: 시간초과 ☞ 방법 2로 방법 2) 두 수의 최대공약수 GCD를 구하여 GCD*(a//GCD)*(b//GCD)를 계산한다. 18과 24의 최대공약수는 6, 최소공배수는 72이다. 72 == 6 * (18//6) * (24//6) == 6 * 3 * 4 이므로 방법 2)로 계산하면 효율적으로 최소공배수를 구하여 시간을 단축할 수 있다. 코드