나그네

1806번: 부분합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 부분합이 S 이상인 부분합 중 길이가 가장 작은 것의 길이를 구하는 문제다. 시간복잡도가 O(N^2)인 알고리즘으로 풀면 시간 초과를 받는다. 따라서 O(N)인 알고리즘으로 풀어야 한다. 그중 하나가 투 포인터를 사용해서 푸는 방법이다. left와 right를 모두 0으로 두고 sum = v[0]으로 초기값을 설정한다. 합(sum)은 인덱스가 left부..

1545번: 안티 팰린드롬 문제 https://www.acmicpc.net/problem/1545 1545번: 안티 팰린드롬 만약 어떤 문자열 P가 있을 때, P[i]와 P[n-i-1] (0 ≤ i

17609번: 회문 문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 문자열을 입력받아 이 문자열이 회문인지, 유사 회문인지, 둘 다 아닌지를 판단하여 각 0, 1, 2를 출력하는 문제다. 여기서 유사 회문이란 문자열에서 한 글자를 제거하여 회문이 되는 문자열을 말한다. 투 포인터(two pointer)를 사용해 풀었다. 문자열을 s라 하면, left는 0번 index부터 차례로 증가, right는 문자열의 마지막 문자 index부터 차례로 감소하며 left < r..