본문 바로가기

Algorithm705

[수학/재귀] 백준 11729 하노이 탑 이동 순서 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 2. 문제 풀이 1) 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다 2) 원판은 위에서부터 꺼내, 1개씩 이동한다 재귀 문제의 대명사, '하노이탑 문제'입니다. 목표 지점까지 '맨 밑의 원판'부터 하나씩 재귀적으로 옮겨야 합니다. 원판이 3개일 때를 예시로 들어보겠습니다. 하노이탑의 규칙에 따라, 목표 막대로 원판을 옮기려면 맨 아랫 원판부터 차근차근 쌓아야 합니다. 그러기 위해서 보조막대.. 2022. 6. 25.
[브루트포스/수학] 백준 1057 토너먼트 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 2. 문제 풀이 계속 이긴다는 보장 하에, 두 사람이 매칭되는 라운드를 구하는 문제입니다. 예를 들어, 2번과 4번은 2라운드에서 만나게 됩니다. 브루트포스 방식으로 완전탐색해서 풀려면, 위와 같이 완전 이진트리를 구성하고 일일이 탐색하면 됩니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N, a, b = map(int, input().split()) # 토너먼트 cnt = .. 2022. 6. 24.
[이진/이분탐색] 백준 2512 예산 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 2. 문제 풀이 제한된 예산 내에서, 줄 수 있는 최대의 예산을 구하는 문제입니다. 2022.02.10 - [Algorithm] - [정렬/탐색] 백준 2805 나무 자르기 - Python [정렬/탐색] 백준 2805 나무 자르기 - Python [ Contents ] 1. 문제 (링크 참조) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1.. 2022. 6. 23.
[탐색/BFS] 백준 4963 섬의 개수 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2. 문제 풀이 섬의 개수를 세는 문제입니다. 2022.02.23 - [Algorithm] - [탐색/BFS] 백준 1012 유기농 배추 - Python [탐색/BFS] 백준 1012 유기농 배추 - Python [ Contents ] 1. 문제 (링크 참조) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부.. 2022. 6. 22.
[정렬/탐색] 백준 11931 수 정렬하기 4 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 문제 풀이 숫자를 입력받고, 내림차순으로 정렬 후 출력하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = int(input()) numlist = [] for _ in range(N): numlist.append(int(input())) # 정렬 numlist.sort(reverse=True) # 출력 for i in numlist: .. 2022. 6. 21.
[자료구조/해시] 백준 7785 회사에 있는 사람 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 2. 문제 풀이 회사에 있는 사람을 역사전순으로 출력하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = int(input()) company = [] for _ in range(N): man, state = input().rstrip().split() if state == 'enter': company.append(.. 2022. 6. 20.
[Greedy/그리디] 백준 2217 로프 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 문제 풀이 각 로프가 버틸 수 있는 최대 중량을 구하는 문제입니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안대를 끼고 있습니다. 이를 '차안대' 라고 합니다. 말의 눈은 양 옆에 달려 있어 시야가 '.. 2022. 6. 19.
[구현/수학] 백준 10974 모든 순열 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 순열을 구하는 문제입니다. itertools.permutations(lst, n): lst에서 n개를 뽑는 순열 파이썬의 itertools 라이브러리를 이용해서 순열을 구할 수 있습니다. 라이브러리를 이용하지 않으려면, dfs와 백트래킹을 이용해야 합니다. 3. 코드 from itertools import permutations # 입력 N = int(input()) # 순열 구하기 res = permutations(range(1, N+1), N) # 출력 for perm in res: f.. 2022. 6. 18.
[구현/수학] 백준 2702 초6 수학 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2702번: 초6 수학 첫째 줄에 테스트 케이스의 개수 T(1 2022. 6. 17.

티스토리툴바