본문 바로가기

코딩코딩/알고리즘5

[프로그래머스] 여행경로 - 파이썬 BFS 꼭 BFS로 풀어야 하는 문제는 아닙니다. 그냥 간만에 BFS 연습할 겸 BFS로 풀어보았습니다. 중복티켓을 위한 테스트 케이스 tickets: [["ICN", "A"], ["ICN", "A"], ["ICN", "A"], ["A", "ICN"], ["A", "ICN"]] Return: ["ICN", "A", "ICN", "A", "ICN", "A"] 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SF.. 2022. 6. 22.
[알고리즘] 이진탐색에서 한 나의 실수 1. left와 right 초기화 단순히 리스트의 길이를 right로 초기화 하면 인덱스의 길이와 맞지 않아 런타임 에러(IndexError)가 발생한다. lst = [1,2,3,4] # 인덱스의 최대값은 3, 길이는 4 left, right = 0, len(lst) -1 # 여기서 1을 빼주지 않으면 lst[4]를 할 수 있어 인덱스 에러 발생 2. while left target: right = mid - 1 elif ns[mid] < target: left = mid + 1 2022. 2. 19.
A* 알고리즘 Heuristics 휴리스틱 함수 h(n)은 A알고리즘에게 현재 위치n에서 *목표까지의 최소비용**을 산정해 알려준다. 따라서 휴리스틱 함수를 어떻게 지정할지가 중요하다. A* Use of the Heuristic 휴리스틱은 A*알고리즘의 행동(이동)을 제어한다. 하나의 극점에서, 만약 h(n)이 0이면, g(n)만 역할을 수행하고 A*는 다익스트라 알고리즘이 된다. (다익스트라는 가장 짧은 경로를 찾는데 보증된 알고리즘) 만약 h(n) 값이 항상 n에서 goal까지 이동하는 비용보다 늘 작거나 같다면, A도 최단 경로를 찾는다고 보장할 수 있다. h(n)값이 작을수록, A가 더 많은 노드를 탐색할 것이고, 더 느리게 만들 것임. h(n)이 n에서 목표까지의 cost와 정확히 일치하는 경우, A는 최선의.. 2020. 12. 12.
[유전 알고리즘, GA] #1 초기 population 생성하기 (generate initial population) 코드: github.com/gon2gon2/lecture/blob/master/GA/initial_population.ipynb gon2gon2/lecture Contribute to gon2gon2/lecture development by creating an account on GitHub. github.com 영상 해설: www.youtube.com/redirect?q=https%3A%2F%2Fg0n1.tistory.com%2F108&event=video_description&v=-BVaM3no590&redir_token=QUFFLUhqbVU4SFVxY1didzhPQUVLSjZLY1JObVhkcVVLUXxBQ3Jtc0tsbkRsNHZJU0ozcDcwclJtWDgwbTN4Y3dLMGJEaXNTM2pM.. 2020. 11. 23.

티스토리툴바