나그네

2568번: 전깃줄 - 2 문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 풀이 전깃줄 문제는 이어진 두 지점이 입력으로 들어오기 때문에 pair로 받아 저장한다. A 건물 기준으로 1번부터 이어야 하기 때문에 입력받은 값들을 정렬한다. 그리고 N의 크기가 10^5이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 14003번 문제와 같이 가장 긴 증가하는 ..

14003번: 가장 긴 증가하는 부분 수열 5 문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 그리고 N의 크기가 10^6이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 12015번 문제와 같이 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. 그러나 이 알고리즘으론 길이만 구할 수 있고 정확한 수열을 구할 수는 없기..

12738번: 가장 긴 증가하는 부분 수열 3 문제 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 12015번 가장 긴 증가하는 부분 수열 2 문제와 완전히 같은 알고리즘으로 풀 수 있다. 수열을 이루는 수의 크기에 변화가 있지만 int 범위 안이고 시간복잡도 자체에는 바뀔 부분이 없다. 12015번 해설은 아래 링크를 참고하자. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 ..

12015번: 가장 긴 증가하는 부분 수열 2 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 LIS 시리즈 문제 중 하나로 N의 범위가 10^5 이상인 문제에선 사용이 불가능한 시간복잡도가 O(N^2) 알고리즘으로는 풀리지 않는 문제다. 이분 탐색을 사용해 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀었다. 첫 번째 원소는 벡터에 넣어놓고, 다음 원소(편의상 x)부터 비교를 시작한다. 만약 x가 백터의 가장 뒤 원소보다 크다면..

15971번: 두 로봇 문제 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 풀이 동굴에서 두 점 A, B에서 각자 최소한으로 움직여 간선 하나를 남겨두고 마주할 수 있을 때 통신이 가능하다. 이때 최단 이동 거리를 구하는 문제다. 처음엔 bfs로 A에서 B까지 도달한 다음 B에서 다시 bfs를 시작해 최단 경로 위에서 B의 이동 거리와 B가 이제 갈 곳까지의 A의 이동 거리의 합이 최소인 것을 찾아줬으나 틀렸습니다를 받았다. 친구에게..

3111번: 검열 문제 https://www.acmicpc.net/problem/3111 3111번: 검열 첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다. www.acmicpc.net 풀이 문자열 T의 왼쪽에서부터 탐색해 문자열 A가 있으면 제거하고, 오른쪽부터 탐색해서 또 있으면 제거, 또다시 왼쪽, 오른쪽,... 반복하며 더 이상 그 문자열 A를 찾을 수 없을 때 남아있는 문자열을 출력하는 문제다. front, back이라는 덱을 2개 사용했다. front는 문자열 T의 앞에서부터 차례대로 넣는 컨테이너고, back은 뒤에서부터 넣는 컨테이너다. 즉, front는 push_back와 pop_bac..

14941번: 호기심 문제 https://www.acmicpc.net/problem/14941 14941번: 호기심 첫 줄에는 질문의 개수 n이 주어진다. 다음 줄 부터 차례대로 함수의 입력 a, b가 주어진다. (1 ≤ a ≤ b ≤ 105) 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다. 따라서 질문의 수 n은 최 www.acmicpc.net 풀이 a 이상 b 이하의 소수를 규칙에 따라 계산하는 간단한 문제다. 먼저 에라토스테네스의 체를 사용해 10^5보다 작은 소수를 걸러낸다. 소수를 하나하나 a보다 큰지 비교하다는 방법은 시간복잡도가 O(N)이고 10^5 이하의 소수는 약 41,000개 이상이고 테스트케이스의 수 N이 10^5이기 때문에 시간초과가 난다. 따라서 prime 배열은 이미 ..

17215번: 볼링 점수 계산 문제 https://www.acmicpc.net/problem/17215 17215번: 볼링 점수 계산 첫째 줄에 각 기회마다 소현이가 쓰러뜨린 볼링핀의 개수가 공백없이 주어진다. 이때 스트라이크는 S, 스페어는 P, 핀을 하나도 못 쓰러뜨린 것은 -으로 주어진다. www.acmicpc.net 풀이 시키는 대로 구현하는 문제다. 볼링에 대한 규칙을 아는 사람이라면 문제도 안 읽고 쉽게 풀 수 있을 것 같다. 문자열의 각 문자를 탐색하며 숫자일 경우 점수를 더하고, P(스페어)인 경우 (10 - 이전 투구에서 친 점수)를 추가하고 다음 투구의 점수도 더해준다. S(스트라이크)인 경우 10점을 추가하고 다음 두 번의 투구 점수를 함께 더해준다. 여기서 주의할 점은 10프레임에 ..

17071번: 숨바꼭질 5 문제 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다. 처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고..

1543번: 문서 검색 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 문서와 단어를 입력받아 문서 내에 단어를 중복되지 않게 몇 개 셀 수 있는지 구하는 문제다. 문서의 가장 처음 인덱스(0)부터 단어와 비교를 하고 다르면 다음 index로 넘어간다. 만약 단어를 찾으면 카운트를 증가시키고 다음 탐색할 문서의 위치를 현재 위치에서 단어의 길이만큼 더해준다. 코드 #include using namespace std; int main() {..