PS문제풀이 (15) 썸네일형 리스트형 하노이탑에 대하여 매우 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 = .. [그리디 알고리즘]1700-멀티탭 스케줄링 먼저 멀티탭 스케줄링을 가장 간단한 언어로 요약하면, n구의 멀티탭에 여러가지 전자제품을 사용하려는데(k개의 전자제품 사용 스케줄), 빼는 횟수를 최소화 하고 싶다는 것이다. 직관적으로 다음 아이디어가 떠오른다. "그러면 그냥 다음에 나올 빈도수가 적은 것 먼저 뽑으면 되는거 아니야?" 그렇게 코딩을 시행해봤고, 광탈했다. 반례는 어렵지 않게 찾을 수 있었다. "가장 늦게 나오는 플러그, 또는 절대 안나올 플러그를 먼저 뽑으면?" 이렇게 아이디어를 잡으면 다음 코드가 나온다. import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) con = list(map(int, input().rstrip().split())) st.. [스택심화]17298-오큰수 오큰수? 육큰수는요? 깔깔깔~ 1. 아이디어 스택 관련하여 유형을 익힐 수 있는 오큰수 문제이다. 오큰수 문제는 간단한 아이디어로 시작된다. 느낌상으로만 보자면 동적 계획법과 비슷한 느낌도 존재한다. 뒤쪽부터 시작하여 스택에 추가한 뒤, pop()해주면서 가장 오른쪽에 있는 값을 찾으면 되지 않을까? 2. 정리 3. 코드 import sys input = sys.stdin.readline print = sys.stdout.write n = int(input().rstrip()) num = list(map(int, input().rstrip().split())) stack = [] value = [-1]*(n+1) for i in range(n-1, -1, -1): while True: if len(sta.. [스택 심화]9935-문자열 폭발 단계별로 풀어보기 스택 2에 있는 문자열 폭발이다. 문제 조건에서 알 수 있듯이, 폭발 문자열이 사라질 때까지 폭발 문자열을 삭제해주면 된다. 1. 아이디어 python replace를 쓰니까 광탈... 직접 replace를 구현해줄 방법이 있을까? ->스택사용! 파이썬은 문자열 합치기 기능(join)이 있으므로 구현하기 간단하다. 2. 코드 s = input() boom = input() stack = [] m = len(boom) for i in s: stack.append(i) while stack and "".join(stack[-1*m:]) == boom: if "".join(stack[-1*m:]) == boom: for j in range(m): stack.pop() if stack: pri.. 이전 1 2 다음
