이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 배열이 아니라 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬하는 문제이다. 정렬문제이므로 어차피 문자열로 처리해야 했기에 입력값을 int로 변환하지 않고 문자열 타입 그대로 받았다. 그 후 sorted() 를 취해 문자열을 정렬한 후, "".join() 을 사용했다. 참고 python에서 문자열 자체를 정렬하려면, s.sort()를 쓰면 안된다. string의 경우 첫글자의 주소값으로 참조를 하기에 원본이 변경되면 안되므로, str type에 sort() ..

문제링크 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제설명 홀수 N개의 값들에 대해 산술평균, 중앙값, 최빈값, 범위를 차례로 구하는 문제로 까다로운 조건이 없었다. 최빈값이 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력해야 하는 조건이 주어졌다. 이 조건에 대해서는 Counter의 most_common으로 2개까지만 구한 후 케이스를 구분하는 방식을 취했다. most_common으로 최빈값을 구한다면, 중앙값 뿐 아니라 최빈값에 대해서도..

문제링크 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 시간 제한과 메모리 제한이 있는 문제이며, 특히 메모리 제한이 빡센 문제로 단순하게 sort로 풀고 PyPy3로 돌려서 해결되는 문제가 아니다. 앞에서 블로깅했던 수 정렬하기 2(https://www.acmicpc.net/problem/2751) 문제는 메모리 제한이 256MB 였지만, 이번 문제는 메모리 제한이 8MB이므로 정렬이라는 접근보다는 새로운 접근으로 풀어야 했다. '수 정렬하기 2' 처..

문제링크 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제설명 O(nlogn) 알고리즘으로 풀어야하는 문제이다. 따라서 시간복잡도가 O(n^2) 인 insertion sort, bubble sort로는 풀기 어렵고, 최악의 시간복잡도가 O(nlogn)인 merge sort나 heap sort로 풀어야 한다. 또한, python 기본 내장함수인 sort, sorted도 병합정렬을 기반으로 만들어진 함수로, O(nlogn)의 시간복잡..

문제링크 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제설명 브루트포스로 푸는 문제이다. 연속으로 666이라는 숫자가 나타나야하므로 문자열로 비교하는 것이 효율적이라고 생각했다. 변수 title을 초기값 666으로 선언해서 title에 1씩 더해갔으며, 주어진 n으로부터 1씩 빼가며 카운팅을 했다. n이 0이 되었을 때의 title을 출력하며 마무리한다. 문제풀이 title = 666 n = int(input()) while n: if ..

문제링크 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제설명 [아이디어1] N x M 판을 전체 경우의 수로 돌려야 한다. 그러기 위해서는 인덱스가 8을 넘지 않도록 조정을 해줘야 한다. 9x9에서 움직여서 조사할 수 있는 경우의 수는 2x2 = 4개이며, 10x10에서 움직여서 조사할 수 있는 경우의 수는 3x3 = 9개이고, 11x11에서 움직여서 조사할 수 있는 경우의 수는 4x4 = 16개이다. 따라서 i는 N-7의 범위에서..

문제링크 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제설명 n명 집단에서 각 사람의 덩치 등수는 자신보다 더 '큰 덩치'의 사람의 수로 정해진다. 또한, 가장 큰 덩치의 사람은 키와 몸무게가 모두 어떤 사람보다도 더 커야하며 그 등수는 1이다. 따라서 자신보다 더 큰 덩치의 사람이 k명이면 그 사람의 덩치 등수는 k+1이다. 이 때, 같은 덩치 등수를 가진 사람은 여러 명도 가능하므로, 2중으로 for문을 돌면서 요소 간 완..

문제링크 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제설명 맨 아래 이외의 원반들은 목표장대가 아닌 보조장대로 옮기는 것을 재귀적으로 실행한다. 또한, n개의 원반을 이동시키기 위해서는 그 위의 n-1개의 원반을 다른 장대로 이동하고 맨 아래 원반을 도착지로 이동해야 한다. 그리고 다시 n-1개의 원반을 이동해야 하므로 다음과 같은 점화식이 성립한다. a_n = 2a_(n-1) + 1 이를 일반항으로 풀어내면 총 이동횟수는 ..