전체태그 보기

#alg (35개의 포스트)

songjy6565

징검다리

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

3 x n 타일링

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

숫자 게임

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는 수가 남든 안남든 버려지는 방식.. 근데 막상 짜...
songjy6565

기지국 설치

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

배달

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

하노이의 탑

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

최고의 집합

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

줄 서는 방법

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

야근 지수

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

방문 길이

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

멀리 뛰기

2019년 5월 14일0개의 댓글
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) 모든 경우의 수에서 ...
songjy6565

가장 긴 팰린드롬

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

순위

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

등굣길

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

저울

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

예산

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

입국 심사

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

이중 우선순위 큐

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

정수 삼각형

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

가장 먼 노드

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