SERIES

algorithm

알고리즘 공부 시작

2019년 3월 14일

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

완주하지 못한 선수

2019년 3월 15일

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

모의고사

2019년 3월 18일

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

k번째수

2019년 3월 21일

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

체육복

2019년 3월 22일

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

2016년

2019년 3월 23일

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

level1 연습문제들

2019년 3월 31일

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

N으로 표현

2019년 4월 2일

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

2 x N 타일링

2019년 4월 3일

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

네트워크

2019년 4월 4일

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

타일 장식물

2019년 4월 4일

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

디스크 컨트롤러

2019년 4월 9일

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

단어 변환

2019년 4월 11일

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

단속 카메라

2019년 4월 11일

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

섬 연결하기 (최소 신장 트리(mst), kruskal alg)

2019년 4월 15일

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

가장 먼 노드

2019년 4월 17일

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

정수 삼각형

2019년 4월 17일

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

이중 우선순위 큐

2019년 4월 17일

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

입국 심사

2019년 4월 17일

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

예산

2019년 5월 3일

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

저울

2019년 5월 3일

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

등굣길

2019년 5월 3일

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

순위

2019년 5월 3일

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

가장 긴 팰린드롬

2019년 5월 3일

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

멀리 뛰기

2019년 5월 14일

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) 모든 경우의 수에서 ...

방문 길이

2019년 5월 14일

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

야근 지수

2019년 5월 14일

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)) 이 ...

줄 서는 방법

2019년 5월 14일

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

최고의 집합

2019년 5월 14일

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

하노이의 탑

2019년 5월 14일

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

배달

2019년 5월 14일

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

기지국 설치

2019년 5월 14일

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 구해주면 됨.....

숫자 게임

2019년 5월 14일

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

3 x n 타일링

2019년 5월 14일

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

징검다리

2019년 5월 14일

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