SW - IT 충남대 콘테스트 문제 풀이 + 후기

 나는, 22학년도 충남대 컴융 신입생이다.
초반엔 극히, 평범한 학생이었고, 술마시고 게임만 하는 페인의 삶을 살았다. 
TMI.1 지금은 PS페인이다.
TMI.2 FPS만 극한으로 파던 사람이다.

4월 쯤인가? 학교 코딩 테스트에서, 간단한 별 찍기 문제가 나왔다. 그 문제에서, 너무 괴로웠고, 쉽게 하는 친구들을 보며, 자괴감이 들었다.

그 후, 만난 컴융 친구들 중, 배인수(사인은 PS로 인한 혈압사)라는 친구가 백준을 하고 있고, 실버를 찍은 것을 보여주었다. 별 찍기 같은 문제들을 잘 풀고 싶은 마음도 있었고, 친구가 실버를 찍은 것을 보니 나도 백준을 하고 싶었고, 기숙사에 들어가자 마자, 백준에 들어가 문제를 미친듯이 풀기 시작했다. 이게 PS페인의 시작이었다..

그리고 5개월 후... SW - IT 콘테스트가 열렸다.


나는 그래도 나름 고인물이 되어있고, 개같이 신청을 넣었다.
그리고 본 대회에서 9솔을 했다.




솔직히, 시간이 있으면 충분히 다 풀지만, 대회라서 긴장하고 있었고, 시간도 촉박 하다는 압박감, 그리고 초반에 실수를 너무 많이 해서, 아래서 올라오는 순위에도 정신이 너무 팔려 있었다.

실제로 대회에서, 했던 생각을 바탕으로, 간단한 문제 해설과, 문제 리뷰를 해보겠다.
진짜 아주 간단하게 해설을 썻으니, 한번 쓱 보고 문제를 푸는 것을 추천한다.

혹여나, 대회에서 기대 이하의 성과를 이룬 사람들은, 노력해서, 다음에 목표한 성과를 이루길 기원한다!!



Division 1 내용만 다룬다.









min(빵 / 2, 패티) 가 정답이다. (정수 연산이다)

실제로 대회에서도, 여기까지 생각하고, 아무 생각없이 제출하고 다음문제로 넘어갔다.







홀수는 홀수 칸에, 짝수는 짝수 칸에 있어야 한다. 
홀수의 개수와, 짝수의 개수, 총 칸의 길이를 적절하게 잘 계산하면 된다.

이 문제도, 아무 생각없이, 제출하고 다음문제로 넘어갔다. 너무쉬웠다.







특정 문자열을 입력받아, 문자를 최소한으로 바꿔, 해당 문자열을 팰린드롬으로 만드는 문제이다.







나는 우선순위로 풀었다. (큰 거 우선 정렬)
큰 수를 먼저 보며, 우선순위에 있는 것보다 작으면, 우선순위에서 뺀 다음에 그 수를 넣었다.
우선순위의 크기가 정답이 된다.

PS를 많이 하지 않은 참가자도 많았기 때문에, 이런 문제는 참가자들의 의욕향상과 지식함양에 있어 좋은 문제라고 생각했다. < -- 대회에서 이생각함.







용태와, 유진이가 부를 수 있는 소수를 다 찾은 다음, 게임을 시작한다.
부를 때, 상대가 가지고 있는 소수를 내가 불러버려서, 상대가 부를게 없게 만드는 간단한 그리디 게임 문제다.

나는 5번 틀렸다. 개 억울하다. 인덱스를 2중 으로 돌려, 같은 걸 찾아 remove 시켰다.
그렇게 했는데 다 틀려서, 같은 소수의 개수를 세고, 각자 고유의 소수를 다 세준 다음에, 갯수를 줄여가는 방식으로 했는데, 그건 또 맞았다. 

분명, 컴퓨터는 나의 살기를 느꼈을 것이다...







굉장한, 관찰이 필요한 문제다.
(출제자 피셜 : 그정도 관찰이야?)

이전에 크기를 다 합쳤는데, 다음 도미노가 더 크기가 크다면, 나머지 왼쪽을 다 버려야 할까? 아니면 오른쪽에 도미노를 없애고 진행을 해야 할 까?

정답은 없다. 둘 다 해봐야 한다. 근데 어떻게 다 확인 해봐야 할까?
오른쪽에 도미노를 없애는 케이스로 진행을 한번 했다고 치자, 또 진행 하다가, 오른쪽 도미노가 더 크다, 그럼 왼쪽 도미노 들을 다 없애는 검사가 필요 할까? 아니다.

왜냐면, 그리디 적으로 생각하면, 왼쪽에 위치한 도미노 들을 다 없앤다는 건, 현재 진행할 도미노의 크기를 최대로 키운다는 단순한 발상에 기반한다.
우리는 이미 오른쪽 도미노를 없애는 케이스를 선택했고, 이건 곧 크기가 최대가 아니라는 것이다.

간단하게 말하면, 크기를 최대로 키워 온 것이 아니기 때문에, 굳이 검사할 필요가 없다!

그래서, 크기를 최대로 키우는 경우로 한번 검사를 하고,
모든 경우에 대하여, 선형으로 오른쪽 도미노를 제거하며, 진행하며 검사하면 된다.

대회 때, 크기를 최대로 키우는 경우만 검사를 했다가, 안 풀려서, 일단 다른 문제 풀러 갔고, 사람들이 많이 풀었길래, 조금 관찰하다가 풀린 문제다.
솔직히, 한번에 안 풀려서, 쫄튀했다 ㅋㅋㅋ

글을 다 쓰고, 추가로 적습니다.
크기를 최대로 키우는 경우를 검사하지 않아도, 오른쪽 도미노를 제거하며 모든 경우를 검사하면, 그 경우가 포함됩니다.

관찰이 필요가 없네용!







한 번 뒤집어야 한다. 근데, 가장 밝아야 한다.
한번의 상태 변화를 연속적으로 일으켜, 가장 밝게 해야 한다.

즉, 변화량이 가장 크면 된다!!

일단 원래 켜진 전구들의 합을 구해준다.
그후, 켜진 전구에 -1을 곱하여 음수를 만들고, 꺼진 전구는 그대로 둔다.

자 그럼 이 배열에서의, 최대 연속합을 구하는 문제로 치환할 수 있다.

나는 왼쪽에서의 최대 연속합, 오른쪽에서의 최대 연속합 dp를 만들었다.
그리고 선형으로 한번 탐색하여, 최댓값을 구했다.

max(원래 상태 + 왼쪽 dp + 오른쪽 dp - (자기 변화량))
자기 변화량을 빼는 이유는 포함 배제 원리에 의해 제거한다.

대회 참여자들이, 이 문제에서 막혔을 것이라고 생각한다.
이 문제는 최대 연속합을 구하는 문제로 치환을 하고, 또한, 그 알고리즘을 구현 할 수 있는가에 달려있다. 

이 문제를 풀지 못했거나 느리게 풀었다고, 낙심 하지 않기를 빈다.

최근에 뇌가 세그먼트 트리에 절여져 있어서, 최대 연속합 트리 템플릿을 가져다 쓸려고 했지만, 이미 손은 왼쪽 오른쪽 최대연속합 dp를 이미 만들어서, 그냥 이걸로 진행했다.

만약, 최대 연속합 트리를 가져다 썻으면, 12번을 보자마자 컷 했지 않을까?

본 대회에서는 6분 컷 했다.







놀이기구를 탈 수 있는 정도를 그냥 간단하게 큰 놀이기구, 작은 놀이기구라고 하겠다.

큰 놀이기구 부터 작은 놀이기구로 순서대로 타게 되면, 결국 큰 놀이기구의 이용권만 남게 된다.

그러면, 가장 큰 놀이기구를 어떻게 하면 제일 많이 탈까?

가장 큰 놀이기구를 탄다음, 다른 모든 놀이기구랑 번갈아 가면서 타면 된다.

끝났다. 생각은 최대한 간단하게 하는게 좋다.

정렬 한 후, 가장 큰 값을 제외 하고 다 더한다.
다 더한 값을 s 라고 하자. 가장 큰 값을 M이라고 하자.
정답은 s + min(s, M-1) + 1 이다.

가장 큰 값을 먼저 타고 시작하기 때문이다.  계산 식을 스스로 이해해보길 바라~

실제로 이렇게 접근했고, 가장 큰 값 계산 하는게 조금 걸렸다.
8분 컷 했고, 풀이를 떠올리는 시간만 6분이었던 것 같다. 쉽다고 생각했는데, 많은 사람들이 힘들게 푸는 것을 보았다.








다익스트라를 이용하여, 거리가 같을 때, 물이 더 크면, 재 탐색 할 수 있게 개조 한다.
끝.

나는 못 풀었다. 저 발상을 했지만, 숨겨진 함정이 있을 까봐, 도전도 안했다.
걍 할껄 ㅋㅋㅋ

근데 또 배인수(PS로 인한 혈압사)가 20번트라이 한걸 보면 안한게 오히려 좋을지도 ㅋㅋ







난 이 문제를 풀지 못했다. dp로도 할 줄 모른다. 그래서, MCMF 최대유량 최소 비용풀이를 쓰려 한다.
노란색 간선의 용량은 INF, 비용은 1로 하고, S에서 정점으로 가는 간선의 용량은 들어 오는 값으로 하고, 비용은 0, 정점에서 G로 가는 용량은 1, 비용은 0으로 한다.
이제 S에서 G로 MCMF를 돌린다.

진짜 개 간단한데, 원래 발상이 어려운 법이다. ㅜㅜ 못풀었다.










DFS를 이용한다. 설명을 어떻게 해야 될지 모르겠다. 구현 부는 간단한데, 발상이 어려워서..
쌍방향 간선을 받았다고 하겠다.

서브트리를 가지는 어떤 노드에 대하여, 그 서브 트리가 가지는 빨간색, 파란색 개수를 탐색.
탐색하면서, Dfs 타고 들어갈 때마다, 얻은 빨간색 파란색 정보를 취합하여, 미리 답을 계산하면서 진행하면 된다.

후, 쿼리를 진행할때, 쿼리 값 k에 대하여, 
전체 빨간색 파란색 값과, k 서브 트리의 빨간색 파란색 값을 통해, k의 상위 노드와 하위 노드들의 연결 갯수를 계산 한다.

너무 대충 설명한 것 같으니, 코드를 써보겠다.
루트는 당연히 1이다.

int R[N+1], B[N+1] 각 서브트리가 가지는 빨간색, 파란색 점의 개수를 저장한다.
이제 아래 노드부터 더해줘 가며, DFS를 통한, 트리에서의 다이나믹 프로그래밍을 시전한다.
간선은 load에, 양방향으로 받았다고 하겠다.

문법은 저세상 문법이다!!

def DFS (node, prev):
    for leaf in load[node]:
        if leaf == prev :
            continue
    
        DFS(leaf, node)
        ans[node] += R[leaf] * B[node]
        ans[node] += B[leaf] * R[node]
        R[node] += R[leaf]
        B[node] += B[leaf]
    
    if node's color is red :
        R[node] ++
    else:
        B[node]++
   

간단한 함수 작성이다. 서브트리로 이어지는 간선들끼리만 미리, ans배열에 기록 해놓고, 후에 상위노드와의 모든 연결 갯수만 추가로 더해주면 된다.

트리에서 다이나믹 프로그래밍의 근본이 되는 dfs 형식의 함수이다.

근본인데, 정점에 색깔을 곁들인 + 상위 노드와의 연결 관계 까지 역어본 이라고 하면 되지 않을까? 이런 괴랄한 문제를 만든 시온 선배에게 경외감이 든다.

나는, 대회에서, 트리에서 센트로이드 분할 정복을 시도 했다.....
TLE를 받았고, 멘탈이 부서졌다....








구조체 세그먼트 트리를 이용한다.
세그 먼트 트리를 생성하는데 노드를 구조체로 생성한다.

Node {
    long max, min, answer;
}

왼쪽 노드, 오른쪽 노드를 가지고 새로운 노드를 만든다.
왼쪽 노드를 L, 오른쪽 노드를 R 이라고 하겠다.
min = min(L.min, R.min)
max = max(L.max, R.max)
answer = max(L.answer, R.answer, R.max - L.min)

이런 식 으로 만들면 된다. 이 문제를 풀 수 있을 정도의 경지라면, 이런 개같은 설명도 바로 이해 된다.
분할 정복 세그먼트 트리 라고 볼 수 있겠다.

대회 때, 미친 짓을 해서 모든 테스트 케이스를 뚫어버렸다..



후기

저는 PS를 순수 알고리즘 구현이 재밌어서가 아닌, 인간이 지금까지 이륙해놓은 대단한 최적화 과정들을 이해하고, 문제를 풀었을 때, 희열을 느껴서 한 것 같습니다.
그래서, 티어가 많이 올려치기 당하긴 했습니다ㅋㅋ

플래티넘 티어 까지, 태그를 까고, 문제 풀이를 했고,
다이아가 되고 나서, 골드 이하는 태그를 안까고 푸는 연습을 조금 했습니다.

그래서, 푸는 속도가 다이아 유저분들에 비해, 느리긴 합니다...
확실히, 아직 5개월 밖에 되지 않았고, 다양한 경험을 해보며, 나날이 성장해야겠다고 생각합니다.

엄선된 어려운 문제들을 박치기 하면서 풀었던 기억이 새록새록 합니다. 그 덕분에, 정답률이 33퍼가 됬지만요 ㅎㅎ.

문제를 풀면서, 하루 이상이 걸린 문제도 있었고, 한달이 넘게 걸린 문제도 있습니다.
노력한 만큼 확실히 실력이 오른다고 생각합니다.
실력은 어느 한 시점으로 갑자기 오르니, 모두 노력하셨으면 좋겠습니다!


4시간 뿐인 대회였지만, 좋은 문제들과, 환경 덕분에, 실력이 체감 될 정도로 성장한 것 같습니다. 그 덕분인지, 그날 코포에서 어려운 문제를 쉽게 풀었더라고요!




이 진행을 맡아준, ANA 동아리 분들과, 학생회 분들 수고 많으셨습니다.

문제를 출제해주신 시온 선배 님에게 감사를 표합니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

백준 16748 Colorful Tree

이미지
  16748번: Colorful Tree (acmicpc.net) 오일러 투어 테크닉을 이용하여, 트리를 선형으로 핀다음, Map을 통해, 한 서브 트리가 가지는 특정 색깔의 갯수를 세그먼트 트리를 통해 O(log N)에 찾을 수 있다. 자바는 시간이 빠듯하여, 바텀업으로 하는 것을 추천한다. O(N(log N)^2)의 상수를 최대한 줄여야 한다. 여유? 그건 C++ 어떤 하나의 색깔이 추가 될 때, 트리를 최적화 하게 만들어 둔다고 했을 때, 추가 하는 색깔의 위치는, 그 전 색깔을 통해 만들어진 최적화 트리를 통해 만들어진 LCA의 서브 트리 아래에 종속 되어 있거나, 서브트리에 속하지 않는다 . 1. 서브트리 아래에 종속 되어 있을 때 1. 최적화 된 트리 안에 색을 추가하는 경우는 트리의 크기에 변화를 주지 않는다. 2. 최적화 된 트리 바깥에 색을 추가하는 경우는, 서브트리에서 색을 발견 할 때까지 거슬러 올라가, 거리를 더해준다. 2. 서브트리 바깥에 있을 때 1. 특정 노드의 서브트리 안에 색을 발견 할 때 까지 거슬러 올라가 거리를 더해준다.  그 지점이 색의 LCA를 서브트리로 가지고 있는 다면, LCA와의 거리도 더해준다. 특정 색깔의 LCA는 깊이가 가장 높은 노드부터, 루트 노드까지의 경로 선상에 존재하게 된다. 색깔의 LCA는 그 경로 선상에서 서브 트리가 특정 색깔을 모두 가지고 있는 노드 중, 제일 하위 노드이다. 이런 색깔의 LCA는 루트와 특정 색깔의 최하위 노드의 경로 선상에서 파라매트릭 서치를 하면 된다. 이 경우 파라매트릭을 하며, 세그먼트 트리 쿼리를 날리므로, O(log N) ^ 2 이다. 색을 발견 할 때 까지 거슬러 올라 가는 것도, 루트와의 경로에서, 파라매트릭 서치를 하며, 세그먼트 트리 쿼리를 날리면 된다. 색깔에 대한 트리의 크기 응답에는 O(1) 색깔을 바꾸는 데에는 O(log N ^ 2 )가 소요된다. 색깔을 없애는 방법은 그 위치에 대한 색깔정보를 없애 버리고, 새롭게 추가하려는 시도를 ...
자세한 내용 보기

볼록 껍질 알고리즘

이미지
플레티넘 이상의 문제에서 그리디 알고리즘이나 애드혹을 제외한 알고리즘들은 알고리즘을 구현하는 방법을 알고 있어도, 그 구현 자체와 개념 이해에 난이도가 붙는 방식이다. 즉 알고리즘을 알고 있을 때, 난이도가 플레티넘이라는 것이다. 플레티넘 이상 알고리즘 태그가 붙은 문제는 공부를 해야 풀 수 있다. 혼자서 푼다면, 대학원 가는 것을 추천한다. 그중 플레문제를 풀고 싶은 당신께 볼록껍질 알고리즘에 대해 소개해보자 한다. 정확히는 Graham Scan 알고리즘이다. 볼록 껍질 알고리즘이란, 좌표평면 상에 점의 집합이 구해졌을 때, 바깥 쪽 점들을 구하는 알고리즘이다. 이와 같이 나머지 점이 다 안쪽에 있는 다각형을 만드는 것이다. 내가 여기서 쓴 알고리즘은 꼭짓점을 구하는 알고리즘이다. 이해도가 높다면 개량하여, 모든 점을 구해보는 것도 시도해보는 것을 추천한다. class Point { int x, y; Point ( int x, int y) { this .x = x; this .y = y; } } 간단하게 CCW 를 구현 하여 보겠다. public static int CCW (Point a, Point b, Point c) { int g = (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y); return Integer. compare (g, 0 ) ; } 반시계 일때 -1, 시계 일때 1, 평행할 때 0 을 리턴한다. 점들을 정렬하여, 맨 왼쪽 아래 점을 찾자. 그 점(central)은 볼록다각형에 무조건 포함된다. 정렬을 해보겠다. Arrays.sort(points, new Comparator<Point>() { @Override public int compare (Point o1, Point o...
자세한 내용 보기