while (1): study();

출처: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 암호의 순서는 언제나 오름차순 정렬로 고정되어 있으므로, 순서에 대해 고려하지 않아도 됩니다. 따라서 조합(Combination)을 이용하여 간단하게 문제를 풀 수 있습니다. 파이썬 내장 라이브러리 중 하나인 itertools의 combinations 함수를 사용하면 됩니다. 소스코드는 다음과 같습니다. from itertools import combinations l, c = list(map(..

출처: https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 최근 바빴던지라 문제풀이를 전혀 못했었는데, 오랜만에 한번 풀어봤습니다. 오랜만에 푼 게 삼성전자 공채 기출문제라니 쉽지는 않았으나.. 오히려 이전 청소년 상어보다 훨씬 쉽게 풀었습니다. 문제 조건 자체가 상당히 복잡하게 느껴졌는데, 이전에 한번 청소년 상어에서 호되게 당해서 그런지 몰라도 차근차근 구현하니까 풀만하게 느껴집니다. 전형적인 구현(..

출처: https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 전형적인 구현 문제입니다만, 조건이 상당히 많아서 실수없이 구현하기가 어려운 문제입니다. 평소에 구현 유형 문제를 많이 풀어보지 않으면 머리에 과부하가 걸리는 문제인 듯 합니다.. 소스코드는 다음과 같습니다. from copy import deepcopy dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, -1, -1, -1, 0, 1, 1, 1] ..

출처: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성전자 공채 코딩테스트에 나왔던 기출문제입니다. 사실 이 문제를 풀었다는 것은 저에게 나름 뜻깊은 일입니다. 상반기 코딩테스트에서 좌절한 뒤, 처음 코딩테스트 알고리즘 공부를 시작했을 때 접했던 것이 이 문제입니다. 당시에는 정말 아무것도 몰랐기 때문에 '내가 정말 코딩테스트에 합격할 수 있을까?'라는 의문이 들 정도로 어렵게만 느껴졌습니다. 그러나 매일의 힘을 믿고 하루하루 정진..

출처: https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 아이디어를 떠올리는 것에 상당히 애를 먹었던 문제일뿐만 아니라, 예외사항에 대해서 모두 고려해야 했던 쉽지 않았던 문제입니다. 다만 후술하겠지만 아이디어를 떠올린 이후에는 구현이 그다지 어렵지 않고, 채점 케이스도 허술하기 때문에.. 어려우면서도 쉬운(?) 문제였던 것 같습니다. 풀이 위상정렬 알고리즘을 사용하는 대표적인 문제로 '선수과목 문제'를 떠올려볼 수 있습니다. 이 문제는 ..

출처: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 이용한 최단경로 문제는 나오기만 하면 정말 땡큐인 문제인 듯합니다. 이 문제 역시 그래프의 노드 개수가 100개 이하이므로, 플로이드-워셜 알고리즘을 사용하여 손쉽게 해결할 수 있습니다. 플로이드-워셜 알고리즘에 대한 조금 더 상세한 설명은 다음 링크를 참조바랍니다. 링크: https://jcy1996.tistory.com/24?category=958980 플로이드..

출처: 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] * (..

출처: 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아이디어를 떠올리기 쉽지 않은 이진탐색 문제이다. 공유기 간 최소거리를 정해놓고 몇 개의 공유기가 설치될 수 있는지 확인한다. 설치할 수 있는 공유기의 개수를 기준삼아 설치해야 하는 공유기의 개수보다 적으면 최소거리를 적게 잡는다. 반대의 경우엔 이미 설치해야 하는 만큼 설치가 가능하다는 의미이므로 정답을 저장하되, 최대거리를 구하는 문제이므로 더 큰 거..