[Algorithm] 2-SUM 알고리즘

2-SUM 알고리즘은 target숫자가 존재할 때 배열의 원소들을 이용해서 target과 가장 근접한 조합을 찾아내는데 사용하는 알고리즘이다.

 

가장 먼저 이러한 문제 해결을 위해서는 정렬이 필요하다.

 

 

 

0. 정렬

원소들을 이용해서 근접한 값, 타겟 값등을 찾는데는 배열을 우선 정렬을 진행해야 한다.

 

 

 

 

1. pointer 이용

배열을 접근할 때 2개의 포인터를 가지고 접근한다.

가장 먼저 pointer1, pointer2가 제일 작은 숫자를 가리키게 되고 pointer2를 한칸씩 늘려가며 원소들이 합을 target값과 비교한다.

 

target = 8 arr[] = {1, 5, 12, 4, 9, 3, 6, 2}

위와 같은 배열이 존재하고 target값이 존재할 때 배열의 2가지 값을 선택해서 target보다 크지않으면서 가장 가까운 숫자를 만든다면 어떤 숫자 2개를 선택해야 하는가?

 

먼저 arr의 정렬을 진행하면

arr[] = {1, 2, 3, 4, 5, 6, 9, 12}

가 된다.

 

그리고 여기서 pointer1, pointer2가 1을 가리키게 된다.

arr[pointer1] + arr[pointer2] 값이 target보다 작다면 pointer2를 한칸 씩 늘려가고 만약에 target보다 크다면 pointer2는 다시 제자리로 돌아오고 pointer1값을 한칸 움직인다.

 

pointer1 = 1	pointer2 = 2	3
pointer1 = 1	pointer2 = 3	4
pointer1 = 1	pointer2 = 4	5
pointer1 = 1	pointer2 = 5	6
pointer1 = 1	pointer2 = 6	7
pointer1 = 1	pointer2 = 9	10
pointer1 = 2	pointer2 = 6	8

 

위와 같이 2-SUM알고리즘을 통해서 문제 해결이 가능하다.

 

 

 

 

 

 

2. 알고리즘 문제

https://leetcode.com/problems/two-sum/submissions/

#include <algorithm> #include <map> class Solution { public:     vector<int> twoSum(vector<int>& nums, int target) {         map<int,vector<int>> indexHash;         for (int i=0; i< nums.size(); i++) {             indexHash[nums.at(i)].push_back(i);         }         sort(nums.begin(),nums.end());         int pt1 = 0, pt2 = nums.size()-1;         vector<int> answer;                 while (pt1 < pt2) {             if (nums.at(pt1)+nums.at(pt2) < target) {                 pt1 += 1;             } else if (nums.at(pt1)+nums.at(pt2) > target ) {                 pt2 -= 1;             } else {                 break;             }         }         if (nums.at(pt1) == nums.at(pt2)) {             answer.push_back(indexHash[nums.at(pt1)].at(0));             answer.push_back(indexHash[nums.at(pt2)].at(1));         } else {             answer.push_back(indexHash[nums.at(pt1)].at(0));             answer.push_back(indexHash[nums.at(pt2)].at(0));         }         return answer;     } };