전체 글 (23) 썸네일형 리스트형 하노이탑에 대하여 매우 standard한 하노이탑을 이해하기란 나의 머리로 쉽지 않았다. 솔직히 상상이 안갔던 것 같다. 나는 개인적으로 DP를 머리보단 유형으로 푸는 타입이었기에 이제는 DP를 생각하면서 푸는 페러다임을 마련해야함을 느꼈다. 가장 DP와 재귀의 기초라는 하노이탑을 풀 수 없는 골 1이라니, 수치스럽기도 하고 발전해야겠다는 강한 동기부여가 들었다. 하노이탑은 간단히 1번의 봉에 있는 원판을 크기가 큰 것이 밑으로 가도록 배열해 3번으로 모두 옮기면 된다. 다음은 원판 3개의 예시이고, 초기 상태에 1번 봉의 최상단에 있는 원판이 숫자 1번 원판이다. 우리가 원판을 옮기려면 어떻게 해야할까? 문제를 분해해보자 원판 n-1개를 어느 한 지점에 몰아둔 뒤, 원판 하나만 옮기는 방식으로 코딩을 진행하면 되지 않을.. 백준 2162 선분그룹(python) https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 나는 이 문제를 풀기 전에 CCW 알고리즘의 응용 버전인 골드 2 문제, 선분교차 2를 풀었기 때문에 그를 이용하여 쉽게 풀 수 있었다. 다음 문제의 아이디어는 다음과 같다. 1.CCW 알고리즘(벡터의 외적)을 이용하여 많은 조건 분기로 선분 교차를 판정하는 함수를 정의한다. 2.Union-Find 자료구조를 활용하여 선분을 통합한다. 3.그룹의 수와 가장 많은 .. 백준 1647:도시 분할 계획(python) 크루스칼 알고리즘 크루스칼 알고리즘의 구동 과정을 설명해보겠다. 1. 간선을 가중치 기준으로 오름차순 정렬한다. 2. 간선을 정렬한 순으로 하나하나 추가해준다. 3. 상호 배타적 집합 자료구조(Union-Find)를 사용하여 사이클을 판별한다. 크루스칼의 구현은 위와 같이 간단하다. 그리고 도시 분할 계획 문제에서는 도시를 분할하여야 하므로, 가장 큰 비용의 마지막 간선을 제거해준다. 코드는 다음과 같다. import sys input = sys.stdin.readline print = sys.stdout.write n, m = map(int, input().rstrip().split()) adj = []# tuple을 이용해 (가중치, 연결된 정점1, 연결된 정점2) 저장 def min(a, b): if a < b: r.. 백준 27172-수 나누기 게임(python) (에라토스테네스 아이디어 응용) 에라토스테네스의 체의 아이디어를 응용하면 풀 수 있었다. import sys input = sys.stdin.readline print = sys.stdout.write n = int(input().rstrip()) num = list(map(int, input().rstrip().split())) m = max(num) point = [0 for i in range(m+1)] visit = [0 for i in range(m+1)] for i in num: visit[i] = 1 for i in num: j = i k = 2 while j*k 백준 2623 음악프로그램 위상정렬 알고리즘 from collections import deque n, m = map(int, input().split()) arry = [[] for i in range(m)] for i in range(m): arry[i] = list(map(int, input().split())) arry[i].pop(0) adj = [[] for i in range(n+1)] pan = 0 for i in range(m): for j in range(len(arry[i])): for k in range(j): if arry[i][j] not in adj[arry[i][k]]: adj[arry[i][k]].append(arry[i][j]) queue = deque() stack = deque() temp = 0 visit = .. 인생은 그리디 알고리즘이다. 그리디 알고리즘을 배우면서 인생이 그리디 알고리즘과 닮았다는 사실을 느끼고는 한다. 항상 최적의 해를 찾고, 그 최적의 해를 찾는 방법의 기준을 잘 세워야하기 때문이다. 인생이라는 컴퓨터 프로그램은 "이후 미래에 편익이 큰 것"을 정렬기준으로 삼는 그리디 알고리즘이 아닐까? 그것이 최적의 해를 찾는 방법임을 알았으면, O(NlogN)이라는 효율적인 방식으로 정렬을 수행하고 O(N)의 수행을 해야하는데 나는 NlogN도 귀찮은 것 같다. 여기서 O(NlogN)은 계획이 아닐까 한다. 계획적으로 공부를 하고 계획적으로 운동을 한다면 미래에 그리디 알고리즘에 대한 성과를 얻을 수 있을 것이다. [그리디] 유형분석, 코딩전략 https://www.acmicpc.net/problem/22864 22864번: 피로도 첫 번째 줄에 네 정수 $A$, $B$, $C$, $M$이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다. www.acmicpc.net 피로도, 난이도: 브론즈 2 그리디보다는 구현에 가까운 유형, 반복문을 통해 가장 큰 값을 선택한다. https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 신입사원, 난이도: 실버1 실버 1이지만 상.. [그리디 알고리즘]1700-멀티탭 스케줄링 먼저 멀티탭 스케줄링을 가장 간단한 언어로 요약하면, n구의 멀티탭에 여러가지 전자제품을 사용하려는데(k개의 전자제품 사용 스케줄), 빼는 횟수를 최소화 하고 싶다는 것이다. 직관적으로 다음 아이디어가 떠오른다. "그러면 그냥 다음에 나올 빈도수가 적은 것 먼저 뽑으면 되는거 아니야?" 그렇게 코딩을 시행해봤고, 광탈했다. 반례는 어렵지 않게 찾을 수 있었다. "가장 늦게 나오는 플러그, 또는 절대 안나올 플러그를 먼저 뽑으면?" 이렇게 아이디어를 잡으면 다음 코드가 나온다. import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) con = list(map(int, input().rstrip().split())) st.. 이전 1 2 3 다음
