Simple in Complex with Simple

직무적성검사를 대비한 명료한 한(?) 문장 정리 및 링크를 통한 깊은 해설.

1. 엔디안(Endian)

- Byte Order를 뜻함. 

- 리틀 엔디안(Little Endian)과 빅 엔디안(Big Endian)이 존재.

- 리틀 엔디안은 메모리 시작 주소가 하위 Byte에서부터 기록(Intel, Window)

- 빅 엔디안은 메모리 시작 주소가 상위 Byte에서부터 기록(Unix)

- 하나의 시스템에서 돌아가면 상관없지만, 값을 주고받는 데이터 통신에서는 Byte Order가 무척 중요.

- int형(4byte)의 데이터 1을 보내도, 엔디안이 다르면 다른 값이 나옴. 왜냐하면 4byte라서 리틀 엔디안은 아래에서 위로 기록, 빅 엔디안은 위에서 아래로 기록. 그래서 1byte는 같아도, 나머지 byte에서 처리값이 차이가 나기 때문에 이상한 값이 나타남. 그래서 Char형(1byte)에서는 문제가 되지 않음.

- 이런 엔디안 문제에 따른 네트워크 통신으로 인해 네트워크 전용 엔디안(빅 엔디안)을 설정.

- 클라이언트 측은 네트워크 전용 엔디안으로 값을 변경 후 전송.

- 서버 측은 전송받은 값을 자신의 엔디안 값으로 변환 후 활용.

깊은 이해를 위한 링크: http://www.joinc.co.kr/w/Site/Network_Programing/Documents/endian

2. 구조체 패딩(Struct Padding)

- 패딩이란 빈 공간에 무언가를 채워넣는 것을 의미. (어깨에 넣는 뽕도 패딩이라 부르고, 파카에 털을 채우는 것도 패딩)

- 구조체 패딩의 문제는 네트워크를 통한 구조체 데이터를 전송할 때 문제가 발생.

- 왜냐하면 구조체가 메모리에 정의되는 형태는 OS와 컴파일러에 따라 달라진다. 

 (동일한 구조체를 서로 다르게 메모리에 정의하고 있는 시스템끼리 통신을 주고받으면 구조체 각 멤버는 서로 다른 값 가짐)

- 해결법 총 3가지 존재.

- 첫 번째 해결법, 프로그래머가 패딩 비트를 직접 설정.(최악의 방법 - 아주 위험함)

- 두 번째 해결법, #pragma pack(1)이라는 문구로 구조체를 1Byte로 자름.(성능이 안좋음, 표준도 아님)

- 세 번째 해결법, 구조체 멤버를 일일이 써주는 방법.

깊은 이해를 위한 링크: http://pangate.com/19

3. Race Condition(경쟁 상태)

- Race Condition은 두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓸 때, 데이터의 일관성을 해치는 현상.

- 회피 방법은 여러가지가 있지만 대표적인 방법으로는 Mutual Exclusion(상호배제), Critical Section(임계구역) 존재.

- Mutual Exclusion이란 두 개 이상의 프로세스가 공용 데이터 접근을 막음. (한 번에 하나씩 공용변수에 접근)

- Critical Section이란 공용 데이터에 접근하는 코드 영역으로 원자성을 띄고 있음. (이 구역에 접근은 한 번에 하나씩)

깊은 이해를 위한 링크: http://egloos.zum.com/agrumpy/v/362254

4. 컴파일 오류 vs 런타임 오류 vs 논리 오류

- 컴파일 오류란 프로그램의 실행을 막는 오류. (컴파일러가 이해하지 못하면, 컴파일러 오류. 형 변환 실패, ; 빠뜨리기 등등)

- 런타임 오류는 프로그램의 실행 중 나타나는 오류. (0으로 나누거나, 배열 index를 침범하거나, 스택 오버플로우 문제)

- 논리 오류는 코드의 흐름이 프로그래머의 의도와 다른 경우. (제일 어려운 경우)

깊은 이해를 위한 링크: https://msdn.microsoft.com/ko-kr/library/s9ek7a19(v=vs.90).aspx

5. 컴파일 과정과 인터프리터 과정

- 컴파일 과정

렉시컬 분석 -> [토큰열] -> 구문 분석 -> [파싱트리] -> 의미 분석 -> [중간코드 생성] -> 목적코드 생성 -> [목적프로그램]

- 인터프리터 과정

렉시컬 분석 -> [토큰열] -> 구문 분석 -> [파싱트리] -> 의미 분석 -> [중간코드 생성] -> 중간코드 실행 -> [실행결과]

깊은 이해를 위한 링크: http://ra2kstar.tistory.com/168

6. 언어의 종류

- 절차적 언어: C, Pascal

- 객체 지향 언어:  C++, JAVA, C#

- 선언형 언어: 함수형 언어, 논리 프로그래밍.

(선언형 언어는 이제 학계를 떠나 업계로 진출 중이다. 특히 신기술의 도입이 빠른 웹 앱 계열에서 선언형 스타일의 프로그램이 선호되고 Javascript 코드의 코딩 스타일이 점점 선언형으로 진화 중이다. 선언형으로 기술하는 가장 유명한 라이브러리로는 jQuery가 있으며 최신 트렌드인 반응형 프로그래밍 개념을 도입하고 있다.)

(순수 선언형, 함수형 언어의 가장 큰 특징은 '지연 평가(Lazy evaluation)'라는 특징이다. 계산이 필요한 순간이 올 때까지 미루는 개념인데, 쉽게 말해서 이 지연 평가의 강력함은 '무한'을 다룰 때 나타난다. 즉, 재귀의 스택 오버플로우를 예방하는 방식이다.)

- 함수형 언어: LISP, Scheme, Clojure, Erlang, ML, Haskell

- 논리 프로그래밍: Mercury

- 특수 목적 언어: SQL(DB), CUDA(GPU), Prolog(인공지능 언어), Processing(그래픽스), MATLAP(공학 시뮬레이션), PHP(웹)

깊은 이해를 위한 링크: https://namu.wiki/w/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4

7. 프로세스와 쓰레드

- 프로세스는 프로그램의 인스턴스를 의미, 운영체제로 부터 자원을 할당받는다.

- 프로세스의 영역은 코드 | 데이터 | 메모리(Heap & Stack)를 가진다.

- 쓰레드는 경량 프로세스라고 불리며, 한 프로세스에서 동작되는 여러 실행의 흐름을 나타냄.

- 쓰레드들은 프로세스의 코드 | 데이터 영역을 공유하지만, 자신의 실행을 위한 실행 스택을 각각 따로 할당받음.(*)

- 기본적으로 하나의 프로세스 생성되면 하나의 쓰레드가 같이 생성, 이를 메인 쓰레드라 하며 프로그램 코드는 여기서 실행.

깊은 이해를 위한 링크: http://ralf79.tistory.com/34

8. OSI 7계층 과정

- 물리층 - 데이터링크층 - 네트워크층 - 트랜스포트층 - 세션층 - 프리젠테이션층 - 애플리케이션층

- 물리층: 네트워크의 하드웨어 전송 기술이 주를 이룸.

- 데이터링크층: 네트워크 카드의 주소인 MAC주소(물리적 주소)를 기반으로 데이터를 전달. (네트워크 브릿지와 스위치 작동)

(네트워크 위 개체들 간의 데이터를 전달하고, 물리 계층에서 발생할 수 있는 오류를 찾아 수정)

- 네트워크층: 논리적 주소 IP를 활용하며 데이터를 전송하며 라우팅이 일어난다. (라우터가 이 계층에서 수행)

- 트랜스포트층: 신뢰성 있는 데이터를 주고 받게 해줌. (UDP/TCP 프로토콜)

- 세션층: 네트워크 양 끝의 응용 프로세스가 통신을 관리하기 위한 방법 제공. (연결 시작 - 유휴 - 종료등을 수행)

- 프리젠테이션층: 코드간의 번역을 담당하여 인코딩, 암호화 또는 복호화같은 과정이 이루어짐. 

- 애플리케이션층: 응용 프로세스와 직접 관계된 응용 서비스를 제공. (텔넷 프로토콜)

깊은 이해를 위한 링크: https://ko.wikipedia.org/wiki/OSI_%EB%AA%A8%ED%98%95

나열하기란 조건에 맞는 모든 경우를 시도해보고 답을 찾는 일을 말한다.

이 방법은 답을 찾는 것은 오래 걸리지만 확실한 방법이다.

나열하기의 대표적인 종류로는 우리가 중, 고등학교 시절에 배웠던 순열, 조합, 중복순열, 중복조합이다.

이 코드의 틀이 가장 대표적인 나열하기의 틀이다.

각각의 방식에 따른 Subset을 풀어야하는 알고리즘에 대입하고 그 알고리즘을 거증하고, 완성시킨다.

재귀적 프로그래밍을 많이 사용하므로 재귀적 프로그래밍에 익숙해야 한다.

이 나열하기의 방식은 모든 경우를 다 따지는 것이므로 그 수행속도가 데이터의 크기에 따라 수없이 오래 걸린다.

하지만 이 나열하기의 방식을 조건에 맞게 가공하여 그 수행속도를 빠르게 할 수 있다면, 

이 시도가 퍼즐 알고리즘을 풀어내는 중요한 틀이 된다.

퍼즐 알고리즘은 무척 중요하다. 

왜냐하면 기업에서 프로그래머를 뽑을 때, 등장하는 대표적인 문제의 형태이기 때문이다.

이번에 치른 코딩테스트도 퍼즐 알고리즘에 대한 작성이었다.

그 때는 퍼즐 알고리즘이나 이 퍼즐에 대한 파트가 있는지도 모르고, 그냥 무작정 코딩하기 시작했다.

끝나고 꼭 한 번 제대로 찾아봐야지라고 생각했었는데, 막상 찾고보니 갈 길이 멀다.

하지만, 그 때의 문제를 풀면서 정말 궁금하고 몰랐던 방법론을 발견했다.

역시 책은 만인의 스승님이시다.

아무튼, 퍼즐 문제가 기업의 대표적인 테스트 문제로 많이 나타나는 이유는 이렇다.

문제의 제약조건을 잘 이해하고, 꼼꼼히 체크해야하며, 추론을 통해서 가장 효율적인 방법을 찾아 답을 구해야 한다.

위의 3가지 방식이 좋은 프로그래머인지 구분하는 정말 중요한 요소라는 것을 다시 알았다.

아직 퍼즐 이론에 대해서 많은 것을 알지 못하지만, 지금껏 해왔던 것처럼.

모르면 배우면 되니까. 아직 학생이니까.

다시 배우자.

1. 개요

이 문제는 어제 풀었던 순열(Permutation) 문제를 아주 약간 비틀어 생각하는 문제다.

그러므로 쉬움. (계속 쉽다고 생각하자)

복습과 반복겸, 그리고 특수 상황에 따라 종료조건 또는 분기조건을 바꿈으로서, 새로운 결과를 만들어 낼 수 있다.

한 번 생각해보고 풀어보기.

2. 문제

대통령 선거에 후보 A와 B가 출마하였다. 이 때, A가 m표를 B가 n표를 득하였다. (1 <= n <= m)

이 경우에서 투표함을 한 표씩 꺼내어 볼 때, 그때까지 나온 갑의 표가 항상 을의 표보다 많은 경우를 출력하라.

3. 코드 및 출력

3-1) 코드

3-2) 출력

4. 정리

기초 순열 알고리즘을 정확히 알았다면, 빠르게 풀어낼 수 있을 것 같다.

아침 뇌 활성화겸 좋은 문제였다.

1. 개요

모든 괄호쌍 알고리즘은 카탈란 수 알고리즘에 속함.

카탈란 수 알고리즘이란 점화식이 다음과 같은 모습을 지닐 때를 지칭함.

Cn = 시그마(0 ~ n-1) Ci * Cn-1-i

이렇게 표현하면 정말 수학적 기호도 없고 너무 어려워 보이기에 쉽게 말로 표현하면

한 가지 경우를 시행하면, 그와 쌍이되는 다른 경우를 반드시 시행해야 하는 모든 개수.

말 또한 어렵기 때문에 괄호쌍을 예를들면,

만약 ( 괄호가 나오면 반드시 ) 괄호가 나와야 함. 

( 이 두 번 나오면 ) 도 반드시 두 번 나와야 함.

이처럼 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다.

괄호쌍 알고리즘도 이에 속하며, 괄호쌍 2개로 예를들면 다음과 같다.

( ( ) )

( ) ( )

단, 이 두 가지 경우뿐이다.

카탈란 수의 정확한 수학적인 성질은 알 수 없지만, 카탈란 수를 나타내는 경우들이 2개 더 있다.

(1) 첫 번째는 2차원 배열에서 한 지점 A에서 B까지 가는 최단경로의 수다.

왜냐하면, A에서 B지점까지 최단경로로 도착하기 위해선 단 두 가지 방향의 쌍으로 이루어진다.

가장 간단히 다음과 같은 배열이 있다.

0 0 B

0 0 0

A 0 0

여기서 A에서 B로 최단경로로 도착하려면, 오른쪽아니면 위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭된다.

그렇기에 카탈란 수에 속한다.

(2) n개의 노드로 이루어진 이진 탐색트리(Binary Search Tree)

괄호쌍이나 2차원 배열 최단경로 수랑은 조금 다르다. 왜냐하면 자식노드의 왼쪽 오른쪽 쌍의 개수가 대칭을 이루지는

않는다. 하지만, 다음의 예를보면

왼쪽 자식 노드 0개, 오른쪽 자식 노드 n-1개.

왼쪽 자식 노드 1개, 오른쪽 자식 노드 n-2개.

왼쪽 자식 노드 2개, 오른쪽 자식 노드 n-3개.

..................

왼쪽 자식 노드 n-1개, 오른쪽 자식 노드 0개.

트리의 구조가 대칭쌍을 이루기에 카탈란 수에 속한다.

2. 문제

2-1) 입력한 괄호쌍 개수에 따른 경우를 모두 출력하는 알고리즘을 작성하시오.

2-2) 카탈란 수를 알고리즘을 작성하시오.

3. 코드 및 출력

3-1) 괄호쌍 코드

3-2) 괄호쌍 출력

3-3) 카탈란 수 코드

3-4) 카탈란 수 출력

4. 정리

이것으로 3장까지 독파했다. 내일부턴 4장.

참 시간은 많은데, 시간이 왜캐 부족하게 느껴질까.

주어진 시간동안 파이팅.