돌이 코딩하는 방

이번 글에서는 어떤 점이 도형의 내부에 있는지 판별하는 알고리즘을 설명하려고 한다. 엄청 많이 쓰이는 것도, 엄청 까다로운 것도 아니지만 나름 중요하며, 어쩌면 쉬어가는 타임으로 받아들일 수도 있다. 도형에서의 점의 내부 판별 들어본 사람은 들어봤을만한 문제이다. 꼭 정보가 아니어도 한 번쯤은 책이나 어디에선가 점이 도형의 내부에 있는지 외부에 있는지에 대해서 설명한 것을 봤을만하다. 점에서 외부로 선을 그었을 때 도형과 짝수번 만나면 외부, 홀수번 만나면 내부이다. 위의 그림에서 확인하고 싶은 점에 대해서 먼 점을 찍으면 그 둘을 이은 선분이 도형을 한 번 지나칠때 마다 내부와 외부가 바뀐다는 사실을 알 수 있다. 따라서 전 글에 나와있는 선분 교차 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다. 이..

이번 글부터 지금까지 공부한 기하 알고리즘들에 대해서 정리를 하고 넘어가려고 한다. 솔직히 나는 기하를 잘 못한다. 많은 사람들이 기하를 어려워 하지만, 나의 꼼꼼한 코딩을 잘 못한다는 약점이 기하의 어려운 점을 더 부각시킨다. 또한, 기본적으로 기하 알고리즘을 많이 알고 있지도 않다. 그래서 아는 기하 알고리즘들을 한 번 정리하고 넘어가려고 한다. 기하 알고리즘? 기하 문제를 푸는 데 쓰이는 알고리즘 들이다. n차원으로 나아가기도 하지만, 보통 좌표평면 상에서 이루어지며, 점, 선 ,도형들 간의 관계, 상태를 표현하는 알고리즘들이 많다. 기본적으로 수학에서의 기하의 지식이 있으면 전체적으로 도움이 될 수 있다. 기하 구현 모든 기하 문제는 일단 기본적으로 점을 잡고 시작한다. 보통 pair형을 사용하여..

이 글은 Segment Tree에 대한 이해가 어느정도 완벽히 되어있다고 가정하고 쓰는 글입니다. Top-Down 방식으로 구현이 되며, Top-Down 세그트리에 대한 이해가 부족하면 이 글을 먼저 읽는 것을 추천합니다. 예제 - 구간 합 구하기 2 링크는 https://www.acmicpc.net/problem/10999 이다. 이번에도 문제에 대해서 이야기 하면서 Lazy Propagation에 대해서 소개해보려고 한다. 이 문제에서 요구하는 사항은 두 가지 이다. 1. 배열 중 구간에 일정 값을 더한다 2. 배열의 구간의 합을 구한다. Segment Tree를 생각해보자. 2번 쿼리는 기존 Segment Tree에 존재하는 기능이다. 하지만 여기서 문제가 되는 것은 1번 쿼리이다. 기존의 방식으로..

한 번 배웠다하면 응용되는 부분도 엄청많고 정말 많은 문제에서 다양하게 사용되는 자료구조인 Segment Tree를 소개하려 한다. 예제 - 구간 합 구하기 1 링크는 https://www.acmicpc.net/problem/2042 다. 평소처럼 Segment Tree란? 으로 시작하지 않고 예제를 가지고 오며 시작한 이유는 간단하다. Segment Tree의 역할, 존재의의, 이점등을 가장 잘 설명할 수 있는 문제이기 때문이다. 워낙 유명한 문제인 만큼 풀린사람 수도 엄청나다는 것을 알 수 있다. Segment Tree를 알면서 이 문제를 모르기는 쉽지 않다. 이 문제에서 요구하는 사항은 두 가지다. 1. 배열의 값을 바꾼다. 2. 구간의 합을 구한다. 시간을 생각하지 않고 가장 쉽게 풀 수 있는 방..

Union & Find 란? 유니온 파인드 (Union & Find)는 Disjoint set으로도 불리는 일종의 자료구조이다. 그래프 문제에서도 그래프 문제가 아니어도 자주 등장하여 활용되어지는 친구이다. 보통 각 요소들을 묶어주고, 둘이 같은 그룹에 속해 있는지에 대한 판별등을 해줄 수 있고, 그러한 연산들이 필요할 때 사용되어진다. 기본 로직 소개 Union & Find 는 보통 두 개의 함수로 이루어져있다. 하나는 두 개의 요소를 받아서 두 개의 요소가 포함된 각각의 그룹을 묶어주는 함수이고, 하나는 하나의 요소를 받아서 그 요소의 조상을 알려주는 함수이다. 방금 조상이라는 표현에서 알 수 있듯이 한 그룹내에서 요소를 묶을때 상하관계가 존재하게 되며 한 그룹의 조상은 하나만 존재한다.. 또한 묶을..

이번에는 최소 스패닝 트리 (Minimum Spanning Tree 약칭 MST)에 대해 이야기 해보려고 한다. MST란? 최소 스패닝 트리로 스패닝 트리 중 간선의 가중치의 합이 최소인 트리이다. 그럼 스패닝 트리는 무엇일까? 그래프에 n개의 정점이 있을때 n-1개의 간선으로 모든 점을 이은 트리이다. 사이클이 존재하지 않으며, 임의의 두 정점에 대해서 이동할 수 있는 경로가 유일하다. 다시 말하자면 그래프에서 n-1개의 간선을 뽑아내 사이클이 없는 트리를 완성하고 이때의 간선의 가중치의 합이 최소이면 이를 최소 스패닝 트리, 즉 MST라고 한다. MST를 구하는 방법 그래프에서 MST를 구하는 방법에는 크게 두가지가 있다. 바로 크루스칼 알고리즘과 프림 알고리즘이다. 둘 다 그리디를 기반으로 하고 있..

이번에 그래프 관련 알고리즘 다익스트라 (dijkstra) 를 들고 오게 되었다. 우리가 앞으로 그래프 문제를 많이 보게 될 텐데, 그래프 문제에서 가장 많이 다루게 되는 요소가 무엇일까? 바로 거리일 것이다. 가장 짧은 거리, 가장 짧은 거리의 경로, 임의의 두 노드 사이의 거리 등 정말 다양한 거리들을 알아야 할 필요성이 앞으로 생기게 된다. 다익스트라는 그 중 한 노드에서부터 모든 노드까지의 각각의 거리를 알아내고 싶을 때 사용되어진다. 어느정도 bfs랑 비슷한 느낌일 수 있다. bfs를 할 때는 queue의 맨 앞 노드에서 도달할 수 있는 모든 노드를 다시 queue에 넣어 탐색을 한다. 다익스트라는 도달할 수 있는 노드 중 기준노드로부터 가장 가까운 점을 뽑아 그 점을 거쳐 도달할 수 있는 다른..

BFS 와 DFS는 정말 노드와 간선이 있으면 어디에서든 쓰일 여지가 있는 알고리즘이다. 정확히 말하자면 탐색방법이다. BFS는 Breadth First Search의 약자로 한국어로는 넓이 우선 탐색이다. 말 그대로 넓이를 우선시 하는 탐색 방법이다. DFS는 Depth First Search의 약자로 한국어로는 깊이 우선 탐색이다. 역시 말 그대로 깊이를 우선시 하는 탐색 방법이다. BFS 와 DFS를 처음 공부할때는 뉴비인 경우가 많기 때문에 보통은 바로 트리나 그래프를 그리기 전에 예시를 든다. 보통은 이러한 예시를 든다. '우리가 만약 넓고 좋은 새 집을 보러간다고 하자. BFS는 처음 들어선 거실에서 연결된 방을 다 가보는 것이다. 여러 방들을 둘러보면, 그제서야 보았던 방 중 하나를 기억해서..

그때는 시간이 없었는데 이제는 진짜로 필요성을 느꼈다. 내가 이러한 꾸준한 관리를 정말 못하고 작심삼일이 되는 경우가 정말 많은데 그러한 습관을 고칠수도 있는 좋은 기회라고 시작한다. 전체적인 글의 순서는 지금까지 내가 PS를 하면서 배워왔던 발자취를 따라가면서 내가 배웠던 순서를 어느정도 따를 것 같다. 복기 를 하며 어떤 알고리즘에 대한 내 코드를 확정지을 것 같다. 또한, 아마도 복기를 하며 알고리즘과 관련된 문제도 같이 포스팅 할 것이다. 그러면 망해가던 블로그도 어느정도 살려낼 수 있지 않을까? *여담: 필자는 1-base만 쓰기 때문에 1번글인 지금부터 진짜 시작이다.