코학다식

안녕하세요. 오랜만의 알고리즘 포스팅입니다. 제가 방학이라고 공부 안 하고 놀아서 그렇습니다. (반성...) 이번 포스팅에서는 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에 대한 설명글에서도 나와 있지만, 이해를 돕기 위해 인접 행렬과 인접 리스트가 어떤 것인지 예를 들어 보자면 다음 사진과 같습니다. 인접 리스트는 존재하는 간선만 표현하지만 인접 행..

문제 링크 :: https://www.acmicpc.net/problem/10951 Solution 매우 간단한 문제입니다. 다만 테스트 케이스의 개수도 주어져 있지 않고 종료 조건도 명시되어 있지 않아 데이터를 더 이상 읽을 수 없음을 나타내는 EOF(End Of File, 콘솔에서는 ctrl+Z로 입력 가능)가 나올 때까지 데이터를 계속 입력받아야 합니다. 혹은 scanf가 반환하는 값이 2인 경우에만 반복문 블럭을 수행하도록 할 수도 있습니다. scanf는 포맷 형식의 수를 반환합니다. 에러가 발생하거나 EOF를 만나면 -1을 리턴합니다. Code 1 2 3 4 5 6 7 8 9 #include int main(void) { int a, b; while (scanf("%d %d", &a, &b) !..

안녕하세요. 이번 글에서는 기초적인 그래프 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이라는 주소를 주소창에 입력해도 백준 온라인 저지에 접속할 수 있습니다. 단계..