IT 방랑기

본 내용은 웹 서핑중에 발견한 소프트웨어 직군의 직무 면접에 대한 예상 질문과 답변을 정리한 내용입니다. [ 문제 ] - 데이터 베이스 1) DB 무결성과 정합성 설명 2) DB 무결성의 4가지 설명 3) DB 제약 조건의 종류와 무결성을 연관 설명 4) DB 정규화 단계 설명 5) 데이터 베이스 언어 (DDL, DML, DCL, TCL)에 대한 설명 6) 뷰 특징과 장단점 설명 7) 조인 (내부/외부 조인)에 대한 설명 8) JDBC와 ODBC의 차이점 설명 9) statement와 preparestatement의 차이점 - 웹 1) GET과 POST의 차이점 2) session과 cookie 차이점과 사용 용도 설명 3) HTML과 XML의 차이점과 장단점 설명 4) MVC 모델이란, 프레임워크란? ..

그래프가 주어졌을 때 시작 노드에서부터 종료 시점까지 최단 경로를 구할때 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘은 반드시 음수 사이클이 존재하지 않아야 한다. 만약 음수 사이클이 발생할 수 있다만 벨만 포드 알고리즘을 이용해야 한다. 다익스트라는 시작점으로부터 cost에 대한 min heap을 이용하여 가장 cost가 적은 순서대로 계속해서 길을 찾아보며 만약 도착 노드를 발견하는 순간 종료된다. 코드를 보자. 이 소스코드는 백준 최단 경로를 기반으로 하고 있다. #include #include #include #include using namespace std; typedef pair pii; #define ff first #define ss second #define mp(x, y) ma..

알고리즘에서 가장 기본이 되는 탐색 알고리즘인 DFS와 BFS에 대하여 정리한다. DFS는 깊이 우선 탐색으로 그래프가 주어졌을 때 함수 스택을 이용하여 현재 노드와 연결된 노드로 탐색하며, BFS는 너비 우선 탐색으로 큐를 이용하여 현재 노드와 연결된 노드들을 탐색한 다음 연결된 노드들에 연결된 노드들을 차례로 탐색한다. 그래프 V와 E가 주어졌을 때 배열으로 노드를 방문하였는 여부를 저장하여, 다시금 방문하지 않도록 강제한다. 그래프가 아래와 같이 주어졌다고 하자. A - B1 - C1 - B2 - C2 - B3 - C3 DFS는 A에 연결된 B1노드, 그리고 B1노드에 연결된 C1노드를 바로 탐색하기 때문에 트리의 순회에 자주 이용된다. 반면 BFS는 A노드에 연결된 모든 노드 B1, B2, B3를..

액션캠으로 가격대비 저렴한 SJ4000와 삼성 Evo plus 마이크로 SD 64GB 카드를 구매했다. 역시 국내 배송이어서 매우 빠르게 도착했다. 액션캠은 고프로가 유명하지만 괴랄한 가격으로 인하여 당연히 패스. 이미 듀란 아쿠아캠을 사용해보았고, 짭프로인 SJ4000은 친구가 사용하는 것을 계속해서 봐왔다. 아무리 생각해도 액션캠에 30~40만원을 투자하기엔 아깝기도 하고, 이미 짭프로에 대한 검증은 친구가 1년간 쓰면서 해주었기 때문에 고민하지 않고 구매했다. 구매를 위해서 상품을 찾아보면서 알아낸 재미있는 사실은 고프로를 카피한 SJCAM을 또 카피하여 SJ9000과 같은 제품을 팔고 있다. 다른 리뷰를 찾아보게 되면, 카피하면 할 수록 성능은 구렁텅이로 빠지는 것 같아서 SJCAM으로 마음을 굳..

구간합을 반복적으로 빠르게 계산하기 위해서 세그먼트 트리와 펜윅 트리를 이용한다. 세그먼트 트리와 펜윅 트리는 원래의 데이터 값을 저장하는 방법이 아니라, 이름에서 알 수 있듯 데이터를 구간별로 저장하는 형식을 가진다. 간단하게 말하여 부분합을 위하여 i번째까지의 데이터를 모두 합한 값을 유지하고 있다고 보면 된다. 세그먼트 트리는 리프노드에는 원래의 데이터를 그리고 그 부모 노드는 아래의 리프 노드들의 합을 저장하고 있다고 보면된다. 이러한 특징을 바탕으로 특정 구간의 값을 찾는 행위는 O(logN) 그리고 값을 변경 하는 행위 또한 O(lgN)만에 수행할 수 있다. 세그먼트 트리의 경우 필요 메모리량이 복잡하게 계산된다. Full binary tree의 경우 N이 2의 제곱꼴이면 2*N-1개의 노드가..

최소 신장 트리(MST, Minimum Spanning Tree)란? - 가중치가 있는 무향 그래프가 주어졌을 때 모든 노드를 연결하면서 간선의 가중치 합이 최소인 신장 트리를 뜻한다. 최소 신장 트리의 특징 1) 가중치의 합이 최소 2) N개의 노드에 대하여 N-1개의 간선으로 구성 3) 사이클이 존재하지 않아야 함 최소 신장 트리를 구하는 방법 그래프가 주어졌을 때 우리는 어떻게 최소 신장 트리를 찾을 수 있을까? 간단한 방법으로 가중치가 작은 간선을 선택할 수 있는지 확인하여 포함하는 Greedy 방식으로 MST를 구할 수 있다. * 가중치가 작은 순서대로 간선을 탐색하면서 Spanning Tree의 조건에 부합하는 간선만 선택 * 간선을 선택시에 사이클이 있는지 여부를 판단해서 해당 간선을 연결할..

트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다. 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다. 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다. 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 ..

정렬 알고리즘을 이야기하다보면, 항상 비교되는 두가지가 퀵 소트와 머지 소트이다. 일반적인 상황에서 두 정렬의 복잡도는 O(nlogn)으로 표기한다. 두 정렬을 구태여 비교하는 이유는 분할 정복(divide and conquer) 패러다임을 이용하기 때문이다. 임의의 배열이 있을 때 반으로 쪼개어 가면서 각 원소를 순서대로 배치하는데, 퀵 소트는 분할 이전 그리고 머지 소트는 분할 이후에 이를 순서대로 배치한다. 좀 더 쉽게 그림으로 보자. 왼쪽 머지 소트는 배열을 1/2씩 나눠가면서 정렬이 되었을 때까지 계속해서 나누어간다. 만약 원소가 1개가 된다면 부분 배열은 정렬된 상태이므로 그 다음부터는 합쳐가면서 다시금 배열을 조립한다. 이 합치는 과정은 각 부분 배열의 길이와 같으므로 O(N)이 걸리게 된다..

IEEE754는 부동소수점을 표현하는 표준으로, 일반적으로 사용하는 C, C++, Java와 같은 프로그래밍 언어의 대부분이 이를 사용한다. 부동 소수점외에도 우리에겐 익숙하지 않은 고정 소수점 표현 방식도 있는데, 이는 특정 자릿수에 소수점이 있다고 가정하고 이를 정수로 표현하는 방식이다. 예를 들어 10^3 위치에 소수점이 있다고 생각한다면 12000과 120을 나타내는 고정 소수점은 각각 12.000과 0.120을 뜻하게 된다. 반면 부동소수점은 이 소수점의 위치를 고정하지 않고 지수부와 가수부의 값에 의하여 변동되므로, 더 큰 값이나 세밀한 값을 표현할 수 있게된다. IEEE754에서는 부동 소수점을 3가지로 구성하는데, 최상위 비트부터 부호비트, 지수비트, 가수비트이다. 32비트 단정도와 64비..

정렬과 더블어 따라오는 탐색 중 바이너리 서치에 대하여 설명하고, 이를 구현한 코드를 포스팅한다. 탐색은 요구에 맞는 데이터를 찾는 과정으로, 실무나 프로젝트 또는 알고리즘 문제를 풀어본 사람들은 잘 알겠지만 가장 빈번하게 일어난다. 따라서 이러한 탐색에 필요한 시간 복잡도를 줄이므로써, 더욱 효율적인 프로그램을 작성할 수 있게 한다. 일반적으로 전체 탐색을 통하여 검색을 하는 경우 N개의 데이터에 대하여 O(N)의 시간 복잡도를 가진다. 하지만 정렬된 데이터에 대하여 키에 대한 값을 탐색하는 경우, 이를 O(lgN)으로 줄일 수 있으며, 사실상 lgN은 상수에 근접하므로 O(N) 탐색에 비하여 더욱 효율적이고 같은 시간내 다양한 작업을 할 수 있다. 바이너리 서치는 정렬된 데이터에서 탐색하는 크기를 반..