우노

문제 링크 https://www.acmicpc.net/problem/10610 풀이 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 102에 포함된 숫자는 1, 0, 2이며, 30의 배수가 되는 가장 큰 수는 210(2, 1, 0)이다. 이 문제는 해당 수가 30의 배수가 되는 조건을 알아야 풀 수 있으며, 30의 배수가 되는 조건은 아래와 같다. 일의 자리가 0이어야한다. 따라서, 받은 숫자 내에 0이 없다면 -1을 출력해야한다. 각 자리의 숫자들을 모두 더했을 때, 3으로 나누어 떨어져야한다. 따라서, 받은 숫자들의 합이 3으로 나누어 떨어지지 않는다면 -1을 출력해야한다. 두 조건을 통과했을 때, 주어진 숫자들을 내림차순 정렬한다면, 30의 배수가 되는..

문제 링크 https://www.acmicpc.net/problem/1931 풀이 주어진 시작 시간과 종료 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는, 회의가 빨리 끝나는 순서대로 정렬을 진행해야 한다. 회의가 빨리 끝날수록 뒤에서 고려할 수 있는 회의가 많기 때문이다. 만약, 회의가 빨리 시작하는 순서대로 정렬을 진행한다면, 오히려 회의가 늦게 끝날 수도 있다. 또한, 회의가 끝나는 시간이 같을 경우엔, 회의가 빨리 시작하는 순서대로 정렬을 진행해야한다. 예를 들어, 회의가 (2, 2), (1, 2) 순서대로 주어진다면, (2, 2) 회의만 진행할 수 있지만 (1, 2), (2, 2) 순서대로 주어진다면, (1, 2), (2, 2) 회의를 모두 진행할 수 있기 때문이다. 따라서, 주어진 회..

문제 링크 https://www.acmicpc.net/problem/1759 풀이 사용할 문자들을 입력 받아, 모음과 자음 리스트에 추가합니다. i를 1부터 l-2까지 증가시키며, 모음 리스트에서 i개의 모음을 뽑는 조합과 자음 리스트에서 l-i개의 자음을 뽑는 조합을 생성합니다. 이후, 모음 조합과 자음 조합의 각 요소들을 결합한 뒤, 정렬하고, 결과 리스트에 추가합니다. 알고리즘에 대한 세부 설명은 아래 코드와 같습니다. 코드 import sys from itertools import combinations # 결과 문자열 길이 l과 알파벳 개수 c l, c = map(int, sys.stdin.readline().split()) # 모음 전체 temp = ['a', 'e&#39..

예제 코드 s = "dcba" s1 = sorted(s) # ['a', 'b', 'c', 'd'] s2 = ''.join(s1) # abcd

예제 코드 # Int를 Char로 변환 print(chr(97)) # a print(chr(122)) # z # Char를 Int로 변환 print(ord('a')) # 97 print(ord('z')) # 122

문제 링크 https://www.acmicpc.net/problem/1929 풀이 에라토스테네스의 체를 이용해야하는 대표적인 문제입니다. m의 값이 최소 1인 것을 주의해야하며, n의 값이 최대 1000000인 것을 주의해야합니다. 또한, 소수 탐색 시, n의 제곱근까지만 탐색을 진행한다면 실행 시간을 단축시킬 수 있습니다. 코드 import sys import math # m과 n 입력 m, n = map(int, sys.stdin.readline().split()) # 소수 판별 결과를 저장하기 위한 리스트 초기화 # 처음에는 모든 수가 소수인 것으로 초기화 array = [True] * (1000001) # 1은 소수가 아님 array[1] = False # 2부터 n의 제곱근까지 에라토스테네스의 ..

들어가기 앞서 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. ‘특정한 합을 가지는 부분 연속 수열 찾기’ 또는 ‘정렬되어 있는 두 리스트의 합집합’과 같은 문제에 사용된다. 특정한 합을 가지는 부분 연속 수열 찾기 투 포인터 알고리즘을 이용하여 ‘특정한 합을 가지는 부분 연속 수열 찾기’ 문제를 풀어보자. 해당 문제는, 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 ‘특정한 합’을 갖는 수열의 개수를 출력하는 문제이다. 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이며, 해당 문제에서는 부분 연속 수열의 시작점(start)와 끝점(end)의 위치를 기록한다. 특정한 부분..

들어가기 앞서, 소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다. 간혹 코딩 테스트에선, 어떠한 자연수가 소수인지 아닌지 판별하거나, 1부터 N까지의 모든 소수를 출력해야 하는 문제 등이 출제된다. 따라서, 해당 포스팅에선 두 가지 문제를 해결하는 효율적인 방법에 대해서 다뤄볼 것이다. 특정 자연수의 소수 판별 특정한 자연수 X가 소수인지 아닌지 효율적으로 확인하기 위해선, 자연수 X의 제곱근까지 나누어떨어지는 수가 있는지 없는지 확인하면 된다. 해당 알고리즘의 시간 복잡도는, 자연수 X의 제곱근까지만 확인하므로 O(X^1/2)이다. import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를..

문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했습니다. 팀은 1번부터 n번까지 번호가 매겨져 있습니다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일합니다. 올해 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했습니다. 그 대신에 작년에 비해서 상대적으로 순위가 바뀐 팀의 목록만 발표하려고 합니다. (작년에는 순위를 발표했습니다.) 예를 들어, 작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표할 것입니다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 합니다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하세요. 하지만, 본부에서 발표한 정보를 가..

문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었습니다. 왕국은 N개의 행성으로 이루어져 있습니다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 합니다. 행성은 3차원 좌표 위의 한 점으로 생각하면 됩니다. 두 행성 A(Xa, Ya, Za)와 B(Xb, Yb, Zb)를 터널로 연결할 때 드는 비용은 min(|Xa - Xb|, |Ya - Yb|, |Za - Zb|)입니다. 민혁이는 터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 합니다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하세요. 입력 조건 첫째 줄에 행성의 개수 N이 주어집니다. (1