목록알고리즘 (45)
while (1): study();
출처: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 이용한 최단경로 문제는 나오기만 하면 정말 땡큐인 문제인 듯합니다. 이 문제 역시 그래프의 노드 개수가 100개 이하이므로, 플로이드-워셜 알고리즘을 사용하여 손쉽게 해결할 수 있습니다. 플로이드-워셜 알고리즘에 대한 조금 더 상세한 설명은 다음 링크를 참조바랍니다. 링크: https://jcy1996.tistory.com/24?category=958980 플로이드..
풀이 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 1. 삽입: 특정한 위치에 하나의 문자를 삽입합니다. 2. 삭제: 특정한 위치에 있는 하나의 문자를 삭제합니다. 3. 교체: 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 조건 - 두 문자열 A와 B가 한 줄에 하나씩 주어집니다. - 각 문자열..
못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 됩니다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다. 입력 조건 - 첫째 줄에 n이 입력됩니다. (1
출처: https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전형적인 LIS(Longest Increasing sequence) 문제이다. 여기서는 내림차순으로 정렬한다고 했으므로 엄밀히 말하면 LDS(Longest Decreasing sequence) 문제이겠으나, 접근방법은 같다. 처음에는 다음과 같이 간단하게 접근해보려 했다. n = int(input()) array = list(map(int, input().split())) cnt..
출처: https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 고려할 조건이 많아서 생각보다 만점을 받기가 어려운 문제였습니다. 만약 상담 시작 일자에 기간을 더해서 '종료 일자'를 만들어 관리하면 코드 작성이 더 수월한 것 같습니다. 풀이에 있어 고려해야할 사항은 다음과 같습니다. 1) 종료 일자가 현재 고려 중인 상담 일자 이하인 경우에만 수익을 더할 수 있습니다. 예를 들어 현재 고려 중인 날짜가 5일의 상담인데, 3일 째의 상담의 종료 일자가 7일이라면, 3일째의 일자를 고려하지 않습니다. 2) 종료 일자가 퇴사 일자 이상이게 되면 고려하지 않습니다. 이것은 첫번째 상담날도 마찬가..
출처: https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 간단한 다이나믹 프로그래밍 문제입니다. 전체 소스코드는 다음과 같습니다. n = int(input()) tmp = [] for _ in range(n): tmp.append(list(map(int, input().split()))) array = [[0] * (n + 1)] for item in tmp: if len(item) < n: item += [0] * (n - len(item)) array.append([0] + item) table = [[0] * (..
n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 촐력하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에 테스트 케이스 T가 입력됩니다. (T는 1 이상 1000 이하) - 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (n, m은 1 이상 20 이하), 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다...
출처: https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 풀이1 문자열을 다루는 문제를 유독 많이 출제하는 카카오이지만 문자열 이진탐색은 덕분에 처음 접해본 듯 합니다. 처음에 접근했던 코드는 다음과 같습니다. def solution(words, queries): import re array = [] for q in queries: length = len(q) pos = 'pre' if q[-1] == '?' else 'post' keyword = re.sub('\?', '', q) cnt = 0 tmp_words = sorted([w for w in words if len(w) == len..
출처: 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아이디어를 떠올리기 쉽지 않은 이진탐색 문제이다. 공유기 간 최소거리를 정해놓고 몇 개의 공유기가 설치될 수 있는지 확인한다. 설치할 수 있는 공유기의 개수를 기준삼아 설치해야 하는 공유기의 개수보다 적으면 최소거리를 적게 잡는다. 반대의 경우엔 이미 설치해야 하는 만큼 설치가 가능하다는 의미이므로 정답을 저장하되, 최대거리를 구하는 문제이므로 더 큰 거..
문제 보기 ↓ 더보기 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때, a[2] = 2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘ㅇ르 설계하지 않으면 '시간 초과' 판정을 받습니다. 입력 조건 첫째 줄에 N이 입력됩니다. (1