이것저것 공부 기록하기

문제링크 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' 처..

추천시스템이란? 추천 시스템 : 아이템을 표현하는 다양한 방법(유저정보, 아이템 정보) 유저의 현 상황을 파악한 후 아이템을 추천하는 방법으로, 유저의 기호가 계속해서 변하는 것을 체크해야 함 cold start problem 개선 연구 필요 데이터마다 고유한 특성이 존재(ex. 이미지: 픽셀, object, 언어: 문법 등) 추천 시스템에서 주로 사용하는 데이터의 형태 categorical type 변수가 많아서 one hot encoding 된 데이터값이 많음 one-hot vector 특성상 데이터 차원이 크고 매우 sparse 함 학습을 위한 label 생성 방법 다양 Rating Matrix를 Matrix Factorization 을 통해 복원하는 방식 → Auto Encoder 계열 방식으로 ..

문제링크 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 이를 일반항으로 풀어내면 총 이동횟수는 ..

문제링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀함수로 푸는 문제이다. 규칙파악이 포인트이고, 그 이후에는 재귀로 풀면 된다. 규칙파악 일정하게 가운데가 뚫린 정사각형 패턴이 반복되고 있다. 예를 들어, 3(=3^1)일 때는 가운데에 공백이 있고 1(=3^0)개 씩의 별이 찍히고 있다. 따라서 패턴은 다음과 같다. 3^i일 때 가운데를 공백으로 하고, 3^(i-1) 개 씩의 별 찍는다. 또한, 정사각형의 ..