미쳐 복습해 기억안나 1. Dynamic Programming 동적 프로그래밍 작은 부분문제들부터 모두 해결한 후 부분 문제들의 해를 이용해 큰 문제를 해결하는 방법(부분 문제들 사이에 의존적) Bottom-up 한 번 구한 값은 절대 바뀌지 않고, 여러번 사용될수 있음 최적성원칙 Principle of Optimality : 최종해는 최적의 부분해들로 이루어져 있어서 최종해 안에 최적의 부분해들이 포함됨 최적성원칙 Principle of Optimality 를 만족하는 문제에서만 동적 프로그래밍 사용 가능 최적화 문제 : 주어진 문제에 대하여 가장 최적인 해답을 찾는 문제 shortest path문제 - all pairs shortest paths 문제(alll to all 알고리즘) 각 정점에서 다른..
DSA
순차검색 2. 분할정복 이분검색 합병정렬 : 다 하나짜리로 쪼개고 하나씩 합치며 정렬 QuickSort 빠른정렬. 분할 교환 정렬 : 기준값(pivot, 보통 맨 첫번째 값)을 정함. 남은 것들 양쪽ij인덱스로 좁히면서 기준값보다 큰거작은거 자리바꾸고 마지막에 j랑 기준값이랑 자리바꿈 3. Greedy 알고리즘 순서 선정 selection 적정성 점검 feasibility check : 조건에 만족하는가 해답 점검 solution check : 최적의 해인가 - 증명은 어려워도 반례가 없는지 마지막에 확인해보는 절차 권장 Fractional Knapsack problem : 단위무게당 profit이 큰 것 부터 넣는 것이 최적 0-1 Knapsack problem Two-way Optimal Merge ..
백준 9372번 문제 상근이의 여행 트리구조를 활용하는 문제이다. https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 풀이 비행기가 연결리스트임. 모든 비행기가 연결되어있으므로 그냥 방문해야 하는 나라 - 1 하면 됨 해답 코드 Python ## 백준 9372 상근이의 여행 트리 from sys import stdin #입력 T = int(stdin.readline()) #중첩 리스트 두 개 - 각 케이스..
백준 1269번 문제 대칭 차집합 트리 문제이다. https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 문제 풀이 파이썬에는 집합 자료형이 있고 관련 메서드들을 활용해서 너무 쉽게 풀 수 있었다. 해답 코드 Python ## 백준 1269 대칭 차집합 트리 # 집합 자료형 사용하지 않고도 풀어보기 from sys import stdin NA, NB = map(int, stdin.readline().split()) #집합 자료형 set() A =..
백준 16466번 문제 콘서트 우선순위 큐 문제이다. https://www.acmicpc.net/problem/16466 16466번: 콘서트 HCPC (Hanyang Completely Perfect Celebrity)는 한양대학교 최고의 가수에게 주어지는 칭호이다. 한양대학교는 매년 최고의 HCPC를 선발한다. HCPC가 되기란 여간 어려운 게 아니다. 매일 아침 날달걀을 까먹 www.acmicpc.net 문제 풀이 입력받은 데이터를 1 2 4 7 8 이라 하면 입력과 크기가 같은 배열인 1 2 3 4 5 를 활용한다. 1 2 4 7 8 1 2 3 4 5 두 배열의 각 원소를 순서대로 비교해나간다. 서로 값이 다를 경우 해당 순서의 자리가 빈 것! 다른 값이 없을 경우 마지막 자리보다 한 자리 뒤가 ..
백준 2959번 문제 거북이 정렬 문제 https://www.acmicpc.net/problem/2959 2959번: 거북이 첫째 줄에 거북이가 생각한 네 양의 정수 A, B, C, D가 주어진다. (0 세 번째 수 2. 두 번째 수 < 네 번째 수 여야 한다. 주어진 수로 만들 수 있는 직사각형 넓이 ..
백준 2720번 문제 세탁소 사장 동혁 greedy 알고리즘 문제 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 문제 풀이 중고등학생 때 풀던 동적 최소 개수 문제랑 똑같다. 괜히 영어동전으로 만들어놨다고 쫄 필요 없다. 거슬러줘야 하는 값을 m에 배열로 담고 현재 m을 coin의 큰 값부터 나누어 몫은 출력할 문자열에 추가, 나머지는 원래 m에 다시 저장하기를 동전 종류 수 만큼 반복한다. 해답 코드 Python #백준 2720 세탁소 사장 동혁 greedy from sys import stdin #입력, 사용..
백준 10162번 문제 전자레인지 greedy 알고리즘 문제 https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 문제 풀이 어렵지 않은 문제. 중고등학생 때 풀던 동전 최소 개수 문제랑 똑같다 출력조건에 따라 1의 자리가 0이 아니면 주어진 숫자로는 만들 수 없는 수이니 -1을 출력하고 1의 자리가 0이면 T를 큰 값부터 나누어 몫은 카운트에 저장하고 나머지는 T에 다시 저장을 반복한다. 해답 코드 Python # 백준 10162 전자레인..
백준 2231번 문제 분해합 완전탐색(브루트포스) 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 풀이 완전 탐색 - 어떤 수의 생성자는 원래 수보다 무조건 작으므로 0부터 N-1까지 다 계산해 봄 부분 코드 설명 isum = sum(list(map(int, str(i)))) 숫자 i를 string으로 형변환한다. 파이썬의 string은 배열처럼 사용할 수 있다. 한 글자씩 나눠져서 배열이 됨 list(m..
백준 2798번 문제 블랙잭 완전탐색(브루트포스) 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 풀이 완전탐색 : 가능한 모든 경우의 수를 탐색하는 방법 N개의 수 중 3개를 비복원추출하는 모든 경우의 수를 탐색한다. 탐색하여 sum 값이 M보다 작거나 같은 값들 중 가장 큰 값을 구한다. 해답 코드 Python #백준 2798 블랙잭 #입력받는 방법 한 번 정리하기 #문제똑바로 읽기..^^ :
백준 15829번 문제 Hashing 해싱 50점 풀이와 100점 풀이가 있는 문제이다. 둘 다 적겠다 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 100점 문제 풀이 알파벳을 의미하는 숫자 반환 함수 - 유니코드 활용 ord() 입력된 알파벳을 숫자로 만들고 해시값 계산 100점 해답 코드 Python #백준 15829 Hashing - 100점 from sys import stdin #데이터 입력 L = int(stdin.readlin..
백준 12605번 문제 단어순서 뒤집기 https://www.acmicpc.net/problem/12605 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 스택을 활용하는 문제 문제풀이 데이터 입력받을 배열과 결과물 넣을 배열 선언 데이터 하나씩 돌면서 스페이스바 기준으로 단어를 잘라 새 배열 slist를 만듦. slist의 값을 역순으로, 준비된 temp에 넣고 temp 하나가 다 만들어지면, 결과물 result에 저장. 해답 코드 python #12605 from sys import stdin #전체 개수..
백준 2161번 문제 카드1 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 큐를 사용하는 문제이다. 문제 풀이 전체 갯수 입력받고 데이터 입력받을 배열과 결과값 넣을 배열 생성 throw : 카드를 버릴 차례라면 True, 뒤로 넣을 차례라면 False를 담는 변수 데이터 배열 data에 값이 계속 추가되므로 data의 현재 길이를 이용해 data배열이 끝날때까지 반복하도록 함 해답 코드 python #2161 #comm. 파이썬 que문제는..
백준 17608번 문제 https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 스택을 활용하는 문제라고 함 문제풀이 전체 개수와 데이터 입력받고 데이터 뒤에서부터 돌면서 현재까지 가장 큰 값은 curBig에 저장. curBig보다 크면 count에 +1하고 curBig값으로 업데이트한다. 해답 코드 python #17608 from sys import stdin #전체 개수와 데이터 입력받 n = int(input()) data = [0]*n for i i..
알고리즘 공부, 문제풀이, 개념 정리!
