코학다식

문제 링크 :: https://www.acmicpc.net/problem/1806 Solution 문제 이름처럼 부분 합을 이용해서 푸는 문제. 그래서 일단 sum 배열에 부분 합을 구해 줬다. 그리고 나서는 어떻게 시간 초과가 나지 않으면서 합이 S 이상인 구간 합 중 가장 길이가 짧은 것을 구하느냐가 관건이었다. 다른 사람들은 어떻게 풀었는지 모르겠지만 나는 S 이상의 부분 합이 나타나는 부분 합을 발견하면 그 인덱스를 기준으로 가장 짧은 구간 합(j가 i-1인 경우)부터 계산하면서 그 값이 S 이상이 되면 정답 후보 배열(sol)에 길이를 저장해 주도록 했다. 가장 짧은 구간 합부터 구하니까 S 이상인 값을 발견하면 바로 반복문을 탈출한다. 만약 가장 짧은 구간 합이 S 이상이면 굳이 나머지 구간 ..

문제 링크 :: 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까지의 부분 합을 구해야 합니다. 이런 사소한 부분에서 실수가 나면 은근 알아차리기 어렵더라구요...

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

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