끄적끄적

문제 풀이

 1. 간단한 dp 문제로, n번째 타일 장식물의 한 변의 길이 dp[n]에 대한 점화식은 다음과 같다.

 dp[n] = dp[n-1]+dp[n-2]

 2. 문제는 n번째 타일 장식물까지 붙였을 때, 가장 바깥의 둘레를 구하는 것인데, 예제에서 제시한 아래의 그림을 살펴보면, 계속 직사각형 형태를 띔으로 상하, 좌우의 길이는 각각 같다. 또한, 상하 또는 좌우의 길이 중 하나는 마지막 타일 장식물의 한 변의 길이가 되며, 나머지 한 변의 길이는 마지막 타일 장식물의 길이와 그 전 타일 장식물의 길이가 된다. 

예를 들면, 5개의 타일 장식물이 붙은 경우에는, 세로의 길이는 마지막 타일의 길이인 5 이고, 가로의 길이는 마지막 타일 장식물의 길이인 5에 이전 타일 장식물의 길이인 3을 더한 8이다. 6개의 타일 장식물을 붙였을 경우에는 가로가 8, 세로는 8(마지막 장식물의 길이)+5(이전 장식물의 길이) 인 13이 된다.

 따라서 n개의 타일 장식물을 붙였을 때의 둘레는 2*dp[n] + 2(dp[n]+dp[n-1]) 이 된다.

Python Code

문제 링크

문제풀이

 N개의 퀸을 하나씩 가능한 자리에 놓는 dfs 문제이다.

 1. N*N 체스판에 N개의 퀸을 놓으므로 한 열에 퀸을 하나씩 놓으면 된다.

 2. answer를 static 변수로 선언해 둔다.

 3. depth가 i 일 때, i번째 열의 퀸의 위치를 결정하며, depth를 1씩 증가시켜간다.

 3-1. i번째 열의 퀸의 위치를 결정할 때는 j<i인 j 열의 퀸들의 위치를 참고한다. i번째 퀸과 j번째 퀸의 행이 같으면 안되며 대각선에 있어도 안된다.(row_i - row_j != col_i - col_j)

 4. depth가 N이 되면 2에서 선언한 answer에 1을 더해준다.

 5. 가능한 모든 경우에 대하여 3 ~ 4 를 반복한 후 answer를 반환한다.

Java Code

Line 4 의 solution method가 main method로, 첫번째 열의 퀸의 위치를 결정한 후 dfs(explore method)를 호출한다.

Line 15 의 explore method가 dfs를 실행하는 부분으로, depth가 n이 되면 answer에 1을 더해주며, depth가 n보다 작은 경우에는 depth 열의 퀸의 위치를 결정한다. depth 열의 퀸의 가능한 모든 위치에 대하여 depth+1로 다시 explore method를 호출한다.

Line 28의 check method와 line 36의 checkPair method로 과정 3-1의 조건을 구현한다. checkPair는 두 개의 퀸의 위치를 비교하며, check에서 마지막 퀸의 위치와 이전 퀸들의 위치를 비교한다. 이전 퀸들 간의 위치는 이전 depth에서 고려했을 것이므로 다시 할 필요는 없다.

문제 링크

Reinforcement learning의 목표

 결국 강화학습에서 하고자 하는것은 세상이 어떻게 돌아가는지를 모를때 ($T(s,a,s'), Reward(s,a,s')$ 등 우리의 행동에 따른 보상을 알 수 없을 때), 현재 상태 $s$에서 utility를 최대화하기 위한 policy $\pi(s)$와 그에 따른 보상 $V_{opt}(s)$ 또는 $Q_{opt}(s,a)$를 추정하는 것이다. MDP를 모르는 상황에서 우리가 MDP를 추정하여 만들어가는 과정이라고도 할 수 있다. 이를 위해서 데이터를 수집하고 그를 바탕으로 여러 값들을 추정하게 된다.

방법론 요약

 강화학습의 방법론으로는 크게 4가지가 있는데, 먼저 Model-based Monte Carlo 방법의 경우에는 가장 단순하게 주어진 데이터로 부터 통계적으로 $\hat{T}$ 와 $\hat{Reward}$를 추정하는 것이다.

 Model-free Monte Carlo 방법의 경우에는 위의 방법과는 다르게 $\hat{Q}_\pi$를 추정하게 된다. 즉, 각 Transition probability와 그에 따른 utility를 구하는 것이 아니라 현재 상태에서 얻을 수 있는 $utility$의 기댓값, 즉 우리가 데이터를 얻은 전략에 따른 $Q_\pi$를 직접 구한다.

 SARSA의 경우에도 Model-free MC의 다른 방식으로, $\hat{Q}_\pi$를 추정하지만, $utility$를 u가 아닌 $r + \hat{Q}_\pi$로 대체함으로써 target의 variance를 줄인다.

 마지막으로 Q-Learning의 경우에는 $\hat{Q}_{opt}$를 추정하는데, MDP에서 $Q_{opt}$를 구하는 방식을 활용하되, target을 $\hat{Q}_{opt}$에 따른 $\V_{opt}$를 활용하여 $r+\hat{V}_{opt}$로 한다. 

On-policy와 Off-policy

 위의 네 방법을 보면, Model-based Monte Carlo와 Q-Learning의 경우에는 추정하는 값이 $\pi$에 독립적이다. 이러한 경우를 Off-policy라고 하며, 반대로 Model-free Monte Carlo와 SARSA의 경우에는 추정하는 값이 내가 데이터를 얻기 위해 취한 $\pi$에 의존적이며, 이러한 경우를 On-policy라 한다. 즉, 직접적으로 optimal value를 구하는지 아니면 $\pi$에 따른 value를 먼저 구하는지가 두 개의 차이라 할 수 있다.

문제풀이

 주어진 조건에 맞게 정렬하는 문제이다. 

 1. 장르별로 각 곡이 몇 번 재생되었는지를 가지고 있는 딕셔너리(g_songs)와 각 장르가 총 몇번 재생되었는지를 가지고 있는 딕셔너리(g_num)을 선언한 뒤, 주어진 genres와 plays에서 하나씩 꺼내며 적절히 넣는다.

* g_songs는 key 가 장르명이고 value는 (곡 번호, 재생수))인 튜플들로 이루어진 리스트이다.

* g_num은 key가 장르명이고 value는 그 장르의 모든 곡들의 재생수의 합이다.

 2. 주어진 곡들을 모두 넣은 후, g_num의 key를 value에 따라 정렬한다. (정렬의 첫번째 조건인 "속한 노래가 많이 재생된 장르를 먼저 수록합니다."를 먼저 수행)

 3. 2에서 정렬된 순서대로 각 장르별로 g_songs에서 value들을 가져와 각 곡의 재생수인 튜플의 두번째 요소로 정렬한 후, 같다면 곡 번호인 튜플의 첫번째 요소로 정렬해 준다. (정렬의 두, 세번째 조건 수행)

Python Code

Line 3의 comparator 함수는 과정 3을 수행하는 함수로 cmp_to_key 를 이용하여 line 34에서 sort함수의 key로 활용됩니다.

Line 18 의 i는 각 곡의 고유 번호로, for문은 과정 1을 수행합니다.

Line 28 ~ 29는 과정 2의 장르를 장르별 총 재생수로 정렬하는 과정입니다.

Line 34는 장르별로 해당 곡들을 꺼내와 정렬하는 과정입니다.

문제 링크

친구 또는 친구의 친구 수가 가장 많은 사람을 찾는 문제이다.

문제 풀이

 모든 사람의 친구들을 저장하기 위해 set 자료구조를 사용하였으며, key가 integer(사람의 번호), value가 set(친구들의 목록)인 딕셔너리를 사용하였다.

 1. N번째 줄에 N번째 사람과 친구인 사람들의 목록이 나오므로, N번째 줄에서 요소가 'Y'인 인덱스 M을 key가 N인 set에 넣는다. 또한, Undirected graph이므로 key가 M인 set에 N을 넣는 과정 역시 필요하다. (M은 N의 친구, N은 M의 친구)

 2. 또한 N의 친구들끼리도 서로 2-친구이다. N의 친구를 M1, M2라 하면, M1과 M2는 N을 매개로 한 2-친구가 된다. 따라서 key가 M1인 set에 M2를 넣고, 반대과정 역시 진행해 준다.

 3. 딕셔너리에서 value의 길이가 가장 큰 key를 반환한다.

Python Code

Line 10 ~ 12 : dic[N]에 M을 넣는 과정 (M은 N의 친구)

Line 17 ~ 22 : dic[M]에 N을 넣는 과정 (N은 M의 친구)

Line 29 ~ 35 : N의 친구들끼리 서로 친구로 넣어주는 과정

문제 링크

2010 정보올림피아드 초등부 마지막 문제이다.

문제 풀이

1. A부터 순서대로 k개의 알파벳의 배열을 만든다.

2. ?로 시작하는 사다리가 나올 때 까지 1에서 만든 배열을 주어진 사다리에 따라 바꾸어 나간다.

3. ?로 시작하는 사다리를 만나면 그 이후의 사다리들을 배열에 넣고 뒤집어 준다.

4. 정답 배열을 3의 배열에서 순서대로 꺼내며 사다리에 맞게 정답 배열을 바꾸어 나간다.(3에서 뒤집에 주었으므로 정답 배열은 가장 밑의 사다리부터 따라가게 된다.)

5. 1의 배열과 4의 배열을 비교하여 적절한 사다리 모양을 만든다.

Python Code

line 5의 al이 과정 1의 배열이다.

line 6의 answer가 과정4의 정답 배열이다.

swap 함수는 al을 사다리에 따라 바꿔주며, swap2는 answer를 바꿔준다.

line 17의 for 문이 과정 2이며, line26의 rest배열이 과정 3의 ?이후의 사다리 배열이다.

line 28의 for 문이 과정 4이다.

line 34가 마지막 과정 5 이다.

37 line의 마지막 조건의 경우, 사다리가 연속으로 이어진 경우는 없다는 조건을 구현한 것이다.

문제 링크

유형 : bfs

저번 문제에 이어서 2010 한국정보올림피아드 초등부 문제이다.

문제풀이

 bfs(Floodfill) 알고리즘을 이용하여 섬의 개수를 찾는 문제이다.

1. 먼저 기준 높이를 정하고, 지역의 높이가 기준 높이보다 높다면 0 아니면 1이 되도록 visit 배열을 초기화한다.

2. (0,0)부터 visit[row][col]이 0인 값을 찾고 그 row, col 값을 기준으로 bfs를 한다. 여기서 방문되는 곳들이 1개의 영역을 형성한다.

3. 2의 과정을 기준높이가 1부터 (지역 높이의 최댓값)-1 까지 반복한다. (기준높이 = 지역높이의 최댓값 같은 경우의 영역의 개수는 0개일 것이므로)

Python Code

42 line ~ 에서 입력값을 받는다.

solution 함수에서 3의 과정을 진행한다.

bfs 함수는 말 그대로 과정 2의 bfs를 하는 과정이다.(한개의 영역을 찾는다.)

getArea 함수의 경우에는 visit 함수를 초기화하고 영역의 총 개수를 센다.

호출 순서는 아래에서부터가 된다. main(입력값을 받는다) > solution(기준 높이를 설정한다) > getArea(visit 배열을 초기화하고 영역의 총 개수를 센다) > bfs(각 지점을 포함하는 영역을 구한다)

시간복잡도는 O(N^2*최대높이)가 된다.

높이가 2인 경우, 높이가 1인 경우의 영역을 참고하면 시간복잡도를 더 줄일 수 있을 것이다. 지금의 풀이의 경우, 높이가 2인 경우, 높이가 1인 경우를 참고하지 않고 처음부터 풀이를 하게 된다.

문제링크

유형 : 투포인터 알고리즘

올림피아드 초등부 1번문제

문제풀이

 이미 정렬된 배열이 들어온다는 것을 이용한다.

1. 두 포인터 l과 r에 맨 첫 요소와 마지막 요소의 주소를 넣는다.

2-1. l과 r의 합이 양수일 경우에는 r이 더 작아져야하므로 r을 하나 앞으로 옮겨준다.

2-2. l과 r의 합이 음수을 경우에는 l이 더 커져야하므로 l을 하나 뒤로 옮겨준다.

3. 이때, l과 r의 합의 절댓값이 이전에 기억해둔 l과 r의 합의 절댓값보다 작다면 이 값과 l, r값을 기억해둔다.

예시

1. l과 r의 합이 5 이므로 r을 하나 앞으로 당겨준다. 이 때 5와 (-10, 15)를 기억해둔다.

2. l과 r의 합이 -6 이므로 l을 하나 뒤로 옮겨준다. 이때의 합의 절댓값 6은 5보다 크므로 기억해둘 필요는 없다. 이런식으로 진행하다보면 4에서 저장된 -5와 4의 합의 절댓값이 끝까지 살아남게 된다.

5과정 이후에는 l+r이 항상 양수이므로 r이 계속 낮아지다가 l보다 낮아지면 알고리즘이 종료된다.

Python code

후기

리스트만 입력값으로 들어오는줄 알고 21 line을 빼먹었다가 한참을 헤맸다...

파이썬으로 푼 사람이 많지는 않지만 1등을 해보는 날이 오다니..

문제 링크