# alg

50개의 포스트

최적의 행렬 곱셈

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

2020년 5월 21일
·
0개의 댓글

단어 퍼즐

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

2020년 4월 15일
·
0개의 댓글

호텔 방 배정

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

2020년 4월 13일
·
0개의 댓글

자동완성

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

2020년 4월 11일
·
0개의 댓글

스티커 모으기(2)

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

2020년 2월 10일
·
0개의 댓글

무지의 먹방 라이브

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

2020년 2월 10일
·
0개의 댓글

블록 게임

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

2020년 2월 6일
·
0개의 댓글

쿠키 구입

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

2020년 1월 31일
·
0개의 댓글

올바른 괄호의 갯수

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

2020년 1월 19일
·
0개의 댓글

숫자 블록

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

2020년 1월 18일
·
0개의 댓글

선입 선출 스케줄링

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

2020년 1월 18일
·
0개의 댓글

게임 맵 최단 거리

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

2020년 1월 17일
·
0개의 댓글

지형 이동

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

2020년 1월 16일
·
0개의 댓글

서울에서 경산까지

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

2020년 1월 15일
·
0개의 댓글

도둑질

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

2020년 1월 15일
·
0개의 댓글

징검다리

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

2019년 5월 14일
·
0개의 댓글

3 x n 타일링

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

2019년 5월 14일
·
0개의 댓글

숫자 게임

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

2019년 5월 14일
·
0개의 댓글

기지국 설치

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일
·
0개의 댓글

배달

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

2019년 5월 14일
·
0개의 댓글