boj

[백준 2026] 소풍 (C++)

2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 백트래킹, 브루트 포스 소풍에 참여할 후보들을 nums배열에 차곡차곡 담아준다. 새로운 친구를 추가하려고 할 때 -> 새 친구는 지금까지 nums배열에 담긴 친구들과 모두 친구여야 한다. 이렇게 친구를 추가해 나가면서 nums배열의 길이가 K가 되면 지금까지 구한 친구들의 목록을 출력하고 exit한다. 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 ..

[백준 14284] 간선 이어가기 2 (C++)

14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 다익스트라 문제를 읽는 순간 s와 t를 연결하는 최소 간선? 하고 바로 스패닝 트리를 돌렸다. 근데 답이 안나온다. 예제 1번도 안나와서 이상해서 다시 읽어봤더니 다익스트라 문제인듯했다.. [백준 2211] 네트워크 복구 C++ 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회 hyeo..

[백준 14391] 종이 조각 (C++)

14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 백트래킹, 브루트 포스 [백준 1799] 비숍 C++ 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 hyeo-noo.tistory.com > N >> M; string str; for(int r = 0; r > str; for(int c = 0; c

[백준 2243] 사탕상자 (C++)

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 이 문제는 array값이 주어지지 않는다. 그럼 트리를 어떻게 만드는가? 사탕의 맛이 1부터 1,000,000 까지의 정수로 표현된다고 한다. 그래서 사탕의 맛을 트리의 인덱스(구간)로 설정하면 되고 사탕의 맛의 개수를 트리의 값으로 설정하면 풀 수 있다. [백준 1321] 군인 C++ 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주..

[백준 13308] 주유소 (C++)

13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 정점을 지나면서 지금까지 지나온 도시중 리터당 가격이 가장 싼 곳의 가격정보를 들고다니면 된다. 처음에 dist배열을 만들어주지 않고 전체 탐색을 하게해서 메모리초과를 띄웠다. pq에 중복된값이 엄청많이 들어간다고 생각했고 걸러줄 방법이 필요했는데 dp를 사용했다. 현재 정점까지 이동한 비용의 최솟값을 저장하는데 현재 정점에서 가지고 있는 리터당 가격정보도 같이 저장해야한다. dp[현재 정점][리터당 가격의..

[백준 11377] 열혈강호 3 (C++)

11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 최대 유량 최대 유량 연습하기 열혈 강호 1번 문제와 동일하지만 2가지 일을 할 수 있는 직원의 수가 주어진다. 처음에 무식하게 직원 중에서 k명을 반복해서 뽑고 S에서 해당 직원으로 가는 용량을 2로 두어 매번 에드몬드 카프 알고리즘을 돌려볼까 하는 생각을 했었다. 당연히 그렇게 풀면 안된다. S에서 직원으로 일을 할 수 있는 에너지를 보낸다고 생각했다. 그리고 S말고 다른 정점에서 직원들에게 K만큼의 에너지를 1씩 분..

[백준 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번째 수를 포함하고 ..