코학다식

안녕하세요. 오랜만의 알고리즘 포스팅입니다. 제가 방학이라고 공부 안 하고 놀아서 그렇습니다. (반성...) 이번 포스팅에서는 Prefix sum(구간 합)에 대해 알아보도록 하겠습니다. 아주 간단하지만 유용한 알고리즘입니다. Prefix sum? 영어로는 이게 뭐지 싶지만 한글로 보면 의미를 대충 짐작하실 수 있을 겁니다. 구간 합이란 말 그대로 수들의 나열에서 특정 구간의 합을 의미합니다. 이와 비슷한 개념으로 부분 합이 있습니다. 부분 합은 구간 합과 달리 처음부터 특정 인덱스까지의 합을 의미합니다. 구간 합에서의 구간은 당연히 어느 구간이든 가능합니다. 처음부터 끝까지일 수도 있고, 세 번째에서 일곱 번째일 수도 있고, 마지막 숫자만일 수도 있겠습니다. 예를 들어 볼까요? 1 2 3 4 5 6 7..

문제 링크 :: https://www.acmicpc.net/problem/1260 Solution 전형적인 DFS, BFS 문제입니다. DFS와 BFS에 대한 설명은 아래의 관련 글 링크에서 보실 수 있습니다. DFS와 BFS 알고리즘에 더해 알아야 할 것이 하나 더 있습니다. 바로 그래프의 표현 방법인데요. 보통 가장 많이 사용되는 방법은 2차원 배열로 구성된 인접 행렬(Adjacency matrix)이나 링크드 리스트(linked list)로 구현한 인접 리스트(Adjacency list)입니다. 제가 쓴 DFS와 BFS에 대한 설명글에서도 나와 있지만, 이해를 돕기 위해 인접 행렬과 인접 리스트가 어떤 것인지 예를 들어 보자면 다음 사진과 같습니다. 인접 리스트는 존재하는 간선만 표현하지만 인접 행..

안녕하세요. 이번 글에서는 기초적인 그래프 operation인 DFS와 BFS에 대해 알아보도록 하겠습니다. 본격적으로 DFS와 BFS에 대해 알아보기에 앞서, 먼저 그래프에 대해 간략하게 알아보도록 하겠습니다. 그래프와 DFS, BFS에 대한 설명은 Fundamentals of data structures in C 2nd edition의 설명을 참고하였습니다. 예제 코드는 C언어를 사용합니다. Graph 그래프[G]는 자료구조의 일종으로 두 집합으로 이루어져 있습니다. 유한한, 그러면서 빈 집합이 아닌 정점들의 집합[V(G)]과 정점들의 쌍인 간선들의 집합[E(G)]이 그래프를 이루어는 두 집합입니다. 참고로 context에 따라 차이가 있으나 대부분 정점이 존재하면서 간선이 없는 그래프도 그래프로 취..

알고리즘 문제 풀이 사이트를 모아 보았습니다. 새롭게 알게 되는 사이트가 있으면 계속 추가될 예정입니다. 프로그래밍 대회 참가보다는 알고리즘 공부에 주안점을 둔 분들(저 포함)을 위한 글이므로 Topcoder, Codeforces 등 대회 참가 목적에 보다 적합한 사이트들은 제외되었습니다. 1. 백준 온라인 저지(https://www.acmicpc.net/) 첫 번째는 많은 분들이 알고 계실 백준 온라인 저지입니다. 다양한 프로그래밍 대회들의 많은 문제들이 올라와 있는 한글 사이트입니다. 대표자이신 최백준 님이 강의도 진행하시는 걸로 아는데, 안 들어 봐서 어떤지는 잘 모르겠습니다. 별로 도움이 되는 정보는 아니지만 noj.am이라는 주소를 주소창에 입력해도 백준 온라인 저지에 접속할 수 있습니다. 단계..