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/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수 판별 알고리즘 중, 에라토스테네스의 체 알고리즘을 이용하면 손쉽게 답을 구할 수 있습니다. 에라토스테네스의 체 알고리즘은 하단 링크에서 설명하고 있습니다. https://jcy1996.tistory.com/68 소수 판별 알고리즘 특정한 수의 소수 판별 특정한 수가 소수(Prime number)인지 여부를 판별하기 위해서는 해당 수에 이르기까지 모든 수를 나누어보고 나머지가 0인지 확인하면 됩니다. import ma..

출처: 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/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 무향그래프에 대해서 최소 신장트리를 구하는 문제이므로, 크루스칼 알고리즘을 적용하면 쉽게 풀 수 있습니다. 크루스칼 알고리즘: https://jcy1996.tistory.com/35 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘에 대해 이해하기 위해서는 먼저 신장 트리(Spanning Tree)에 대해 이해할 필요가 있습니다. 신장 트..

문제 한 마을은 N개의 집과 M개듸 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작..

문제 공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번쨰 비행기를 1번부터 $g_{i}$번째(1 $\le$ $g_{i}$ $\le$ G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다. 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에는 탑승구의 수 G(1 $\le$ G $\le$ 100,0..

문제 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다. 1번 여행지 - 2번 여행지 1번 여행지 - 4번 여행지 1번 여행지 - 5번 여행지 2번 여행지 - 3번 여행지 2번 여행지 - 4번 여행지 만약 한울이의 여행 계획이 2번 → 3번 → 4번 → 3번이라고 해봅시다. 이 경우 2번 → 3번 → 2번 → 4번 → 2번 → 3번..