1. 동적 계획법(DP)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 2. DP vs 분할 정복 DP 분할 정복 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨 동일한 부분 문제가 반복적으로 계산되지 X 최적 부분 구조를 가질 때 사용 O (큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황) 3. DP의 2가지 방식 1. Top-Down(하향식) - 재귀 이용 - 메모이제이션 기법 활용 - 한 번 계산한 결과를 메모리 공간에 메모하는 기법(캐싱) - 다이나믹 프로그래밍 구현 기법(하..
[이코테] 문제3 - 두 배열의 원소 교체(182p) (한줄평) 정렬만 할 줄 안다면 쉽게 해결할 수 있는 문제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 배열의 크기: n, swap 가능 횟수: k 라고 주어졌을 떄 A, B 2가지 배열의 원소를 각각 하나씩 swap하여 만들 수 있는 A의 원소 합의 최댓값을 구하는 문제다. A, B의 원소를 서로 바꿔 A의 원소 합이 최댓값이 되게 하려면 단순하게 A의 작은 수와 B의 큰수를 바꾸는 것을 최대 K번 반복하면 된다. 그러므로 A는 오름차순 정렬, B는 내림차순 정렬하여 0번부터 (k - 1)번 까지 값을 swap하면 된다. 여기서 중요 포인트는 A, B를 각각 정렬 해야함을 떠올리는 것이다. 단, A의 원소가 B의 원소보다 크거나 같으면 굳이 바..
[이코테] 문제1 - 위에서 아래로(178p) (한줄평) 정렬 알고리즘 예제 문제 수준으로 여러가지 정렬 알고리즘을 연습해볼 수 있는 문제! 퀵 정렬만 조금 더 연습해보면 좋을 듯! 이 문제는 n개의 수가 주어지고 내림차순 정렬을 하는 문제다. 수의 개수가 500개 이하로 매우 적고 모든 수는 1이상 100,000이하로 어떠한 정렬 알고리즘을 사용해도 해결할 수 있다. (풀이1) 파이썬 기본 정렬 라이브러리 이용 풀이 시간: 3분 이내 1) 문제 해결 아이디어 가장 단순한 방법으로 sorted()를 이용하여 해결하였다. 2) 소스코드 n = int(input()) arr = [int(input()) for _ in range(n)] # n개의 수 # 1. 정렬 라이브러리(내림차순) #print(*sort..
& and | or ^ xor ~ not 6059 - 비트단위로 NOT 하여 출력하기 a = int(input()) print(~a)#비트 not 6060 - 비트단위로 AND 하여 출력하기 a, b = map(int, input().split()) print(a & b) #비트 and 연산 6061 - 비트단위로 OR 하여 출력하기 a, b = map(int, input().split()) print(a|b) # 비트 or 연산 6062 - 비트단위로 XOR 하여 출력하기 a, b = map(int, input().split()) print(a^b) #비트 xor 연산
