기술 예상 질문 [ Programming ] 1. 프로그램이란 ? 컴퓨터가 사람 일을 할 수 있게 해주는 것 컴퓨터에 처리되는 작업의 순서를 논리적으로 명령어로 작성하는 것 2. 객체 지향 프로그래밍 언어 특징? 캡슐화 데이터와 데이터를 처리하는 함수를 하나로 묶는 것 캡슐화된 객체들은 재상용이 용이 정보 은닉 캡슐화에서 가장 중요한 개념 다른 객체에게 자신의 정보를 숨기고 자신의 연산만을 통해 접근 허용 추상화 = 모델화 불필요한 부분을 생략하고 객체의 속성 중 가장 중요한 것에만 중점을 두어 개략화 데이터의 공통된 성질을 추출해 슈퍼 클래스를 선정 상속성 이미 정의된 상위 클래스의 모든 속성과 연산을 하위 클래스가 물려받는 것 하위 클래스는 상위 클래스의 모든 속성과 연산을 자신의 클래스 내에서 다시..

시간복잡도 -> 실행 시간이라는 관점에서 알고리즘의 효율 측정 -> 문제를 해결하려고 할 때마다 시간복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있다 -> 이때 가장 중요한 건 연산자의 숫자 혹은 연산과정의 수 -> 예를 들어 N이라는 인자가 주어졌을 때 1부터 N까지를 더하는 함수를 sumOfN을 정의 def sumOfN(N): theSum = 0 for i in range(1,N+1): theSum += i return theSum ->함수 sumOfN에서 주요 연산 횟수를 보면 아래와 같습니다 def sumOfN(N): theSum = 0 for i in range ( 1, N+1): theSum += i return thesSum 함수 sumOfN의 시간 복잡도는 아래와 같이 표시 가능 ..

탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 - 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 문제2: 부분 배낭 문제 (Fractional Knapsack Problem) - 무게 제한이 k인 배..

1. 최소 신장 트리 ( Minimum Spanning Tree ) 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다. 이전 글에서 살펴봤던 BFS, DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다. MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다. 이해를 돕기 위해 예제를 살펴보도록 하겠습니다. 2. 주요 용어 MST에서 핵심이 되는 용어는 안전간선(Safe edge)입니다. 안전간선을 정의하기 위해서는 4가지의 용어가 필요하므로, 이 용어들을 살펴보고 안전간선을 정의하도록 하겠습니다. 1) 단절 단절은 트리의 모든 정점들의 집합을 V라고 할 때, 어떤 ..

최소 신장 트리의 이해 1. 프림 알고리즘 (Prim's algorithm) - 대표적인 최소 신장 트리 알고리즘 - Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) - 프림 알고리즘 - 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 - Kruskal's algorithm 과 Prim's algorithm 비교 - 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) - Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 M..

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V^2)O(V2)의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, O((V+E)logV)O((V+E)logV)(V는 정점의 개수, E는 한 정점의 주변 노드)의 시간복잡도를 가지게 되었다.[1] O((V+E)logV)O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(..