고양이 두 잔

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 풀이..

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 풀이 계속 이어지는 정렬 문제다. 기본 수학 문제는 푸는 재미가 있지만 이 문제와 같이 자료형을 다루는 것은 언어 자체에 대해 친숙해진다는 면에서 또 다른 재미가 있는 것 같다. 이번에는 주어진 문자열에서 중복을 제거한 뒤 길이순 길이가 같다면 사..

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 조금 헷갈리지만 일단은 동적 계획법 문제이다. 그걸 몰랐으면 순열로 모든 부분수열을 순회하려고 했을 것 같다. 문제를 보고 이게 뭘로 풀 때 더 효율적인 유형인가 판단하는 것도 능력일 듯. 어쨌거나 주어진 두 문자열에 대해서 각각 처음부터 끝까지 순회하며 ..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 풀이 문제에서 주어진 기준은 파이썬에서 다차원 리스트를 정렬할 때 기본적으로 사용하는 기준이다. 따라서 그냥 아래처럼 정렬해도 답은 맞출 수 있다. import sys n = int(sys.stdin.readline()) b = [] for..

문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 풀이 입력받은 문자열을 바로 리스트로 전환할 수 있는 파이썬은 여러모로 편리하다. 문제가 있다면 내가 파이썬으로 개발을 하고있지 않아 자주 까먹는다는 것 정도. 문자열을 리스트로 받아 정수형으로 전환한 뒤 정렬, 이어서 다시 문자열로 합쳐서 출력해주었다. import sys a = list(map(int, list(sys.stdin.readline().strip()))) a.sort(reverse=True) print(*a, sep='')

문제 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11,..., F: 15,..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다. 출력 첫째 줄에 10진법 수 N을 B진법으로 출력한다. 풀이 이 문제도 누구도 시키지 않은 복잡한 방법으로 풀다가 수도 없이 틀리고 나서 싹 지우고 다시 풀었다. 그나마 이전 문제에 대한 경험이 있어서 시간이 덜 소모되기는 했다. 알고리즘은 아래와 같다. 주어진 10진법 수를 B로 나눈 나머지를 문자열에 더해준다. N을 N ..

문제 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11,..., F: 15,..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 출력 첫째 줄에 B진법 수 N을 10진법으로 출력한다. 풀이 즐거운 토요일. 빡센 문제보다는 쉬운 문제로 두어 개 풀고 딴짓하고 놀아야지~ 했다가 이 문제와 다음 문제에게 털렸다. 오히려 어줍잖게 알고리즘을 풀었던 경험 때문에 이상하게 꼬아서 풀고, 게다가 틀리기를 반복함. 문제는 별 거 없다. 말..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 문제 소개에 카운팅 정렬을 사용하면 된다고 해서 순수하게 구현해놓은 카운팅 정렬을 써보았다. 단 한 문제도 통과하지 못하고 메모리 초과. 어떻게든 스텝을 줄여보려고 for문을 합쳐보기도 하고 리스트의 요소 개수를 조절해봐도 여전히 메모리 초과와 시간 초과. 그래도 도전해보겠다고 한시간 내내 매달리다가 포기하고 그냥 카운팅 정렬의 아이디어만 응용하기로 했다. 풀이 단계..

문제 두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄 을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 문제의 팁에 병합정렬이나 힙정렬 등으로 풀 수 있으나 내부 정렬을 이용해도 된다고 적혀있다. 파이썬의 내부 정렬은 팀정렬이기 때문에 병합정렬만을 사용하는 것보다는 당연히 빠르겠으나, 이참에 파이썬으로도 병합정렬을 구현해보기로 마음먹었다. 아래는 그 결과물: 2023.03.31 - [Development/.py] - [Algorithm..