본문 바로가기

Algorithm

 (84)
[Two pointer] 백준 2003번 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 간단한 투포인터 문제이다. 정렬은 할필요없고, start, end 가 00부터 시작해서, sum과 타겟을 비교하면서 이동시키면된다. 다만 마지막 인덱스에 대해서는 조금 고민을해볼필요가 있다. 왜냐면 end가 index range를 벗어나게 되면 오류가 발생하기때문이지만 end가 마지막 지점에 있고 start를 줄여나가면서 탐색을 해야될 수도 있기 때문에, ..
[Two pointer] 2230백준 문제 풀이 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 해당 수고르기 문제에서는, 정렬을 사용하면된다. 문제 풀이는 크게 이렇다. left는 0 right는 맨마지막에 포인터를 둔다. 두수의 차이를 절대값으로 해서 비교를하고 taget보다 큰경우에 answer를 math.min으로 값을 업데이트해준다. 그리고 만약에 sum이 target보다 크다면, 정렬이 되어있으니 left를 하나 옮기는데, 여기서 right와 값이 같은 Inde..
[Two pointer] 3273번 문제풀이 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 전체 목록중에서 해당 하는 값의 쌍을 구하는 문제이다. 연속된 숫자에 대한 제약조건이 아니기 때문에, 우선 정렬을 한다. 정렬을 하고 left는 0 right는 끝에 두어서, sum과 비교, 작으면 left를 추가, 반대면 right를 추가하면서 값을 계산한다. 간단한 문제이다.
[Two pointer] 백준 2559번 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 백준 투포인터문제이다. 이중 for문을 돌면 10만개를 최대 10만번까지 돌 경우가 있기 때문에, 시간초과이다. 투포인터로 풀어야한다. 처음에, 초기값을 설정한다 (범위가 주어지기 때문에) 해당 기준으로 answer에 값을 넣고, right를 더하고, left를 빼주면서 sum과 answer를 비교해서 answer를 관리해준다. 굳이 범위 내의 전체를 더할필요없이, 기존에서 추가, 제..
[Binary Search] 백준 - 10816 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드에 대한 풀이 이다. 이 문제는 기존의 이분탐색 문제와 조금 다른 부분이 있다. 기존에는 값의 범위나, 배열의 범위를 통해서 단일의 값이나 정답을 구하는 문제였지만, 이 문제의 경우에는 한 배열에서 해당과 같은 값의 수를 구하는 것이다. 배열의 탐색, 정렬에 대한 특성 중 하나를 기억 해두자 그것은 바로, 정렬된 배열에서는 자신의 값과 유사하거나 같은 값..
[Binary Search] 백준 1764번 풀이 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 단순히, 두개의 배열에 모두 속하는 교집합 원소들을 뽑는 과정이다. hashset을 사용하여, 중복처리에 대한 이슈를 회피해주고 최종 적으로 contains으로 값을 잡아가 주면된다.
[Binary Search] 백준 1920 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이건 단순한 이분탐색이다.
[Binary Search] 백준 2110 풀이 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 공유기 설치 문제이다. 이전에 풀었던 레슨 문제와 유사하다. 범위를 구하고 이분탐색을 하면 끝이다. 말하면, 각각의 리스트들을 합하듯이, 앞에서 뒤의 집을 빼주면서 체크를 하고, 이분탐색의 mid 값보다 크다면, cnt를 증가, 반복문이 다돌면, answer보다 큰지 작은지 체크해서, 답에 update해주면 된다.

티스토리툴바