algorithm

초심으로 돌아가서 꾸준히 나아가 보려고 한다. 같은 문제에 대해 c++, javascript, python3 으로 각각 작성하기로 계획중이다. (너무 근본없이 이거 쓰다 저거 쓰다 하다보니 익숙해지질 않아서 몇 개를 꾸준히 써보자는 느낌?) 언어는 솔직히 중요하지 않은 것 같아 언제든 변경될 수 있다. 기존에는 빠르다고 알고 있는(착각인가?) c를 많이 ...

프로그래머스 js, cpp, python3 - level1 체크했을 때, 가장 먼저 뜬 문제다. https://programmers.co.kr/learn/courses/30/lessons/42576 thinking flow N, N-1 input array 가 존재한다. 일단 무조건 한번씩은 참조를 해야 한다고 생각 -> 최소 O(2N) 비교를 해야 되는...

https://programmers.co.kr/learn/courses/30/lessons/42840 flow 이미 비교해야 될 대상의 규칙,패턴이 주어짐. 정답 배열만 참조하면 해결 가능한 문제, 즉 O(N) brute force 하게 풀어도 O(N) 으로 큰 차이 없음. modular 관련해서 규칙 깔끔하게 정리 되는 것 같지도 않아 단순 비교 re...

https://programmers.co.kr/learn/courses/30/lessons/42748 solution 단순 정렬 문제? 정렬에서 O(NlogN) 이 걸리기 때문에 이 부분을 줄이지 않는 이상 전체 시간복잡도는 줄지 않는다. 정렬값을 반환하는 것이 아닌 k번째 수를 반환하는 문제이기 때문에 이것저것 해보고 싶긴 하다. min(k,n) (n=...

https://programmers.co.kr/learn/courses/30/lessons/42862 solution 단순히 lost 와 reserve 간 element 들을 최대한 많이 매칭해주는 문제이다. 인풋 수가 거대하지도 않고, 시간복잡도 또한 신경쓰일 만큼 복잡해지지가 않아서 단순하게 생각 lost 가 정렬이 되어 있다고 생각해서(아닌가?) l...

https://programmers.co.kr/learn/courses/30/lessons/12901 solution 요일 문제... 1월 1일 금요일이 주어졌으므로 input의 날짜와 1월 1일의 차이를 7로 나눈 나머지를 이용해 요일을 구할 수 있다. result https://github.com/songjy6565/alg-js/blob/master/...

생각보다 단순한 문제들이 많아서 일일이 풀어 쓰기가 비효율적일 것 같아 넘어가기로 결정.. 가운데 글자 가져오기 (https://programmers.co.kr/learn/courses/30/lessons/12903) https://github.com/songjy6565/alg-py/blob/master/programmers/level1/A6.py htt...

https://programmers.co.kr/learn/courses/30/lessons/42895 flow 카테고리가 dp 인 문제이다.. solution[n] 을 N을 n번 사용했을 때, 만들어질 수 있는 모든 수라고 정의하면 solution[n+1] 은 solution[n] 집합 내 모든 수에서 N 을 사칙연산 해준 값이 되지 않을 까 생각했다. ...

https://programmers.co.kr/learn/courses/30/lessons/12900 flow n 의 총 길이를 채우는데 가로 2, 세로 1.. 가로로 배치한 수를 고정했을 때, 경우의 수를 합하면 될 것이라 생각.. 예를 들어 n = 5 이면, 가로 배치 0일때 경우의 수 1 가로 배치 1개일 때 경우의수는 n-2 개의 세로 타일들을 1...

https://programmers.co.kr/learn/courses/30/lessons/43162 flow 간단히 보면 n x n 배열의 원소들을 모두 탐색하는 문제이다. 최적화 해서 몇가지 원소들을 탐색하지 않아도 되게끔 만드려고 해도 결국 O(n^2) 이기 때문에 쉽게 가도록 하겠다. 키워드가 dfs 와 bfs 인데 둘중 어느 것을 써도 상관 없는...

https://programmers.co.kr/learn/courses/30/lessons/43104 flow 얼마 전에 봤던 타일링과 비슷하게 피보나치 수열이 이용이 된다. 규칙을 조금 생각해보면 쉽게 solution(n) = solution(n-1) + 2*f(n) 위와 같은 공식을 만들 수 있다. ( f 는 피보나치 수열 ) 키워드로 나온 dp 에 ...

https://programmers.co.kr/learn/courses/30/lessons/42627 flow 특정 시점일때, 요청이 들어와서 처리가 가능한 작업중 가장 짧은 작업을 선택해 나아가면 된다. 예시같은경우 처음 시점 0ms 일때, A만 가능하므로 A선택, A는 3ms 걸리므로 다음 시점은 3ms, 이 때 가능한 작업들은 요청 들어온 시간이 1...

https://programmers.co.kr/learn/courses/30/lessons/43163 flow 가장 짧은 변환 과정을 찾는 문제.. 루트가 begin인 트리에서 자식 node들이 words에 포함되어 있고 부모로부터 변환이 가능한(철자 하나 차이) 집합을 규칙으로 하는 트리가 만들어질 때, 너비 우선 탐색을 통해서 target과 일치하는 ...

https://programmers.co.kr/learn/courses/30/lessons/42884 flow 그리디 알고리즘? routes 리스트를 정렬한 후, 순서대로 겹치는 부분을 확인해 나아가면 될 듯함 정렬 했을 때, 순서대로 A와 B가 겹치는 부분 존재하고, B와 C가 겹치는 부분 존재하면서 A와 C가 겹치지 않을 때, 그냥 A와 B가 겹치는 ...

https://programmers.co.kr/learn/courses/30/lessons/42861 flow 문제를 보면서 계속 생각해봤는데 왠지 예전에 알고리즘 수업에서 봤던 되게 흔한 느낌이 났다.. 정확히는 기억 안나서 찾아보았더니 최소 신장 트리를 만드는 문제와 동치이다. 예전에 공부했던 자료도 다시 보고 정리해서 써볼까 했는데 코드를 작성하는 ...

https://programmers.co.kr/learn/courses/30/lessons/49189 flow 간선 가중치를 모두 1이라 생각하면 양수 가중치 쌍방향 그래프가 되서 다익스트라로 1번 노드와 다른 모든 노드간의 최단 거리 값을 구할 수 있다.. 그 중 거리가 가장 큰 노드들의 개수가 답이 되겠지만 약간 비효율적인 것 같아 다른 방법을 생각해...

https://programmers.co.kr/learn/courses/30/lessons/43105 flow 너무 뻔한 dp 문제이다.. f(n) : 높이 n일 때, 바닥까지의 최댓값 리스트 로 이전 값을 계속 볼 필요 없이 한 층씩 쌓아 나갈 수 있다. 시간 복잡도는 근데 O(N^2) 이 나온다.. N은 높이 1+2+3+4... + N 의 연산이 필요...

https://programmers.co.kr/learn/courses/30/lessons/42628 flow 동시에 최소힙과 최대힙을 운용하면 된다. 예전 글에 python heapq를 이용했던 적이 있다. 이번에도 이용해서 풀면 금방 풀 수 있다.. 시간 복잡도는 힙 두개를 만드는 것이므로 O(NlogN) 이다. Operations 길이가 N이고 모두...

https://programmers.co.kr/learn/courses/30/lessons/43238 flow 처음에 카테고리가 이분탐색인 것을 보고 약간 멘붕이 왔다. binary search 를 오랜만에 보다 보니 이게 이분 탐색으로 푸는 게 적합한 문제인가 감이 안 왔다. 계속 생각해보다가 적합한 time을 이분탐색으로 찾는 거구나 해서 바로 풀었지...

https://programmers.co.kr/learn/courses/30/lessons/43237 flow 한동안 다른 일로 바빠서 예전에 풀어놨던 문제인데 정리를 못했었다. 기억이 완전하진 않지만 이것도 이분탐색 알고리즘을 이용하면 되는 문제이다. 예산 배정 상한액을 구하는데 min=0, max=max(budgets) 부터 스타트하면 깔끔한 것 같다...

https://programmers.co.kr/learn/courses/30/lessons/42886 flow 일단 추를 무게순으로 정렬하고, 특정 추의 무게가 n일 때, 그 추보다 작은 무게를 가진 추들 모두의 합이 n-1 보다 작으면 sum+1 ~ n-1 의 무게는 절대 잴 수 없다. 이 점을 이용하면 무게가 작은 추부터 차례대로 확인해 나아가면서 정...

https://programmers.co.kr/learn/courses/30/lessons/42898 flow 처음에 이 문제를 보고 카테고리가 dp라서 바로 생각의 풀이 제한되어 버렸다.. 특정 칸의 최단 경로 갯수는 인접한 전칸들의 최단 경로 갯수 합이 될 것이고, 웅덩이들만 적절히 반영해주면 풀릴 문제라고 생각을 했다. 근데 막상 알고리즘을 짜려고 ...

https://programmers.co.kr/learn/courses/30/lessons/49191 flow 각 선수가 node 일 때, 방향성이 있는 edge들로 구성되는 그래프를 만들 수 있다. ((4,3) 이 4->3 edge) 이 그래프에서 특정 노드와 바로 연결되어 있거나 단방향으로 연결이 되는 집합(한붓그리기, ex)특정노드 2일때, 2->3...

https://programmers.co.kr/learn/courses/30/lessons/12904 flow 팰린드롬을 확인하는 알고리즘.. 특정 센터를 기준으로 양옆으로 나아가면서 같은 지 확인 센터는 문자 하나가 될 수 있고, 같은 문자 두개가 될 수 있음. 이를 토대로 문자열 s 모든 인덱스에 대해 센터를 잡고 팰린드롬 길이를 확인해서 max 값을...

https://programmers.co.kr/learn/courses/30/lessons/12914 flow 이거 옛날에 풀었던 2xN 타일링 문제와 같은 방식으로 풀 수 있다. 보면 f(n) = f(n-1)+f(n-2) 의 점화식이 정답이 됨을 쉽게 파악할 수 있다. f(n-2) 모든 경우의 수에서 2칸 뛰는 것과 f(n-1) 모든 경우의 수에서 1칸...

https://programmers.co.kr/learn/courses/30/lessons/49994 flow 되게 단순히 생각해보자. 뭐가 어떻게 되든 지나간 길을 기억해야 한다는 것이 주요 포인트다. 이러한 점은 양보 못하고 알고리즘에 따라 시간복잡도와 공간복잡도가 달라질 것이다. 일단 지나가는 길을 모두 배열안의 element 들로 표현하게 만들어서...

https://programmers.co.kr/learn/courses/30/lessons/12927 flow 처음에 생각을 짧게 해서 (Sum % leng) * (Sum//leng + 1)^2 + (leng - Sum % leng) * (Sum//leng)^2 이런 공식 (sum == sum(works)-n, leng == len(works)) 이 적용...

https://programmers.co.kr/learn/courses/30/lessons/12936 flow 이거는 문제에 힌트가 있는게 ㅋㅋ.. 제한사항에서 k가 n! 이하의 자연수 조건이 있다. 고등 수학 많이 까먹었지만 n 개 집합에서 순서 세우는 것의 가짓수가 n! 라는 것을 기억해낼 수 있다. 이게 생각나자마자 바로 문제를 풀 방법이 떠올랐는데...

https://programmers.co.kr/learn/courses/30/lessons/12938 flow 이거는 좀 생각해보다가 문제를 의심했음.. 그냥 당연히 max(집합) 과 min(집합) 값의 차이가 가장 작은 방향으로 골고루 원소를 분포하게 만들면 최고의 집합이 됨.. 고등수학 때 배웠던 정리중에 연관된게 있었던 것 같은데 잘 기억이 안남.....

https://programmers.co.kr/learn/courses/30/lessons/12946 flow 처음에 당연히 횟수 구하는 줄 알고 ㅋㅋ 점화식이 뭐였더라 회상함.. f(n) = 2f(n-1) + 1 임을 인지했지만 그게 아니라 방법을 return 하는 문제였음.. 이런 문제는 처음 봤는데 의도를 생각해봤을 때, 당연히 규칙이 있겠지 생각을...

https://programmers.co.kr/learn/courses/30/lessons/12978 flow 이런 그래프 문제 읽자마자 또야 라는 생각이 들었음.. 그냥 다익스트라 알고리즘과 거의 유사하다 보면 정답이 보임. 시간복잡도를 더 줄일 수 있는 방법이 있기야 하겠지만 그렇게 깔쌈한 솔루션이 나올 것 같진 않아서 단순하게 구현 (양방향 그래프라...

https://programmers.co.kr/learn/courses/30/lessons/12979 flow 딱 보자마자 greedy 한 방법이 생각남.. station을 기점으로 split되는 구간들이 발생할 것이고 이 구간들의 거리값 각각 Di 면 Sum((Di//2w+1) + (Di%2w+1)) i=1~len(station)+1 구해주면 됨.. 코...

https://programmers.co.kr/learn/courses/30/lessons/12987 flow 처음에 생각났던 것은 B.count(2)와 A.count(1) 로 시작해서 1과 2를 매칭시키고 계속 나아가는 방식이였음.. A의 수가 남으면 다음 index count 수에 덧셈이 되고 B는 수가 남든 안남든 버려지는 방식.. 근데 막상 짜려고...

https://programmers.co.kr/learn/courses/30/lessons/12902 intro 이제부터 level 4로 진입하게 되었다.. flow 이제 슬슬 이런 문제가 보이면 또 점화식이 있겠구나라는 생각이 먼저 든다. 제한 조건이 정확하지 않은데 일단 n은 짝수만 허용하는 것이라 단정 지었다. 홀수는 타일로 구성하기 불가능하기 때문...

https://programmers.co.kr/learn/courses/30/lessons/43236 flow 일단 카테고리도 그렇고 바로 이분탐색 솔루션이 떠올랐다. 거리의 최솟값을 타겟으로 이분탐색을 진행하는데 검증하는 방법에는 greedy 한 방법을 쓰면 된다. 정렬된 rocks 를 순서대로 보면서 이전 바위와의 거리가 설정된 거리값인 mid 보다 ...

https://programmers.co.kr/learn/courses/30/lessons/42897 flow 동적 계획법을 이용하면 쉽게 풀 수 있는 문제이다. n번째 집까지만 생각했을 때, (n-2 까지의 최댓값 + n번째 집 money) 와 n-1까지의 최댓값 둘을 비교하여 더 큰 값이 n번째의 최댓값이 되고 이를 반복해 나아가면 정답이 나온다. 주의...

https://programmers.co.kr/learn/courses/30/lessons/42899 flow 제한시간 K에 대해 동적 프로그래밍을 진행하면 된다. 구간 1부터 도보와 자전거 시간 정보를 받은 뒤, 가능한 시간에 대해 모금액 최댓값을 업데이트해 나아가면 된다. 코드를 간결하게 짜는 경우 O(K) 에 가능한 문제이지만 필자는 travel 배열...

https://programmers.co.kr/learn/courses/30/lessons/62050 flow 가장 먼저 너비 우선 탐색(bfs)를 이용해 region growing 하듯이 사다리가 필요없는 그룹끼리 같은 노드로 묶는 작업이 필요하다. (dfs도 상관 없음) 이후 그룹을 노드라고 생각하고 그래프를 만든다 생각해보면, 높이차가 간선(edge...

https://programmers.co.kr/learn/courses/30/lessons/1844 flow 어제 풀었던 문제와 비슷하게 1인 칸을 노드라고 생각하고 인접한 노드끼리간 가중치가 1인 간선이 존재한다고 생각했을 때 나온 그래프에서 시작 노드와 끝 노드 간의 최단 거리를 구하면 된다. dfs bfs 모두 가능하지만 필자는 너비 우선 탐색(bf...

https://programmers.co.kr/learn/courses/30/lessons/12920 flow 이 문제는 처음 봤을 때, 이분 탐색이 생각 났는데 바로 정답을 찾기에는 좋은 방법이 떠올리지 않았다. 그래서 이분 탐색으로 정답을 직접적으로 찾는 것이 아니라 모든 작업이 코어에 진입하는(주의. 작업이 완료되는 것이 아니라) 최소 시간을 찾는다...

https://programmers.co.kr/learn/courses/30/lessons/12923 flow 처음에 문제를 봤을 때 소수와 관련이 크다고 생각을 했다. 자세히 보다보면 규칙을 찾을 수 있는데 소수인 index는 값이 1이 되고, 합성수들은 약수 중 가장 작은 소수로 나눠진 값을 가진다. 길이와 블록 수가 달라서 이를 유의하면서 조건을 추...

https://programmers.co.kr/learn/courses/30/lessons/12929 flow 처음에 규칙을 찾아보려고 생각하다보니 일단 부분적으로 잘라보았을 때, 항상 여는(왼쪽)괄호 갯수가 닫는(오른쪽)괄호 보다 같거나 많아야 한다는 것을 주의깊게 보았었다. 그리고 이전항과의 점화식을 찾아보려고 노력했는데 다음과 같이 정답이 아닌 결론을...

https://programmers.co.kr/learn/courses/30/lessons/49995 flow 이 문제는 greedy 하거나 linear하게 풀 수 없을 것 같다고 느꼈다. 결국 A[l] 부터 A[m] 까지의 sum과 A[m+1] 부터 A[r] 까지의 sum 을 모두 비교해주는 작업이 최소 한번 씩은 들어가야 한다고 생각이 들었다. 이는 ...

https://programmers.co.kr/learn/courses/30/lessons/42894 flow 문제를 읽고 처음 떠오른 아이디어는 12가지 블록중에 5가지 경우를 제외한 나머지는 어떠한 경우에도 속이 꽉 채워진 직사각형을 만들 수 없다는 것을 깨달았다. 이 때 5가지의 공통점은 (ㅏ) 모양과 (ㅓ) 모양을 제외하고 위에서 부터 볼 때, 가장...

https://programmers.co.kr/learn/courses/30/lessons/42891flow단순히 생각해봤을 때, 음식 번호 순서대로 하나씩 세면서 진행했을 때, k번째 음식을 찾으면 된다. 이를 어떻게 효율적으로 풀어볼까 고민했는데 다른 특별

https://programmers.co.kr/learn/courses/30/lessons/12971flow이 문제는 단순하게 동적 프로그래밍(dp) 로 풀 수 있는 문제이다. 초기 위치부터 나아갈 때 f(n) = max(f(n-1),f(n-2)+sticker

https://programmers.co.kr/learn/courses/30/lessons/17685flow일단 검색 단어 수 N 이고, 단어들 평균 길이가 M이라고 했을 때, 어떤 알고리즘을 쓰던간에 한번씩 탐색이 필요하니 O(MN) 이 최소일 것이다. 처음

https://programmers.co.kr/learn/courses/30/lessons/64063flow1.) 효율성 테스트가 있고 간단한 태스크 처럼 보여 최적화가 상당히 어려울 것이라 예상하긴 했지만 일단 가장 간단하게 먼저 풀어보았다.단순히 index

https://programmers.co.kr/learn/courses/30/lessons/12983flow예전에 솔루션이 한번에 생각이 안 나서 넘어갔었는데 이번에 다시 보니 금방 dp 쪽으로 idea가 생각이 났다. dpi 의 값을 t 를 앞에서부터 i+1

https://programmers.co.kr/learn/courses/30/lessons/12942flow of the solution기본적으로 greedy 한 solution 없이 모든 matrix multiplication 경우를 확인해야 한다. 이는 a