Algorithm

[백준 2159] 케익 배달 (C++)

2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 다익스트라 주문이 들어온 순서대로 배달한다는 게 문제의 핵심. 별이 시작점이다. 여러 최단거리 중 임의로 하나를 잡으면 위와 같은 경로가 생긴다. 처음에 다익스트라인 줄 모르고 3번 케이크에서 2, 1번 순으로 이동시키며 가장 짧은 거리만 찾아 그리디 하게 탐색할까 생각했었는데 이 문제와는 전혀 어울리지 않는 알고리즘이었다. 현재 위치한 지점의 고객번호와, 지금까지 이동한 거리, 현재 위치를 저장하고 있는 구조체를 만들어주었다. 그리고 일반적인 다익..

[백준 10999] 구간 합 구하기 2 (C++)

10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리, Lazy propagation 처음에 그냥 세그먼트 트리를 사용했다. 구간을 update할 때마다 리프노드까지 들어가서 update하고, 되돌아오면서 update값을 더해서 tree에 적용해줬다. 제출하면서도 매우 찝찝했다. 값을 수정하는 구간이 1~N까지라면 값을 update하는데 N의 시간이 걸리게 될 것이다.. 구간합을 찾는 쿼리는 log(N)이라서 둘을 더하면 O(NM + K..

[백준 1701] Cubeditor (C++)

1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP 문자열의 길이가 5,000이라서 O(N^2) 시간이 가능하다. kmp알고리즘은 text문자열과 pattern문자열이 주어지고, pattern문자열에서 text 문자열의 접두사가 몇 번 나오는지, 나올때마다 접두사의 몇 번째 문자열까지 나오는지 알 수 있다. text문자열을 pattern으로 써서 일명 jump table 이라고 하는걸 만들 수 있는데 jump table의 특성을 생각해보면 문제를 해결할 수 있다. 위 ..

[백준 1275] 커피숍2 (C++)

1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 세그먼트 트리 [백준 11505] 구간 곱 구하기 (C++) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고. hyeo-noo.tistory.com 위 문제와 똑같은 문제이다. a번째수를 b로 바꾸어야 하므로 a번째 수를 포함하고 ..

[백준 9019] DSLR (C++)

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 이미 찾아 본 숫자라면 que에 넣지않도록해서 최대 10000번만 bfs를 수행하도록 했다. 메모이제이션 안하면 4^n 의 시간복잡도로 시간초과가 난다. D S L R 연산을 조심하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..

[백준 2188] 축사 배정 (C++)

2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 최대 유량 주어진 입력을 그래프로 나타내 보았다. 소는 자신이 원하는 축사로만 이동할 수 있음을 나타냈다. 축사에는 소를 1마리만 들일 수 있으므로 축사에서 목적지로 1마리만 보낼 수 있다고 생각해도 무방하다. 위 그래프의 정점의 개수는 12개이다. 시작점이 0번, 끝점이 1번. 소들은 2번부터 6번까지, 축사는 7번부터 11번의 번호를 가지게 된다. 그래프는 단방향 그래프지만 음수 유량을 통해서 유량 상쇄를 구현하기 위해서 그래프는 모두 양방향으로 연결해 준다. ..

[백준 11505] 구간 곱 구하기 (C++)

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 구간의 곱을 구하는 문제라서 0을 신경써줘야 한다. 구간 합을 update할 때는 update값이 마이너스로 들어와서 부모부터 갱신이 가능했다. 하지만 곱을 update할 때는 안된다. 예를 들어서 3번째 수를 6으로 바꾸려고 하고 현재 3번째 수가 0인 경우를 생각해보자 구간 합을 구할 때와 조금 다르게 리프노드부터 업데이트해 나가면 편하다 3번째 수에 도달하면 (항상 리프노드일 것임)..

[백준 1305] 광고 C++

1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net KMP 15분 정도 뚫어져라 본 결과 규칙을 찾았다. 문자열의 마지막이 접두사와 중복된 채로 끝난다면 해당 중복 문자열의 길이만큼 광고 문자열을 감소시킬 수 있다. babba 라는 문자열이 주어졌다고 가정. 접두사 table을 만들어보자 table = {0, 0, 1, 1, 2} 테이블의 마지막 값이 2이므로 해당 문자열은 마지막 2개가 중복된다고 볼 수 있다. 따라서 문자열의 길이 5에서 중복 문자열 2개를 제외한 3개가 답이 된다. -> bab 다음 광고가 중복되는 부분부터 ..

[백준 1786] 찾기 C++

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 어젯밤부터 이해하는데 어려움을 느꼈던 알고리즘 기본 kmp문제를 보니 대놓고 알고리즘을 설명해주고 있다. 더보기 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할..

[백준 4013] ATM C++

4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 강한 연결 요소, 다이나믹 프로그래밍 처음 풀어보는 플레2 문제였다. 풀려서 기분이 매우 좋았음 우선 모든 정점들을 dfs로 순회하며 각 정점의 SCC를 구해줬다. SCC를 구하면서 해당 SCC에 속하는 현금의 양 + 해당 SCC에 레스토랑이 있는지 판단해 주었다. 구한 SCC를 통해서 SCC 그래프를 만들어 주었다. -> make_sccgraph() 이제 DP문제로 바뀌게 되었다. 시작점의 SCC에서 출발해, 레스토랑이 있는 SCC까지의 거리의 ..