9시 24분

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net t = int(input()) for _ in range(0,t): n = int(input()) zero = [0] * (n+2) one = [0] * (n+2) for i in range(0, n+1): if i == 0: zero[i] = 1 elif i == 1: one[i] = 1 else: zero[i] = zero[i-1] + zero[i-2] one[i] = one[i-1] + one[i-2] print(zero[n], one[n]) 앞선 문제와 달리, if-elif-else로 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net def makeOne(n): dp = [0] * (n + 1) for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i], 1 + dp[i//3]) if i % 2 == 0: dp[i] = min(dp[i], 1 + dp[i//2]) return dp[n] n = int(input()) print(makeOne(n)) DP는 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식이다. 결국 1 빼기, 2 나누기, 3 나누기라는 세 가..

https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr def solution(s): answer = -1 stack = [0] for i in range(len(s)): top = stack[-1] if(top == s[i]): stack.pop() else: stack.append(s[i]) stack.remove(0) if not stack: answer = 1 else: answer = 0 ret..

https://mk28.tistory.com/193 참고 1) [1, min(a, b)] 범위에서 두 수 모두의 약수가 되는 값 중 최댓값을 구하는 방법 시간복잡도 O(min(a,b)), 시간초과가 발생하기 쉬움 2) 역순 탐색 - [1, min(a, b)]부터 1까지 역순으로 탐색하여 가장 처음 발견된 공약수가 결국 최대 공약수가 됨 1번 방법을 역순으로 진행하고, 공약수가 발견되면 break하는 방법으로 구현 1번보다는 빠르겠지만 최악의 경우 모든 수를 검사함 1번과 동일한 시간 복잡도 3) 유클리드 호제법 f(a, b) = gcd(a, b)라 하자. 이 때 a mod b = 0 이라면, f(a, b) = b임이 자명. 이 때 a mod b이 0이 아닌 경우, f(a, b) = f(b, a mod b..

'이것이 취업을 위한 코딩 테스트다' 참고 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘 : DFS/BFS 스택과 큐에 대한 이햐가 전제되어야 함 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 삽입(Push) / 삭제(Pop) 두 핵심적인 함수로 구성 오버플로(가득 찬 상태에서 삽입 연산 수행) / 언더플로(전혀 들어 있지 않은 상태에서 삭제 연산 수행)도 고민해주어야 함 스택 : 선입후출 구조 stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append..

'이것이 취업을 위한 코딩테스트다' 참고 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 ㄴ 이 책에선 완전 탐색, 시뮬레이션 유형을 묶어 다루고 있음 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 변수의 표현 범위 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. > 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 괜찮다. 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자. 리스트 크기 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자. 리스트를 여러 개 선언하고, 그 중 크..

'이것이 취업을 위한 코딩 테스트다' 참고 그리디 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 [ 92쪽 큰 수의 법칙 ] My Code n, m, k = map(int, input().split()) num = list(map(int, input().split())) num.sort(reverse=True) # 4 3 2 1 print(num) result = 0 for i in range(m): if (i+1)%(k+1)==0: result += num[1] else: result += num[0] 책 속 Code # N, M, K를 공백을 기준으로 구분하여 입력 받기 n, m, k = map(int, input().split()) # N개의 수를 공백을 기준으로 구분하여 입력 받기 ..

'이것이 취업을 위한 코딩 테스트다' 참고 리스트 컴프리헨션 arr = [i for i in range(20) if i % 2 == 1] print(arr) // [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 언더바(_)의 역할 for _ in range(5): print("Hello World") 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 사용 N*M 크기의 2차원 리스트 초기화 n = 3 m = 4 arr = [[0]*m for _ in range(n)] // [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 리스트 관련 메서드 append() sort() reverse() insert() - 시간 복잡도 O(N), 동작이 느리므로 남발하면..