스티커 모으기(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개의 댓글

하노이의 탑

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

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

최고의 집합

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

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

줄 서는 방법

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

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

야근 지수

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