본문 바로가기

분류 전체보기361

[코딩테스트 연습] 쿠키 구입 문제: https://programmers.co.kr/learn/courses/30/lessons/49995 1. N^2 탐색을 통해 모든 구간합 DP[L][R]을 구해줍니다. 2. 그리고 난 후 DP[L][M] == DP[M+1][R]인 구간의 갯수을 찾습니다. 이 때 M의 범위는 [L,R) 입니다. 이 범위 탐색을 이분 탐색을 통해 logN에 처리하면 N^2 logN으로 통과할 수 있습니다. O(N^2)이 정해인 것 같은데, 문제를 해결한 아이디어만 얻어가시면 될 것 같습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter07.cc 2020. 5. 12.
[코딩테스트 연습] 배달 문제: https://programmers.co.kr/learn/courses/30/lessons/12978 기본적인 다익스트라 문제입니다. 1. N제한이 크지 않고 2. "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다." 위 두 가지 이유 때문에 인접리스트보다 인접행렬로 최소 비용의 간선만 저장하도록 그래프를 구현하였습니다. 1번 마을은 무조건 배달이 되므로, 2번 부터 N번 마을까지 다익스트라를 돌려서 dist[N] 2020. 5. 11.
[002]Single Number 문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3283/ 숫자 배열에서 하나의 값만 1개 들어있고, 나머지 값들은 2개씩 들어있을 때 1개만 있는 값을 찾는 문제. std::map을 생성한 뒤 배열을 순회하면서, map에 이미 있는 숫자면 pop, 없는 숫자면 insert. 그렇게 순회하고 나면 map에는 1개인 값만 남게 됩니다. class Solution { public: int singleNumber(vector& nums) { map numbers; int answer; for (int num : nums) { if (numbers.find(num) == numbers.end()) numb.. 2020. 5. 10.
[001]Subarray Sum Equals K 문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3307/ array의 부분합이 K인 구간을 O(N)만에 구하는 알고리즘. 구하고자 하는 것: array[L...R] = K인 구간의 갯수 1st. array[L...R] = K (=) prefixSum[R] - prefixSum[L-1] = K (prefixSum은 ∑ array[0...i]) 2nd. prefixSum[R] - prefixSum[L-1] = K 에서 K와 prefixSum[L-1]의 위치를 바꾸면, (=) prefixSum[R] - K = prefixSum[L-1]이 성립합니다. 3rd. prefixSum[R]은 ∑ array[0... 2020. 5. 10.

티스토리툴바