Algorithm

[백준 2517] 달리기 (C++)

2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 세그먼트 트리 최대 50만명의 선수들의 실력이 1부터 10억까지의 범위를 가지고 주어진다. 선수들의 등수는 상대적이므로 실력을 10억까지 되는수로 가지고 있을 필요가 없다. 정렬을 사용해서 선수들의 실력을 1~N까지의 수로 조정해준다. 그리고 주어진 선수들을 한명씩 세그먼트 트리에 넣으면서 자신보다 앞서 있지만 자신보다 실력이 낮은 선수의 수를 구한다. 세그먼트 트리의 구간은 선수들의 실력이 된다. 각 노드의 값은 해당 실력에 속한 선수들의 수가 된다. 트..

[백준 5527] 전구 장식 (C++)

5527번: 전구 장식 서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 www.acmicpc.net 다이나믹 프로그래밍 가만히 머리로만 생각할 때는 잘 떠오르지 않다가 손으로 패턴이 될 만한것들을 적다보니까 풀 수 있었다. 가장 긴 증가하는 부분 수열 문제와 비슷한 느낌을 받았다. 증가하는 부분수열의 크기를 구할 때와 비슷하게 연속해서 나타나는 교대 패턴의 최대 길이를 구했다. 1번 예제 : 1 1 0 0 1 0 1 1 1 0 연속해서 나타나는 패턴의 길이는 1 2 4 1 2 이렇게 구할 수 있다. 나뉘는 구간은 그림에 나타난다 나뉘는 구간이 3개가 있다면 두번째 ..

[백준 17142] 연구소 3 (C++)

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net BFS 삼성 SW 기출 BFS 시뮬레이션 문제! M은 최대 10개!! 바이러스도 최대 10개이므로 바이러스를 고를 수 있는 경우의 수는 최대 252개! -> 10C5 연구실의 최대 크기는 50x50 = 2500!! 252 * 2500 하면 약 60만개!! 0.25초 안에 해결하기 충분함! 바이러스를 고를 수 있는 경우의 수를 백트래킹을 통해서 구하고, 바이러스 M개를 고르면 고른 바이러스들을 가지고 bfs를 돌린다! 빈 칸에 도달한 경우에만 답을 갱신한다! -> 가장 마지..

[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍, 비트마스킹 [백준 13308] 주유소 (C++) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리 hyeo-noo.tistory.com 얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다 모든 행성이 서로 이..

[백준 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씩 분..