알고리즘 일지

 나는, 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...