기술 예상 질문 [ 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. 프림 알고리즘 (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(..

백 트래킹 기법의 이해 1. 백 트래킹 (backtracking) - 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 - 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - 상태 공간 트리를 탐색하면서,..