본문 바로가기

전체 글276

[Python] 프로그래머스 Lv 3 - 가장 먼 노드 개고생했던 문제 중 하나. 출처 알고리즘 그저, 1번노드부터 시작해서 최단거리를 구하면 되는 문제다. BFS로 depth를 돌려줘도 되고, 다익스트라를 쓰되, 모든 거리를 1이라고 가정해도 되는 문제다. 주의할 점은, edge의 집합이 주어져 있는데, 모든 vertex에 대해 edge의 유무를 따질 경우 시간초과가 난다. 따라서, dict를 만들어야 하는데, 각 꼭지점으로 연결된 상태 파악을 위해서는 defaultdict를 활용하여, 각 꼭지점마다 연결된 다른 점들의 list를 만들어줘야 한다. 코드(1트, 실패) 그저 bfs로 푼 코드이다. 시간 초과가 걸려 실패했으며, 빼는 방향과 넣는 방향이 반대로 해야 성공하는데, 아직까지도 정확한 이유를 판단하지 못했다. 따라서, 더 확실한 방향인 다익스트라로의.. 2021. 4. 29.
[기본이론] defaultdict()의 활용법 참고 : dongdongfather.tistory.com/69 [파이썬 기초] 유사 딕셔너리 defaultdict() 활용법 defaultdict()는 딕셔너리를 만드는 dict클래스의 서브클래스이다. 작동하는 방식은 거의 동일한데, defaultdict()는 인자로 주어진 객체(default-factory)의 기본값을 딕셔너리값의 초깃값으로 지정할 수 있 dongdongfather.tistory.com 해당 내용을 바탕으로 정리하였다. 코딩테스트 문제를 풀다가, 때로는 리스트에 담아서 key를 부여하여 dict로 묶어서 한번에 정리하는 것이 편한 경우가 있고, (특히 그래프 문제에서 이것이 기본 세팅이다) 이를 위한 방법이 defaultdict이다. defaultdict는 collections에 있는 .. 2021. 4. 29.
[DevCourse] 0429 TIL 백트래킹 vs DFS 전부 다 깊이탐색을 다 해버리면 DFS이다. 그러나 백트래킹의 경우에는 가지치기가 있어, 특정 조건을 만족하지 않으면 탐색을 중단하는 경우가 발생한다. Dict의 활용 유용성 List에 비해 Dict로 접근할 경우, 속도가 무쟈게 빨라진다. 또한 defaultdict라는 모듈을 활용해 초기 세팅을 더 편하게 할 수 있다. 이는 별도의 게시물로 defaultdict에 대해 정리한다. 2021. 4. 29.
[Python] 프로그래머스 Lv 3 - 거스름돈 프로그래머스 Lv 3 거스름돈 문제 풀이 출처 알고리즘 단순히, 큰 거부터 고르면 큰일난다. 왜냐면, 돈의 종류에 대해서 제한이 없기에, 작은 돈의 배수가 money중에 있을 수 있 으며, 이의 경우 경우의 수가 달라진다! 따라서, 그리디로 푸는 것은 불가능. 이 문제는 다른 방법으로 풀어야 할 것이다. 그 방법은 바로 DP. 동전이 1개인 경우, 2개인 경우, 3개인 경우로 늘려야 한다. 간단한 방식인데, 동전이 2개로 해결되는 경우와 그 동전이 꼭 필요한 경우를 나눠서 합치면 된다. 예시) 1,2,5원에서 13원 의 경우의 수를 구할려면 (1, 2원으로만 13원을 만드는 경우의 수) + (5원을 끼고 1,2,5원으로 13원을 만드는 수) = (1, 2원으로만 13원을 만드는 경우의 수) + (5원 1.. 2021. 4. 29.
[Python] 프로그래머스 Lv 3 - 입국심사 이진탐색을 어떻게 써먹는지 알 수 있는 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43238 알고리즘 그냥 배수를 저장한다던가, 하는 방식으로는 도저히 무리거니와, 입국심사대가 늘어날수록 2개의 쌍만 최소공배수인 경우도 발생하고... 너무 복잡하다. 되도 않는 소리다. 따라서, 방법을 바꿔야 한다. 시간을 많이 줄수록 입국심사대에서 처리할 수 있는 사람은 많을거니까, 아예 시간을 기준으로 입국심사대가 제한된 인원보다 많거나 같게 처리하면 시간을 줄이고, 덜 통과시키면 늘려버리면 된다. 최소의 지점이 바로 최소시간이 될 것이고 이는 이진탐색으로 구현 가능하다. right의 지정이 문제인데, 최소 개수의 * n만큼만 하면 충분하다. 그거보다 다른.. 2021. 4. 29.
[Python] 프로그래머스 Lv 3 - 단속카메라 프로그래머스 Lv 3 - 단속 카메라 출처 : https://programmers.co.kr/learn/courses/30/lessons/42884 알고리즘 가장 좋은 상황을 찾아야 한다. 빠져나갈 시점이 가장 빠른 순서대로 나열하자. 빨리 나갈 차는 나갈때 빨리 잡아버리고, 이미 잡아버린 차는 보내고 못 잡은 차만 나갈때 잡아버리면 최소가 될 것이다. 코드 def solution(routes): answer = 0 routes.sort(key = lambda x: x[1]) camera = -30001 for car_route in routes: if camera < car_route[0]: answer += 1 camera = car_route[1] return answer 2021. 4. 28.

티스토리툴바