helloahram

컴퓨터는 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드 machine code 를 실행한다컴파일러는 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영 체제의 관례 등에 따라 기계어 코드를 생성한다어셈블리 코드로 프로그램을 짤 때는 프로그래머가 계산을 하기 위해 사용해야 하는 저급 인스트럭션들을 명시해야 한다 대개의 경우 고급 언어가 제공하는 높은 수준의 추상화를 사용하는 것이 보다 더 생산적이고 안정적이다 어셈블리 코드를 이해하면 1) 컴파일러의 최적화 성능을 알 수 있으며 2) 코드에 내재된 비효율성을 분석할 수 있다 쓰레드 패키지를 사용해서 동시성 프로그램을 작성할 때 어떻게 프로그램의 데이터가 공유되고, 쓰레드들이 이들을 사적 Private 으로 어떻게 유지하고, 공유된 데이터가 정..

최소 신장 트리 MST, Minimum Spanning Tree가중치가 있는 연결 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에간선들의 가중치 합이 최소가 되는 트리즉, 스패닝 트리 중 간선의 가중치 합이 최소인 트리스패닝 트리 Spanning Tree 그래프 내의 모든 정점을 포함하는, 그래프의 최소 연결 부분 그래프 n 개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) 이고, (n-1) 개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다 -> 스패닝 트리!MST 특징1. n 개의 정점을 가지는 그래프에서 최소 신장 트리는 n-1 개의 간선을 가진다(단, 모든 정점이 반드시 연결된 경우에만 성립하며, 가중치가 음수인 경우는 해당되지 않는다)2. 사이클이 없고 모든 정점이 연결되..

CH01 컴퓨터 구조를 알아야 하는 이유01-1. 컴퓨터 구조를 알아야 하는 이유문제 해결 능력을 배양할 수 있다 - 컴퓨터를 미지의 대상이 아니라 분석의 대상으로 인식하고 개발할 수 있다성능, 용량, 비용을 고려한 프로그래밍을 할 수 있다 01-2. 컴퓨터 구조의 큰 그림 컴퓨터가 이해하는 두 가지 정보1) 데이터- 숫자, 문자, 이미지, 동영상과 같은 정적인 정보- 컴퓨터와 주고받는/ 내부에 저장된 정보를 데이터라 통칭하기도 한다2) 명령어- 컴퓨터를 실질적으로 움직이는 정보- 데이터는 명령어를 위한 일종의 재료  컴퓨터의 네 가지 핵심 부품1) 메모리- 프로그램이 실행되기 위해서는 메모리에 저장되어 있어야 한다- 메모리는 실행되는 프로그램의 명령어와 데이터를 저장한다 - 메모리에 저장된 값의 위치는..

1. 문제그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V M 개의 줄에는 간선이 연결하는 두 정점의 번호가 주어지고, 입력으로 주어지는 간선은 양방향이다1 2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 깊이 우선 탐색3. 접근 방식DFS (Stack 이용) 와 BFS (deque 이용) 를 공부한 김에 관련 문제를 풀어봤다DFS, BFS 개념 정리 [TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Se..

플로이드 와샬 Floyd Warshall 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘거쳐가는 정점을 기준으로 최단 거리를 구한다  플로이드 와샬 특징 1. 시작 정점과 도착 정점의 구분 없이 모든 경로에 대한 최단 경로를 구하는 데 사용된다2. 동적 계획법을 사용하여, 경로가 점차적으로 개선되면서 최단 경로를 찾는다3. 음수 가중치를 갖는 그래프에서도 동작하지만, 음수 사이클이 있으면 알고리즘이 제대로 동작하지 않는다  (음수 사이클 - 음수 가중치를 갖는 경로로 인해 무한히 작은 경로가 생기는 경우)4. 시간 복잡도 가 O(N^3) 으로, 정점의 수가 적을 때는 효율적이지만 정점 수가 많을 수록 비효율적일 수 있다 5. 인접 행렬로 표현하여 사용되며, 행렬의 각 값은 두 정점 사이의..

1. 문제1번부터 N번까지의 도시와 M개의 단방향 도로가 존재할 때 (모든 도로의 거리는 1이다)특정한 도시 X로부터 출발하여 최단 거리가 K인 모든 도시의 번호를 구하는 프로그램을 작성하시오2  2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 최단 경로* 데이크스트라 3. 접근 방식Week02 퀴즈 주제인 다익스트라를 이용하여 문제를 푸려고 한다 4. 전체 코드첫번째 시도 다익스트라 함수를 별개로 구현하고, N, M, K, X 를 입력 받아 딕셔너리 형태로 graph 를 만들었다 그리고 딕셔너리에서 items() 로 node 와 edge 를 꺼내 edge 와 K 를 비교해서 result list 에 append 하고, 나중에 .join() 으로 정리해서 print 했다import h..

MAC VScode 에서 변수명을 한꺼번에 바꿀 때 사용하는 간편한 방법  1. 똑같은 단어를 선택하고 2. Command + Shift + L 을 누르고 3. 단어를 변경하면한꺼번에 변경된다!

다익스트라를 공부하는데 코드 구현에서 heapq 가 나와서 정리한다 힙큐 heapq최대값과 최소값을 찾는 연산에 특화된 완전 이진 트리 우선순위 큐를 위해 만들어 자료 구조이다  최소힙 Min Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 것최대힙 Max Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 것 힙큐는 최소힙 자료 구조를 이용한다  heapq 메서드1. heapq.heapify(iterable)원래 있던 리스트를 힙으로 사용하기 위해 힙화 (heapify) 진행Heapify 의 디폴트 값은 최소힙이다import heapqheap2 = [5, 2, 1, 3, 8]heapq.heapify(heap2)print(heap2) # 결과 출력 [1, 2, 5, 3, 8..

다익스트라 Dijkstra최단 경로 Shortest Path 탐색 알고리즘 가중 방향 그래프 G = (V, E) 에서 모든 간선의 가중치가 음이 아닌 경우에 단일 출발점 최단 경로 문제를 푼다  다익스트라 특징1. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 2. 가중치가 음수인 경우는 적용이 될 수도 있고 안 될 수도 있다3. 무방향 그래프, 방향 그래프 모두 사용 가능하다  다익스트라 동작 과정1. 시작 정점 설정 - 시작 정점을 설정하고, 그 정점에서 다른 모든 정점으로 가는 최단 거리를 계산한다                 처음에는 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리는 무한대로 설정2. 미방문 정점 중 최단 거리 선택 - 아직 방문하지 않은 ..

위상 정렬 Topology Sort순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 DAG 에만 적용이 가능하다  DAG Directed Acyclic Graph 방향이 있는, 비순환적인 그래프대학교의 선후수 과목에 비유할 수 있다전자회로 과목은 회로이론과 기초전자회로실험 과목을 이수해야 수강이 가능하다 여기에서 회로이론과 기초전자회로실험의 수강 순서는 중요하지 않다  진입 차수와 진출 차수위상 정렬 동작 과정을 보기 전에 진입 차수와 진출 차수에 대한 개념을 먼저 알아 두어야 한다 진입 차수 Indegree 는 노드로 들어오는 간선의 개수이고진출 차수 Outdegree 는 노드에서 나가는 간선의 개수이다 위상 정렬 동작 과정1. 진입 차수가..