반응형
반응형

문제 : https://programmers.co.kr/learn/courses/30/lessons/72412


query가 100,000 infos가 50,000.

query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다.

개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개.

3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다.

scores[개발언어][직군][경력][소울푸드] = 점수들 배열.

 

만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다.

query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다.

scores 조건에 맞는 점수들의 개수는 이분탐색으로 구할 수 있다. 이분탐색을 위해 점수들 배열은 오름차순 정렬되어 있어야 한다.

 

시간복잡도는 query가 N, infos가 M이면 O(NlogM).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EC%88%9C%EC%9C%84%20%EA%B2%80%EC%83%89.cpp

반응형
반응형

문제 : programmers.co.kr/learn/courses/30/lessons/72413


그래프이고 간선에 가중치가 있다. 최단거리알고리즘을 생각해본다.

정점 개수 n의 크기가 200으로 작은 편이므로 플로이드 워셜알고리즘으로 각 정점에서 다른 정점까지 이동할 때 최소 비용을 구해둔다.

pays[u][v] = u->v로 택시를 타고 이동할 때 드는 최소 비용 

 

합승종료지점 m 이라 하자.

이 때, 택시 비용은 출발지점에서 m 위치로 이동하는 비용 + m에서 각자의 집으로 이동하는 비용이 된다.

pays 배열로 표현하면 pays[s][m] + pays[m][a] + pays[m][b] 과 같다.

따라서 m을 0~n으로 두고 위 수식에 적용하여 구한 택시비용들 중 최소 비용이 정답이 된다.

 

시간복잡도는 플로이드 워셜을 사용하여 각 정점 사이 드는 택시 최소 비용 구하는데 가장 오랜 시간이 소요되므로 O(n^3).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%ED%95%A9%EC%8A%B9%20%ED%83%9D%EC%8B%9C%20%EC%9A%94%EA%B8%88.cpp


적으면서 알았는데 플로이드 워셜 알고리즘에 대한 포스팅을 아직 안했다..

간단히 말하면 중간 지점으로 잡는 정점을 k로 두고 u->v로 이동할때 간선의 최소값을 갱신해나가는 방법이다.

for(k = 0~n){
 for(u = 0~n){
   for(v = 0~n){
      dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
   }
 }
}

참고코드

반응형
반응형

문제 : leetcode.com/problems/intersection-of-two-linked-lists/


2개의 연결리스트가 주어질 때, 교차점이 시작되는 노드를 찾아라.

교차점이 시작되는 노드 이후의 노드들은 두 개의 연결리스트에서 모두 같다.


예시로 나온 listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]로 살펴보자.

listA-listB

listB-listA

를 순서대로 연결한뒤 앞에서부터 하나씩 비교하다보면 교차점이 시작되는 노드를 찾을 수 있다.

 

[4,1,8,4,5-5,6,1,8,4,5]

[5,6,1,8,4,5-4,1,8,4,5]

 

위와같이 연결해서 앞에서부터 하나씩 비교하면 언젠가는 교차점이 되는 8을 찾을 수 있다.

만일 탐색이 끝날때까지 같아지는 노드를 찾을 수 없다면 교차점이 없는 경우이다.

 

시간복잡도는 listA, listB 길이를 각각 N, M이라 했을 때, O(N+M)

 


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/160.%20Intersection%20of%20Two%20Linked%20Lists.cpp

반응형
dfs, DP, HARD
반응형

문제 : leetcode.com/problems/longest-increasing-path-in-a-matrix/


N*M 정수 배열이 주어질 때, 각 셸에서 상하좌우에 위치한 셸이며 현재 셸의 수보다 높은 수를 가지는 셸로 이동가능하다.

가장 긴 경로 길이를 구하라.


DFS + DP 로 풀었다.

i번째 셀에서 상하좌우로 이동가능한 곳으로 이동하면서 이동 가능한 경로의 최장 길이를 저장하는 배열(let, dp)을 만든다.

dp[i] = min(dp[상하좌우 중 이동가능한 곳])

위 점화식을 적용하며 dp배열을 dfs로 탐색하면서 세팅한다.

dp 배열이 이미 갱신된적 있다면 새로 값을 구하지 않고 해당 값을 사용하여 시간을 줄일 수 있다.

 

시간복잡도, 공간복잡도 모두 O(NM).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/329.%20Longest%20Increasing%20Path%20in%20a%20Matrix.cpp

반응형
반응형

문제 : leetcode.com/problems/missing-number/


고유한 숫자 배열 nums가 주어질 때, 0~n 까지 수 중 누락된 수를 구하라.


누락된 수는 0~n까지 수들의 합에서 nums배열의 합을 뺀 값과 같다.

0~n까지 수들의 합은 등차수열의 합 공식으로 n(n+1)/2로 구할 수 있고, nums배열의 합은 배열을 한 번 탐색하면서 구할 수 있다.

 

시간복잡도는 O(n), 공간복잡도는 O(1).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/268.%20Missing%20Number.cpp

반응형
반응형

문제 : leetcode.com/problems/set-mismatch/


1~n 까지 모든 정수를 포함하는 배열이 있다. 오류로 인해 숫자 하나가 1~n 중 다른 숫자로 변경되었다.

즉, 변경된 배열에는 누락된 숫자와 중복(2번 발생)된 숫자가 존재한다.

변경된 배열이 주어질 때 중복된 수와 누락된 수를 구하여라.


n크기의 등장횟수를 저장하는 배열을 만든다.

입력 배열을 탐색하면서 등장횟수를 갱신한다.

등장횟수가 2번인 것과 0번인 수가 정답이 된다.

시간복잡도와 공간복잡도 모두 O(N).


등장하지 않거나 두 번 등장하는 수가 한 개만 존재한다고 하였기에 비트를 쓰거나 수학적으로 접근이 가능할거 같아서 토론글을 둘러보았다. 그러다 좋은 글 있어서 해당 글  보고 정리한 방법. 따봉따봉

 

학창시절 배운 수학공식

x^2 - y^2 = (x+y)(x-y)

등차수열합(1~n) = n(n+1)/2

거듭제곱합(1^2 ~ n^2) = n(n+1)(2n+1)/6

 

let,

x = 2번 나타난 수

y = 등장하지 않은 수

 

배열의 합 = (1~n의 합) - 등장하지 않은 수 + 2번 나타난 수 
        = n(n+1)/2 - y + x
        
x - y = n(n+1)/2 - 배열의 합 = let, A
제곱 배열의 합 = (1^2 ~ n^2의 합) - 등장하지 않은 수의 제곱 + 2번 나타난 수의 제곱
        = n(n+1)(2n+1)/6 - y^2 + x^2

x^2 - y^2 = n(n+1)(2n+1)/6 - 제곱 배열의 합 = let, B

A 식의 양변에 (x+y)를 곱해준다.

(x - y)(x + y) = A(x+y)

이는 x^2 - y^2 와 같기 때문에 B와 같아진다.

 

즉,

A(x+y) = B
x + y = B/A

 

x+y = B/A

x-y = A

 

// 두 식을 더한다.
2x = A + B/A
x = (A + B/A)/2

// 두 식을 뺀다.
2y = B/A - A
y = (B/A - A)/2

 

x, y를 제외한 모든 수들은 입력값에서 구할 수 있으므로 A, B를 구한 뒤 위 수식에 대입하면 x, y를 구할 수 있다.

 

시간복잡도는 동일하게 배열을 한 번 탐색해야 하므로 O(N)이지만 공간복잡도는 O(1)로 줄어든다.


소스코드 

space O(N) : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/645.%20Set%20Mismatch.cpp

space O(1) : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/645.%20Set%20Mismatch(math).cpp

 

참고

leetcode.com/problems/set-mismatch/discuss/1089475/Python-O(n)-timeO(1)-space-math-solution-explained

반응형
반응형

문제 : leetcode.com/problems/distribute-candies/


n개의 사탕타입 배열이 주어진다. n/2개의 사탕만 먹을 때, 가장 다양하게 먹을 수 있는 사탕 타입의 수를 구하라.


n/2와 사탕타입의 개수 중 최소값이 정답이 된다.

배열을 탐색하면서 set에 타입을 저장한다. set의 크기가 사탕 타입의 개수가 된다.

 

시간복잡도는 O(N).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/575.%20Distribute%20Candies.cpp

반응형
반응형

문제 : leetcode.com/problems/shortest-unsorted-continuous-subarray/


정수형 배열이 주어질 때, 연속적인 서브배열을 오름차순 정렬하면 전체 배열이 오름차순 정렬이 되게 하는 서브배열의 최소 길이를 구하라.


가장 간단한 방법은 주어진 배열을 오름차순 정렬한뒤 정렬한 배열과 기존 배열을 비교하면서 다른 요소값을 가지는 인덱스의 최소 값과 최대 값을 구한다. 최대값 - 최소값 + 1이 정답이된다.

이 방법으로 한 경우 정렬이 필요하므로 O(NlogN)의 시간이 소요된다.

 

문제에서는 선형복잡도로 풀 수 있는지 물었으므로 좀 더 효율적인 방법을 살펴보자.

[2,6,4,8,10,9,15] 를 예로 들어보자.

배열이 오름차순 정렬이라고 가정한다면,

왼쪽에서 오른쪽으로 탐색 시 탐색 중인 요소값은 이때까지 탐색한 값보다 같거나 커야한다.

오른쪽에서 왼쪽으로 탐색 시 탐색 중인 요소값은 이때까지 탐색한 값보다 작거나 같아야한다.

 

따라서 왼쪽에서 오른쪽으로 탐색하면서 요소의 최대값을 갱신시키면서 현재 탐색중인 값이 탐색한 값들중 최대값인지 판단한다. 만일 최대값이 아니라면 위 가정이 성립되지 못하므로 재정렬되어야한다. 따라서 현재 인덱스 값을 rightInd로 갱신한다.

이와 동일하게 이번에는 오른쪽에서 왼쪽으로 탐색한다. 최소값을 갱신시키면서 만일 탐색 중인 요소가 최소값이 아니라면 현재 인덱스 값을 leftInd로 갱신한다.

입력배열[leftInd, rightInd]가 재정렬 필요한 하위배열이 되므로 rightInd-leftInd+1이 정답이 된다.

예외적으로 만일 전체 배열이 정렬되어 있다면 0이 정답이 된다.

시간복잡도는 O(2N). 배열을 한 번 탐색하면서 배열[i], 배열[N-1-i]로 동시에 판단가능하므로 O(N)으로도 가능하다.


소스코드 

O(NlogN) : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/581.%20Shortest%20Unsorted%20Continuous%20Subarray(NlogN).cpp

O(N) : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/581.%20Shortest%20Unsorted%20Continuous%20Subarray(N).cpp

반응형

+ Recent posts

반응형