충남대학교 컴퓨터융합학부 1학년을 마치며

 수고하셨습니다. 어느덧, 잎은 떨어지고, 추운 한파가 몰아치는 겨울이 되었네요. 신입생이 되어, 학교를 거닐고, 막동에 앉아, 술이랑 치킨을 시켜 먹던 때가 엊그제 같은데요... 12월 20일, 저는 오늘 인공지능과 미래 사회 마지막 시험을 치고, 기숙사 퇴거를 한 뒤, 집에 와서 바로 글을 쓰고 있습니다. 글을 빨리 쓰는 이유는 이제 곧 사라지는 많은 동기들이, 글을 보고 군대를 들어갔으면 좋겠다는 마음에서 빨리 쓰게 되었습니다. 아버지의 차를 타고 전주를 오며, 지난 1년을 되새겨 보았는데요, 정말 많은 변화를 맞이 한 것 같습니다. 되돌아 보니, 공부를 너무 열심히 한 것 같습니다. 동기들과 술판을 더 벌이거나, 그냥 다 밀어두고 백준만 하는게 더 정신건강에 좋았었을 거 같은데... 둘 다 하려고 하니까, 코피쏟고, 저체중에서 체중 더 빠지고 그런 것 같습니다. 중요한 건 휴식과 체력이 맞는 말 같습니다. 매일 하루 종일 백준 풀고, 자기 전 까지 풀고, 눈감고 풀이 방법 떠올리다가 자면, 꿈에서도 복습하는 꿈을 꾼 다음에, 일어나면, 정말 정신병 걸린 사람처럼, 잠을 못 깨고, 몇 분 동안 그동안 배운 알고리즘이 몰아쳐서 생각이 마비 되는 경험을 합니다. 그래서 병원을 한번 갔었습니다 ㅋㅋ (비타민 부족) 1학기 에는 동기들이랑 좀 많이 다녔고, 2학기 에는 동아리 방에만 박혀있던 것 같네요. 1학기때, 5시간씩 자면서 공부했는데, 2학기 되고 나선, 거만해지고, 게을러져서, 백준만 하고, 공부도 좀 게을리했던 것 같습니다 ㅋㅋ 꿈이 없던 제가 하고 싶은 게 생겼고, 수능을 보던 고3 때보다 더 열심히 무언가에 시간을 쏟아 본 것 같습니다. 또, 철판 깔고 남에게 먼저 선뜻 다가가는 것도, 좋은 동기들이랑 개드립을 서로 나눌 정도로 친해지는 것도, 대회에서 1위를 하는 것도, 전액 장학금을 받는 것도 제가 될 줄 몰랐습니다. 알고리즘으로 저를 밀어 넣은 배인수22 씨에게 감사의 말씀을 드립니다. 항상, 게임만 하며, 게임을 잘 하는 것만이 저의 인생의

내가 배운 알고리즘 정리

이론은  기울임  표시가 있다. 2022 / 10 / 28. 수정이 안되어, 한번 더 올림. 아래 알고리즘은 전부 독학으로 익혔고, 배우다 보니 몇개는 까먹음. 그래프 그래프 이론은, 기본적인 DFS / BFS 를 기반으로 시작한다. 이분 그래프 NetWorkFlow, 네트워크 플로우 / 최대유량 문제 Edmonds-Karp Algorithm, 애드몬드-카프 알고리즘 Ford-Fulkerson Algorithm, 포드-풀커슨 알고리즘 Dinic Algorithm, 디닉 알고리즘 Bipartite Matching, 이분 매칭 알고리즘 Minimum Vertex Cover 최소 버텍스 커버 /  Kőnig's Theorem 쾨닉의 정리 MCMF 최소 비용 최대 유량 문제 그래프 Dijkstra, 다익스트라 알고리즘 / 최단거리 Union Find, 유니온 파인드 Union by Path Compression, O(N) / 경로압축을 통한 구현 Union by Rank Compression, (height on log N) O(N log N)  Floyd Warshall Algorithm, 플로이드-워셜 알고리즘 / 최단거리 위상 정렬 Strongly Connected Components (SCC), 강한 연결 이론 2 - SAT 트리 SparseTable, 희소배열 Heavy-Light-Decomposition, HLD (세그먼트 트리 응용 필요) Splay Tree, 스플레이 트리 Link-Cut-tree, 응애컷 트리 Divide on Centroid Decomposition and Conquer Lowest Common Ancestor (LCA) 최소 공통 조상 Kruskal Algorithm, 크루스칼 알고리즘 오일러 경로 투어 테크닉 트리에서의 파라매트릭 서치 자료구조 HashSet / HashMap LinkedList, Queue, Deque, Stack 값 / 좌표 압축 Segment Tree (왕도가 없다.) Lichao Tree, 리차오 트

백준 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 )가 소요된다. 색깔을 없애는 방법은 그 위치에 대한 색깔정보를 없애 버리고, 새롭게 추가하려는 시도를 한다. 그 때,

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

이미지
 나는, 22학년도 충남대 컴융 신입생이다. 초반엔 극히, 평범한 학생이었고, 술마시고 게임만 하는 페인의 삶을 살았다.  TMI.1 지금은 PS페인이다. TMI.2 FPS만 극한으로 파던 사람이다. 4월 쯤인가? 학교 코딩 테스트에서, 간단한 별 찍기 문제가 나왔다. 그 문제에서, 너무 괴로웠고, 쉽게 하는 친구들을 보며, 자괴감이 들었다. 그 후, 만난 컴융 친구들 중, 배인수 (사인은 PS로 인한 혈압사)라는 친구가 백준을 하고 있고, 실버를 찍은 것을 보여주었다. 별 찍기 같은 문제들을 잘 풀고 싶은 마음도 있었고, 친구가 실버를 찍은 것을 보니 나도 백준을 하고 싶었고, 기숙사에 들어가자 마자, 백준에 들어가 문제를 미친듯이 풀기 시작했다. 이게 PS페인의 시작이었다.. 그리고 5개월 후... SW - IT 콘테스트가 열렸다. 나는 그래도 나름 고인물이 되어있고, 개같이 신청을 넣었다. 그리고 본 대회에서 9솔을 했다. 솔직히, 시간이 있으면 충분히 다 풀지만, 대회라서 긴장하고 있었고, 시간도 촉박 하다는 압박감, 그리고 초반에 실수를 너무 많이 해서, 아래서 올라오는 순위에도 정신이 너무 팔려 있었다. 실제로 대회에서, 했던 생각을 바탕으로, 간단한 문제 해설과, 문제 리뷰를 해보겠다. 진짜 아주 간단하게 해설을 썻으니, 한번 쓱 보고 문제를 푸는 것을 추천한다. 혹여나, 대회에서 기대 이하의 성과를 이룬 사람들은, 노력해서, 다음에 목표한 성과를 이루길 기원한다!! Division 1 내용만 다룬다. 2022 충남대학교 SW-IT Contest - Division 1 (acmicpc.net) 25628번: 햄버거 만들기 (acmicpc.net) min(빵 / 2, 패티) 가 정답이다. (정수 연산이다) 실제로 대회에서도, 여기까지 생각하고, 아무 생각없이 제출하고 다음문제로 넘어갔다. 25629번: 홀짝 수열 (acmicpc.net) 홀수는 홀수 칸에, 짝수는 짝수 칸에 있어야 한다.  홀수의 개수와, 짝수의 개수, 총 칸의 길이를 적절하게 잘

볼록 껍질 알고리즘

이미지
플레티넘 이상의 문제에서 그리디 알고리즘이나 애드혹을 제외한 알고리즘들은 알고리즘을 구현하는 방법을 알고 있어도, 그 구현 자체와 개념 이해에 난이도가 붙는 방식이다. 즉 알고리즘을 알고 있을 때, 난이도가 플레티넘이라는 것이다. 플레티넘 이상 알고리즘 태그가 붙은 문제는 공부를 해야 풀 수 있다. 혼자서 푼다면, 대학원 가는 것을 추천한다. 그중 플레문제를 풀고 싶은 당신께 볼록껍질 알고리즘에 대해 소개해보자 한다. 정확히는 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