Tech blog

# 그래프의 기본 구조: 노드Node와 간선Edge로 표현되며 이때 노드를 정점Vertex라고도 말한다.그래프를 표현하는 방식인접행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결관계 표현인접리스트(Adjacency List): 리스트로 그래프의 연결관계 표현 인접행렬Adjacency MatrixINF = 1e7 # 무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph)인접리스트(Adjacency List)# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현graph = [[] for _ in range(3)]# 노드 0에 연결된 노드 정보 저장graph[0]...

# 1. 가장 빠른 길 찾기최단 경로 알고리즘: 가장 짧은 경로를 찾는 알고리즘 ('길 찾기')다양한 종류가 있지만, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데각 지점은 '노드', 지점 간 연결된 도로는 '간선'으로 표현된다.코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 컴퓨터공학과 학부 수준에서는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지를 배운다.본 책에서는 가장 많이 등장하는 유형인 최단 경로와 플로이드 워셜 알고리즘만 배운다.더불어, 앞서 공부한 그리드 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로에 그대로 적용된다는 특징이 있다..

중복되는 연산을 줄이자컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적이다.따라서 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘이 필수적이다.프로그래밍에서 '다이나믹'이란, '프로그램이 실행되는 도중에'라는 의미이다. (ex. 동적할당)그러나 다이나믹 프로그래밍은 이와 관련이 없다. # 예시다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. $$a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1$$ 그럼, 코드로는 어떻게 구현할 수 있을까?가장 쉽게 생각할 수 있는 방법은 바로 재귀함수일 것이다.  그러나 코드를 이와 같이 짜면 심각한 문제가 생긴다.바로 n이 커지면 커질수록 수행시간이 기..

보호되어 있는 글입니다.

# 1. 당장 좋은 것만 선택하는 그리디그리디(Greedy) 알고리즘: 탐욕적 알고리즘의 뜻은, '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.따라서, 매순간 가장 좋아보이는 것을 선택하게 되며, 현재의 선택이 미래에 어떤 영향을 미칠지 고려하지 않는 것이다.따라서 그리디 알고리즘은 '정당성 분석'이 중요하다.단순히 현재 best를 선택해도 그게 최적의 해가 되는지 검토가 필요하다는 소리이다! 코딩 테스트에서 그리디 알고리즘의 문제유형은'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이다.반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은이미 그 알고리즘의 사용방법을 정확하게 알아야 하는 경우가 많다.또한, 그리디는 기준에 따라 좋은 것을 선택하는 알고리즘이므로문..

✅ 우선순위 큐 ADT 우편배달부: 우체국에서 그날 배달해야 할 우편물들을 가방에 넣어 우체국을 출발해서 배달처를 돌며 배달함 배달부A: 우체국에서 가방에 우편물을 담을 때 아무렇게 (fast), 배달 과정에서는 그때그떄의 배달처에 맞는 우편물을 찾아야 하니까 시간 걸림 (slow) 배달부B: 우체국에서 가방에 우편물을 담을 때 배달처 주소 순서대로 차곡차곡 (slow), 배달 과정에서는 차례로 꺼내면 되기 때문에 시간 절약 (fast) 또 다른 예로는, 거둬들인 시험 답안지 100장을 학번 순서대로 점수표에 입력한다고 할 때 교수A: 답안지 더미에 놓인 순서대로 채점(fast), 채점완료된 답안지 더미에서 학번 순서대로 찾아내 점수표에 입력함 (slow) 교수B: 채점을 마친 답안지를 학번 순으로 쌓고..