알고리즘 23

코딩 테스트 요약본

코딩 테스트 준비하면서 핵심 요약 파이썬으로 준비합니다. 많은 부분을 나동빈님 저자, 이것이 취업을 위한 코딩 테스트다 with Python 를 참고하였습니다. 외워야할 것 들 import sys input = lambda: sys.stdin.readline().rstrip() sys.setrecursionlimit( LIMIT ) from collections import deque from itertools import combinations, permutations import math math.ceil() math.floor( NUMBER + 0.5 ) # 반올림 import heapq q = [] heapq.heappush(q, NUMBER) n = heapq.heappop(q) arr = AR..

알고리즘 2023.10.13

다익스트라 알고리즘

다익스트라 알고리즘 Dijkstra Algorithm 짧은 요약 다익스트라, 그게 뭔데? 음의 간선이 없을 때, 특정 노드로부터 다른 노드까지의 최소 경로를 구하는 알고리즘. 만약 간선의 비용이 일정하다면 BFS로도 충분. 매 순간 가장 비용이 적은 노드를 선택하여 누적 비용을 갱신하므로 그리디 알고리즘으로 분류된다. 시간 복잡도, 얼마나 빠른데? 구현 방법에 따라서 시간 복잡도가 다르다. 우선순위 큐를 사용하지 않았을 때, $$O(V^2)$$ 우선순위 큐를 사용했을 때, $$O(E + VlogV)$$ 필요한 요소, 그래서 뭘 하면 되는데? 각 노드의 연결상태를 저장하는 행렬, 2차 배열. 시작 노드로부터 각 노드로의 누적 비용을 저장하는 리스트 방문한 노드를 저장하는 리스트 예시 초기 설정 출발 노드,..

알고리즘 2023.05.27

Algorithm 시작하기

자바 알고리즘 공부 시작? 하반기 공채지원을 위해서 다시 공부 시작 최근 코딩테스트에서 관련 업무에 맞는 언어로 제한되는 경우가 있다고 들었다. 백엔드는 Spring계열이면 Java, Kotlin 코딩테스트를 어떤 언어로 볼 지 고민 중이다. 자바 장점 Spring 구현에 간접적으로 도움이 된다. 앞으로 다가올 코딩테스트에서 제한이 걸릴 확률이 없다. 이 글을 작성하면서 네이버 신앱채용을 확인해보니깐 여전히 파이썬을 사용할 수 있다. 내가 취업을 준비할 때는 파이썬으로 응시할 수 있다고 판단되어 그냥 파이썬으로 준비해야겠다.

알고리즘 2023.05.27