코학다식

문제 링크 :: https://www.acmicpc.net/problem/14648 Solution Prefix sum 알고리즘으로 쉽게 해결할 수 있는 문제입니다. 관련 설명은 아래 링크에서 보실 수 있습니다. 그런데 한 가지 주의해야 할 점이 있습니다. [a, b] 구간의 합을 구하기 위해서 b까지의 부분 합과 a-1까지의 부분합을 알아야 하는데, 편의상 배열의 크기를 (n이 최대 1000이므로) 1001로 선언해 두고 첫 번째 요소의 인덱스가 1이 되도록 코드를 작성하는 경우에는 그대로 b와 a-1까지의 부분 합을 사용해서 구간 합을 구하면 되지만, 첫 번째 요소의 인덱스가 0인 경우에는 b-1과 a-2까지의 부분 합을 구해야 합니다. 이런 사소한 부분에서 실수가 나면 은근 알아차리기 어렵더라구요...

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

안녕하세요. 이번 포스팅에서는 코딩, 프로그래밍, 컴퓨터공학 관련 강의 사이트들을 모아 보았습니다. 여러 이유로 코딩을 배우고자 하는 사람들이 점점 늘어나고, 현재 온라인 여기저기서 많은 강의들을 유/무료로 제공하고 있죠. 공부할 리소스가 넘쳐나지만 아무것도 모르는 상태에서는 이렇게 많은 정보 속에서 어떤 것을 선택해야 좋을지 혼란스럽기도 합니다. 그래서 제 경험과 주변 분들, 코딩 관련 커뮤니티 등을 보았을 때 좋은 평을 받고 있는 온라인 강의 사이트를 소개해 보려고 합니다. 전부 무료인 곳도 있고, 유/무료 강의 모두 제공하는 곳도 있습니다. 유료로만 강의를 제공하는 곳은 제외하였습니다. 어떤 곳이든 선택하셨다면 같이 차근차근 열심히 공부해 보아요! 1. 생활코딩(https://www.opentuto..

문제 링크 :: 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) !..

안녕하세요. 오늘은 웹 사이트에 소스 코드를 예쁘게, 보기 좋게 올리는 방법에 대해서 알아보려고 합니다. 저번 포스팅에서 사용한 티스토리에 기본으로 있는 코드블럭이 너무 안 예뻐서 쓰는 포스팅입니다. 웹 사이트에 소스 코드를 올리고 싶을 때 코드를 그대로 복붙 해서 올리면 들여쓰기도 엉망이 되는 경우가 많고, 텍스트 에디터들처럼 깔끔하고 문법이 강조된 채로 올릴 수도 없죠. 그럴 때 syntax highlighter, 혹은 color scripter를 사용하면 소스 코드를 보기 좋게 올릴 수 있습니다. Syntax Highlighter 먼저 syntax highlighter의 사용법에 대해 알아보도록 하겠습니다. Syntax Highlighter v3.0.83 파일을 CDN로 이용하여 설치하고 사용하는 ..

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