https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 중간에서 만나는 투 포인터를 이용하여 문제를 해결했다. 입력받은 물건을 반으로 나눠서 앞쪽 물건들을 이용해 만들 수 있는 모든합과, 뒤쪽 물건들을 이용해 만들 수 있는 모든합을 구해서(이때 합이 c가 넘어가는 것은 넣지 않는다) 각각 정렬한 뒤, 앞쪽 물건들을 이용해 만들 수 있는 모든 합은 앞쪽에서 뒤쪽 물건들로 만들 수 있는 모든 합은 뒤쪽에서 시작하여 중간에서 만나는 투 포인터를 이용해..

https://www.acmicpc.net/problem/16934 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, www.acmicpc.net 트라이 자료구조를 이용해서 문제를 해결했다. 노드에는 해당 노드에서 끝나는 문자열의 개수, 해당 노드에서 나아가는 알파벳별 개수를 저장하여 확인을 할 때 해당 노드에서 끝나는 문자열의 개수를 통해 같은 닉네임으로 가입한 사람의 수를 계산하거나, 알파벳별 개수를 통해 해당 접두사가 이전에 가입한 닉네임의 접두사와 겹치지 않을 때인지를 확인하여 문제를 해결했다. 코드 #include #..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘을 이용하여 문제를 해결했다. 시작점에서 도착점으로 가는 최단경로를 통해 해당 경로에 속하는 길들을 저장한 뒤, 체크해 두었고, 다시 시작점에서 도착점으로 가는 다익스트라 알고리즘을 사용하는데 이때 체크해둔 길로는 이동하지 못하도록 하는 방법을 통해 문제를 해결했다. 코드 #include #include #include #include using n..

https://www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net 유니온 파인드를 활용해서 문제를 해결했다. vector basket(300001, 0);에는 해당 서랍에 술이 들어 있는지 비어있는지를 나타냈다. 해당 술이 들어가고 난 뒤 해당 서랍에서 나중에 옮겨질 수 있는 서랍 쪽으로 유니온을 하고, 파인드를 통해 특정 서랍에 있는 술을 다른 서랍으로 옮길 수 있는지 확인하는 방법으로 문제를 해결했다. 코드 #include #inc..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리를 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n, m; vector number; vector sgmtt; vector result; int Make_sgmtt(int here, int index_left, int index_right) { if (index_left..

https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net dvd 벡터에 처음 m 개는 꺼내고 다시 올려놓을 곳으로 비워놓고(0을 넣어 놓고) 그다음 n개의 영화를 놓는 것으로(1을 넣어 놓는다) dvd의 초기 상태를 나타낸다. [영화 번호] = dvd 벡터의 어느 인덱스에 있는지를 나타내는 movie_index를 통해 어떤 영화가 dvd 벡터의 어떤 인덱스에 있는지 나타내고, dvd 벡터의 상태를 세그먼트 트리로 나타낸다. 그리고 영화 번호를 입..