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..

만약 [left index, right index]로 구성된 M개의 쿼리에 대해 구간합을 구하고자 한다면, 단순 반복으로는 시간복잡도가 O(NM)이 됩니다. 따라서 데이터의 개수가 1,000,000개인 경우에는 쿼리가 10개만 되어도 연산량이 급격하게 많아집니다. 조금 더 효율적으로 구간합을 구할 수 있는 방법 중 하나가 바로 접두사 합(Prefix sum)입니다. 이 때, 접두사 합은 리스트의 맨 앞부터 특정 위치까지 누적 합을 구해 놓은 것을 의미합니다. 즉, 이후의 계산을 위해 일종의 캐싱을 해놓는 것이라 볼 수 있겠습니다. 접두사 합 알고리즘은 다음과 같이 진행됩니다. 1. N개의 수에 대하여 접두사 합(Prefix sum)을 계산하여 배열 P에 저장한다. 2. 매 M개의 쿼리 정보 [L, R]을..

투 포인터(Two Pointers) 알고리즘은 말 그대로 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 간단하게 얘기하면 '시작점'과 '끝점'을 이용하여 데이터의 범위를 표현하는 방법론입니다. 특정한 합을 가지는 부분 연속 수열 특정한 합을 가지는 부분 연속 수열을 찾아야 할 때, 투포인터 알고리즘이 유용하게 쓰일 수 있습니다. 절차는 다음과 같습니다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2. 현재 부분합이 M과 같다면 카운트한다. 3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다. 4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까..

특정한 수의 소수 판별 특정한 수가 소수(Prime number)인지 여부를 판별하기 위해서는 해당 수에 이르기까지 모든 수를 나누어보고 나머지가 0인지 확인하면 됩니다. import math def is_prime_number(x): for i in range(2, x): if x % i == 0: return False return True is_prime_number(1e100) 단 이 경우엔 x가 매우 큰 값일 경우 계산해야 하는 경우의 수가 많아져 결과적으로 효율성이 저하됩니다. 따라서 이를 개선하기 위해서 약수(Dvisor)의 성질을 알고 있다면 좋습니다. 모든 수는 자신의 모든 약수에 대해서 대칭적인 형태를 보입니다. 16을 예로 들었을 때, 16의 약수는 1, 2, 4, 8, 16이며 1 ..

출처: 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)에 대해 이해할 필요가 있습니다. 신장 트..