Algorithm5 [Leetcode / Javascript] 15. 3Sum 문제는 다음과 같습니다. 숫자의 배열이 주어지고 배열의 원소 중 3개를 더해서 0이 만들어지는 조합을 찾는 문제입니다. 문제 해결방법은 다음과 같습니다. nums 배열을 정렬한 후 제일 앞 원소를 조합의 첫 번째 숫자로 지정합니다. 그리고 그 뒤에 있는 숫자들 중 조건을 만족하는 나머지 2개의 숫자를 찾습니다. nums 배열을 순회하면서 이 과정을 반복합니다. 즉, 3개의 숫자 중 가장 작은 수를 하나 뽑고 나머지 숫자의 조합을 찾는 방법입니다. nums 배열이 정렬되어 있기 때문에 첫 번째 숫자가 0보다 크다면 합이 0이 될 수 없기 때문에 순회를 종료합니다. 나머지 숫자에서 2개를 찾는 방법은 다음과 같습니다. 첫 번째 숫자 바로 다음 숫자의 index를 lo로 지정하고 가장 마지막 index를 hi.. 2021. 6. 23. [Leetcode / Javascript] 14. Longest Common Prefix 문제는 다음과 같습니다. 문자열의 배열이 주어지고 그 원소들의 가장 긴 공통 prefix(Longest Common Prefix, LCP)를 찾는 문제입니다. 여러 문자열의 LCP를 찾으려면 두 문자열 씩 비교하며 LCP를 찾아나가면 됩니다. Example 1을 예로 들면 "flower"와 "flow"의 LCP인 "flo"를 찾고 다시 "flo"와 "flight"의 LCP인 "fl"을 찾는 방식입니다. 이렇게 찾아진 "fl"인 ["flower", "flow", "flight"]의 LCP가 됩니다. 위 예시를 식으로 나타내면 LCP(S1, S2, ... , Sn) = LCP(LCP(S1, S2),... Sn) 이렇게 됩니다. 이 식을 코드로 나타내보겠습니다. function LCP(left, right) .. 2021. 6. 2. [백준] 1002번: 터렛 문제는 다음과 같습니다. www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 간단히 정리하면 두 원의 중심 (x1, y1), (x2, y2) 와 두 원의 반지름 r1, r2가 주어졌을 때 원의 접점의 개수를 출력하는 문제입니다. 접점의 개수가 무한대일 경우 -1을 출력합니다. 접점의 개수를 구하기 위해서는 세 가지 변수가 필요합니다. distance : 두 원의 중심 사이의 거리 rsum : 두 원의 반지름의 합 rsub : 두 원의 반지름의 차의 절대값 이제 경우의 수를 살펴보겠습니다. 우선 두 원의 중심과 반지.. 2021. 2. 11. [백준] 9251번 : LCS 문제는 다음과 같습니다. https://www.acmicpc.net/problem/9251 두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 수열 중 가장 긴 수열인 최장 공통 부분 수열(LCS)을 찾는 문제입니다. 아무리 생각해도 모르겠어서 결국 답을 봤습니다. 풀이의 컨셉은 이렇습니다. for(int i=1;i 현재 문자가 LCS에 포함되지 않으므로 현재 문자가 등장하기 전 LCS 중 큰 값을 대입 이 규칙으로 표를 채우면 다음과 같습니다. dp[][] A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 표를 채운 후 답은 .. 2019. 8. 22. 이전 1 2 다음
