[SKCT] SW직군역량검사

1. 정렬 알고리즘

1). 선택정렬(Selection Sort)

현재 위치부터 배열의 끝까지 탐색하여 현재 위치에 들어갈 값을 찾아 정렬한다.

정렬되어 있지 않은 크기 n의 배열을 정렬한다고 가정할 때, i번 인덱스에 i ~ n-1번까지의 배열의 값중 가장 작은 값을 찾아 교환한다.(왼쪽에서부터 작은 값으로 정렬)

배열의 모든 인덱스를 한 번씩 돌면서(n) * 해당 인덱스 이후의 값을 탐색(n-i)하므로 시간 복잡도는 O(n^2)이다.

2). 삽입정렬(Insert Sort)

현재 위치의 값과 그 이하의 배열을 비교하여 자신의 위치를 찾아 정렬하는 방법이다.

정렬되어 있지 않은 크기 n의 배열을 정렬한다고 가정할 때, 두번째 인덱스 i부터 시작하여 0 ~ i-1번까지의 배열값과 비교하여 알맞은 위치에 삽입한다. 즉, i를 기준으로 0 ~ i-1까지의 값은 정렬되어 있다.

배열의 모든 인덱스를 한 번씩 돌면서(n) * 해당 인덱스 이전의 값을 탐색(최대 n-1)하므로 시간 복잡도는 O(n^2)이다.

3). 버블정렬(Bubble Sort)

인접한 두개의 값을 비교하여 정렬해나가는 방식이다.

정렬되어 있지 않은 크기 n의 배열을 정렬한다고 가정할 때, (1). i와 i+1의 값을 비교하여 두 값중 큰 값을 i+1로 배치한다.
(2). 다음으로 i+1과 i+2의 값을 비교하여 i+2에 큰 값이 오도록한다.
(1), (2)를 반복하여 가장 큰 값이 배열의 맨 마지막에 순서대로 정렬되도록 한다.

i가 0부터 n-1까지 i, i+1값을 비교해나가므로 (n-1) * 비교를 총 n번 진행하므로 시간 복잡도는 O(n^2)이다.

4). 합병정렬(Merge Sort)

분할 정복 방식으로 배열을 반씩 쪼개가며 최소 단위로 쪼갠 후, 쪼갠 배열을 정렬하여 병합하는 방법이다.

크기가 n인 배열을 정렬할 때, n/2로 쪼개는 것을 계속하면서 ((n/2)+(n/2)이므로 logn) * n번의 병합과정을 가지므로 시간복잡도는 O(nlogn)이다.

5). 퀵정렬(Quick Sort)

(1). 분할 정복 방식으로 pivot값을 정하여(보통 배열의 맨 왼쪽, 오른쪽, 가운데 값중 하나) pivot보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬한다.
(2). pivot보다 작은 값이 왼쪽에 남아있지 않고, 큰 값이 오른쪽에 없는 경우( 정렬할 값이 남아 있지 않는 경우) pivot을 기준으로 쪼개어 다시 (1), (2)번 과정을 반복한다.
이 과정을 반복하여 분할된 배열의 크기가 1이 되면 정렬이 완료되었다고 볼 수 있다.

크기가 n인 배열을 정렬할 때, 정렬을 진행하여(n) * pivot을 기준으로 왼쪽과 오른쪽으로 쪼개므로 ((n/2)+(n/2)이므로 logn) 시간복잡도는 O(nlogn)이다.

단, 이미 정렬된 배열을 퀵 정렬할 경우 분할이 logn번이 아닌, n번 일어나므로 최악의 경우 시간복잡도는 O(n^2)이다.

2. 논리회로

1). 불 대수

불 대수란 논리식을 전개하여 참 또는 거짓을 판단하는 방법으로 교환법칙, 결합법칙, 분배법칙, 멱등법칙, 보수법칙, 항등법칙, 콘센서스, 드모르간, 복원법칙 등이 존재한다.

(1). 보수법칙 : A+A’ = 1, AA’ = 0
(2). 멱등법칙 : A+A = A, AA = A
(3). 드모르간 : (A+B)’ = A’B’, (AB)’ = A’+B’
(4). 콘센서스 : AB+BC+CA’ = AB+CA’, (A+B)(B+C)(C+A’)=(A+B)(C+A’)

2). 논리 게이트

3. TCP/IP 4계층

TCP/IP는 인터넷 통신규약이다.
데이터의 흐름을 관리하고 정확성을 확인(TCP)하며, 목적지에 패킷을 보내는 역할(IP)을 한다.

1 계층. 네트워크 엑세스 계층

(송신) 데이터링크 계층에서 물리적인 주소로 MAC을 사용하여 헤더를 추가하여 프레임을 만들고, 프레임을 하위계층인 물리계층으로 전달한다.

(수신) 데이터링크계층에서 추가된 헤더를 제거하여 상위 계층인 네트워크 계층으로 프래임을 전달한다.

2 계층. 인터넷 계층

네트워크 상에서의 패킷을 제어하고 라우팅 기능을 담당한다.
TCP/IP의 IP가 여기 속한다. 전송계층에서 받은 패킷을 목적지까지 효율적으로 전달하는 것만을 고려하므로 비신뢰성과 비연결성이라는 특징을 갖는다.

※ IP : 데이터그램(패킷 데이터)를 정의하고, 전송을 위한 경로를 설정한다.

3계층. 전송 계층

네트워크 양단의 송수신 호스트 사이에서 신뢰성 있는 데이터의 전송 기능을 제공한다.
TCP/IP의 TCP가 여기 속한다.

※ TCP vs UDP
TCP는 정확한 패킷의 전송을 위해 패킷 헤더 부분에 패킷의 일련번호 같은 정보를 포함하지만, UDP는 패킷 헤더에 추가정보가 저장되지 않으므로, 패킷의 정확한 전송을 보장하지 않는다.
데이터의 정확한 전송보다 빠른 속도의 전송이 중요할 때 TCP보다 UDP의 사용이 유용하다.

4계층. 응용 계층

TCP, UDP 기반의 응용 프로그램을 구현할 때 사용한다.
FTP, HTTP, SSH 등이 여기 속한다.

※ OSI 7계층과 TCP/IP 4계층

4. OSI 7계층

각 계층의 변화는 다른 계층에 전혀 영향을 주지 않는다.

1계층. 물리 계층

데이터링크 계층으로 부터 받은 데이터를 통신회선을 통해 비트단위로 전송하는 계층
케이블이나 연결장치 등의 전기적 항목을 정하고 네트워크 상의 두 노드를 물리적으로 연결시켜주는 역할을 한다.

2계층. 데이터링크 계층

인접한 개방형 시스템 사이에서 프레임을 오류 없이 전달하는 계층으로 신뢰성 있는 데이터의 전송을 제공한다.
물리주소, 네트워크 토폴로지, 오류검출, 프레임 전달, 흐름제어, 순서 제어, 데이터흐름 제어 등의 데이터 전달(이때 전달은 기지국대 기지국)을 감독한다.

※ 프레임 : 상위 네트워크 계층으로부터 전송단위인 패킷을 받아들이고, 의미있는 정보(비트)들을 패킷의 앞뒤에 추가시킨 전송단위

3계층. 네트워크 계층

데이터링크 계층이 제공하는 인접한 개방형 시스템 간에 데이터 전송기능을 이용하여 연결, 통신경로 선택을 제공한다. 데이터 전송 및 중계, 여러 개의 네트워크를 경유할 경우 네트워크 품질 차이 조정 기능을 수행
라우팅 프로토콜이 서로 연결된 네트워크를 통한 최적의 경로를 선택하여 송신을 진행
네트워크 층은 각 패킷이 시작지점에서 최종 목적지까지 성공적이고 효과적으로 전달하게 하며, 패킷의 송신 및 수신을 감독한다.

4계층. 전송 계층

오류제어, 흐름제어를 발신지 대 목적지 수준에서 감독하며, 전체 메시지가 완전히 바른 순서로 도착하는 것을 보장한다.
네트워크 상에서 신뢰성있는 데이터의 전송 문제와 관련된 계층이다. 즉, 전체 메시지의 발신지 대 목적지 전달을 책임진다.

5계층. 세션 계층

네트워크의 대화 제어자로서 통신 장치들 간의 상호작용을 설정하고 유지하며 동기화 한다.
어플리케이션 간의 세션을 구축하고 관리하며 종료시키는 역할을 한다. 즉, 사용자(프로세스) 연결이 유효한지 확인하고 설정하여 세션이라는 가상 연결을 확립하고 동기화하는 기능을 제공한다.
표현 계충 사이의 대화를 동기화시키며 데이터의 교환을 관리한다.

6.계층. 표현 계층

두 장치 간에 서로 다른 제어코드와 문자 및 그래픽문자 등을 위하여 번역을 수행하여 두 장치가 일관되게 전송 데이터를 이해할 수 있도록 한다. 즉, 송수신자가 공통으로 데이터를 이해할 수 있도록 표현 방식을 변환한다.
데이터의 암호화, 복호화, 압축, 해제 등을 수행

7계층. 응용 계층

사용자 또는 응용 프로그램이 네트워크에 접근할 수 있도록 사용자 인터페이스를 제공한다. (전자우편, 파일전송, 공유데이터베이스 관리 등)
응용 프로세스가 네트워크 환경에 접근하는 수단을 제공함으로써 응용프로세스들이 상호간 유용한 정보교환을 할 수 있도록 한다.

5. 데이터베이스

1). 무결성 제약조건

6. 기타 수식

1). 이진수의 음수변환

이진수로 표현된 11100001을 십진수로 표시하자.

(1). 맨 앞자리가 1이므로 음수임을 알 수 있다. (2). 절대값 구하기 : 보수를 취하고 1을 더한다.

즉, 00011111로 -31이 된다.

2). Byte 단위

B < KB < MB < GB < TB

7. IT기술 용어

- Header Translation : IPv4와 IPv6망 사이의 연동기술로 IPv4클라이언트가 IPv6서버에 접속할 때 또는 IPv6클라이언트가 IPv4서버에 접속할 때 사용된다.

- Tunneling : IPv6를 사용하는 두 컴퓨터 사이의 통신 과정에서 IPv4의 네트워크를 통과할 때 사용되는 전략으로, IPv6 패킷이 IPv4 영역을 통과하기 위해 IPv4 패킷 내에 캡슐화 된다. 그 영역을 통과하고 나올 때 역캡슐화 된다.

- Packet Handling : 패킷 단위의 데이터 처리 기법

- Dual Stack : 하나의 시스템에서 IPv6와 IPv4를 동시에 처리하는 기법이다.

- Multi Thread : 1개의 응용 프로그램이 스레드로 불리는 처리단위를 복수 생성하여 복수의 처리를 병행하는 것

- 애드혹 : 라우터 장비 없이 무선 기반의 이동간말기 간의 연결망의 일종으로서, 노드들에 의해 자율적으로 구성되는 기반 구조 없는 네트워크다. 험난한 지형이나 위험한 장소에서 네트워크 구성에 용이하다. 네트워크에 사용되는 노드들은 무선 인터페이스를 사용하여 통신하고, 이동이 자유로워 네트워크 토폴로지가 동적으로 변화되는 특징이 있다.

- 지그비 : 근거리 통신을 지원하는 국제 표준

- 핫스팟 : 무선으로 초고속 인터넷을 사용할 수 있도록 전파를 중계하는 무선랜 기지국

- SON(Self Original Network) : 상황에 스스로 적응하는 통신망을 구축하는 네트워크

- UC(Unified Communication) : 이용자의 위치에 상과없이 언제나 실시간 접근 및 단일 인터페이스를 통한 통합 메시지 처리, 다양한 매체의 접속을 지원하는 통합 솔루션