본문 바로가기

CS/알고리즘

PS를 하며 느끼는 DFS와 BFS 선택의 기준 2021. 12. 12. 알고리즘 문제 풀이를 하며 여러 사람들과 이야기를 나눈적이 있다. 그 중 알고리즘 문제 풀이를 막 시작한 초급자분들이 가장 헷갈려하는 부분이 그래프탐색 문제를 만났을때, 언제 DFS를 선택해야되고 언제 BFS를 선택해야 되나요? 에 대한 부분이였던것 같다. 보통 코딩테스트 문제를 풀며 느끼는 이런 그래프 탐색 문제의 경우 1) DFS or BFS 어떤것이든 사용해도 무관한 경우 2) DFS를 사용하는것이 압도적으로 편한경우 3) BFS를 사용하는것이 압도적으로 편한경우 이렇게 3가지 경우의 수로 나뉘는것 같다. 나는 1) 의 경우 DFS를 선호하는경향이 있다. 이건 본인이 어떤 알고리즘을 더 편하게 느끼고 많은 경험이 있는지 판단해 적당히 정하면 될 문제라고 생각한다. 그렇다면 남은 문제는 2)번과 3)..
알고리즘용 파이썬 sorted 함수로 정렬하는 여러 방법들 2021. 6. 11. 파이썬으로 알고리즘을 풀다보면 정렬을 사용해야 되는 경우를 자주 본다. 알고리즘에서 많이 쓰이는 파이썬 자료형은 리스트, 이차원리스트, 딕셔너리 여러 경우의 수에 어떻게 정렬을 하면 좋은지 정리해보았다. 앞으로 문제 풀며 다른 상황을 마주하게 된다면 추가하겠음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #################################################################### #리스트 str_li = ['AB', 'AA..
[다익스트라 알고리즘/ 플로이드 워셜 알고리즘] 구현코드 2021. 6. 4. 다익스트라 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로 우선순위 큐를 이용한 구현법이 더 쉽고 시간복잡도도 낮음 O(E logV) 그리디 스러움 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import heapq import sys input = sys.stdin.readline INF = 1000000000 # 무한을 의미하는 10억 설정 # 노드의 개수, 간선의 개수 n, m = map(int, input().split()) # 시작노드 번호를 입력받음 start = int(input()) # 각 노드에 연..
조합과 순열 c++ 로 구현 2021. 5. 15. https://yabmoons.tistory.com/99 https://yabmoons.tistory.com/100 저 위 블로그 주소에서 보고 알고리즘 공부중 써먹을곳이 많겠다 싶어서 작성합니다 백준 17281번 문제 푸는데 푸는법은 알겠어.. 근데 순열을 구현할 능력이 없었음 permutation 이라는 내장 기능이 있는데 이걸 자주 쓰는것도아니고 조합, 순열 한번쯤은 구현해봐야겠다 싶어서 시작 조합코드 백트래킹을 통해 선택 했을때 경우와 안 했을떄 경우를 재귀적으로 진입하는 방법인것 같음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43..

티스토리툴바