boj

[백준 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까지의 거리의 ..

[백준 1321] 군인 C++

1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그먼트 트리 10개월 만에 다시 풀어보는 세그먼트 트리문제이다. 우선 a ~ b 구간의 부대의 인원의 합을 하나의 노드로 잡고 세그먼트 트리를 만들었다. 특정 부대의 증원이나 감원을 할 때는 업데이트 쿼리를 만들어서 수행했다. ex) 2번 부대의 인원이 늘어났다면 1-5번, 1-3번, 2번 노드의 인원이 모두 같은 수 만큼 증가해야 한다. 마지막으로 군인을 배치하는 arrangement쿼리를 만들었다. 군인의 번호가 왼쪽 자식 노드의 최대 인원보..

[백준 1944] 복제 로봇 C++

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 - MST 현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다. 전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다. 입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다. 정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다. BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 ..

[백준 2262] 토너먼트 만들기 C++

2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 그리디 랭킹이 높은 사람이 반드시 이기기 때문에 우승자는 항상 1번이다. 부전승이 여러번 있어도 상관없기 때문에 매번 가장 랭킹이 낮은 사람(번호가 높은 사람)만 경기를 하게 했다. 랭킹이 가장 낮은 사람(자신)의 양 옆 사람 중에서 자신과 랭크 차이가 적게 나는 사람과 경기를 치러야 한다. 랭크 차이가 많이 나는 사람과 경기를 치르게 되면 그 사람은 랭크차이가 많이 나는 만큼 경기를 더 많이 치러야 하기 때문이다. 경기를 더 많이 한다면 그만큼 최솟값과는 멀어질 수..

[백준 2211] 네트워크 복구 C++

2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라 최소 스패닝 트리의 탈을 쓴 다익스트라 문제였다. 끊어진 그래프에서 최소 개수의 회선만을 복구해야 한다고 하길래 n-1개의 간선을 연결시켜서 모든 컴퓨터를 연결해 주는 MST 문제로 착각했다. 위 그래프에서 MST는 어떻게 될지 생각해보자 2-3, 2-4, 1-3 간선이 모여서 MST를 이룰 수 있다. 하지만 이 때 1 -> 2로가는 비용은 5가 되고, 1 -> 4로 가는 비용은 7이 된다. 각각 기존의 최단거리였던 4, 3..