참고
알고리즘이란?
NOTE
“특정한 문제를 해결하기 위한 명확한 명령의 집합으로서, 주어진 입력에 대하여 유한한 시간 내에 원하는 출력을 생성하는 절차”
•
위에 문장을 자세히 살펴보고 이해하면, 좋은 알고리즘을 만들려면 어떤 것들을 고려해야되는지 알 수 있다.
특정한 문제
NOTE
데이터 정렬, 최단 경로 찾기, 문자열 검색 등 알고리즘으로 설계해서 해결할 수 있는 문제를 의미한다.
•
다른 말로 하면, 알고리즘으로 풀수 없는 문제가 있다는 것을 의미한다.
•
이러한 문제들은 “게산 불가능한 문제”라고 한다.
◦
이 문제들은 원천적으로 어떤 알고리즘을 사용하더라도 합리적인 시간내에 해결될 수 없다.
◦
ex) Halting Problem
모호한 명령 vs 명확한 명령
NOTE
알고리즘은 일련의 명령으로 구성되며, 각 명령은 구체적이고 모호하지 않아야 한다!
모호한 명령
함수 findElements(배열):
배열 안의 숫자들을 조합하여
합이 0이 되는 세 수를 찾아서
그 세 수를 반환하라
Java
복사
문제: 주어진 정수 배열에서, 합이 0이 되는 서로 다른 세 수를 찾아 반환하라.
•
모호한 명령은 여러 해석이 가능하도록 만든다.
•
ex) “새로운 책을 책장에 놓아라” ⇒ 어느 위치, 어떤 방향으로 놓아야 하는가?
•
문제 해결 방식이나 구체적인 접근 방법에 대한 힌트를 제공하지 않기 때문에, 구현자에게 많은 해석의 여지를 남긴다.
명확한 명령
함수 findElements(배열):
결과 = 빈 리스트
배열을 오름차순 정렬
for i = 0 to 배열의 길이 - 3 do
// 중복된 값 건너뛰기
if i > 0 and 배열[i] == 배열[i-1] then
continue
왼쪽 = i + 1
오른쪽 = 배열의 길이 - 1
while 왼쪽 < 오른쪽 do
합 = 배열[i] + 배열[왼쪽] + 배열[오른쪽]
if 합 == 0 then
결과에 [배열[i], 배열[왼쪽], 배열[오른쪽]] 추가
// 중복된 값을 건너뛰기
while 왼쪽 < 오른쪽 and 배열[왼쪽] == 배열[왼쪽+1] do
왼쪽 증가
end while
while 왼쪽 < 오른쪽 and 배열[오른쪽] == 배열[오른쪽-1] do
오른쪽 감소
end while
왼쪽 증가
오른쪽 감소
else if 합 < 0 then
왼쪽 증가
else
오른쪽 감소
end if
end while
end for
결과 반환
Java
복사
문제: 주어진 정수 배열에서, 합이 0이 되는 서로 다른 세 수를 찾아 반환하라.
•
알고리즘의 각 단계를 구체적으로 제시하여 구현을 훨씬 쉽게 만든다.
•
ex) “새로운 책을 책장의 맨 오른쪽에, 서브 표지가 앞을 향하도록 놓아라” ⇒ 책의 위치, 방향, 어떻게 배치하는지 모두 지시한다.
알고리즘을 제대로 학습하려면?
NOTE
거의 모든 언어에 공통되는 연산만 사용하기 (사칙 연산, 비트 연산, 조건문, 반복문)
•
하드웨어와 기계어/어셈블리어 수준에서 지원하는 것들로 알고리즘을 설명하는 것이 좋다.
◦
면접관은 당신이 작성한 그 한줄짜리 코드를 작성할 수 있는지를 보고 싶은것이다.
•
컴퓨터가 실제로 돌아가는 방법에 대해서 알아야한다.
◦
하드웨어가 어떤 연산을 지원하는가?
◦
컴퓨터에 데이터가 어떻게 저장되는가?
◦
힙과 스택 메모리의 차이에 대해서 아는가?
CPU 동작 원리 (명령어 처리 과정)
NOTE
CPU의 산술논리 연산장치, 제어장치, 레지스트 세트가 어떻게 협업하여 명령어를 처리하는가?
int A=2, B=3, C;
C=A+B;
Java
복사
D2에 저장된 값과 D3에 저장된 값을 더해서 그 결과를 sum에 넣으라는 의미이다.
•
CPU는 0과 1의 2진수로 이루어진 기계어만 인식한다.
•
따라서 위 코드를 실행하려면 컴파일러(Compiler)를 이용하여 사람이 이해하기 쉬운 기호와 일대일로 대응시켜 어셈블리어로 변환된다.
LOAD mem(10), register 2;
LOAD mem(11), register 3;
ADD register 5, register 2, register 3;
MOVE register 5, mem(12)
Java
복사
어셈블리어로 변환한 덧셈 프로그램
•
10번지 메모리에 있는 값을 읽어온 후에 11번지에 있는 값과 더한 다음, 12번지에 저장해라
•
이후 최종적으로 어셈블러(Assemlber)를 통해서 기계어로 변환된다.
## 어셈블리어로 변환한 덧셈 프로그램 ##
01 LOAD mem(10), register 2;
02 LOAD mem(11), register 3;
03 ADD register 5, register 2, register 3;
04 MOVE register 5, mem(12)
Java
복사
16비트 → 6비트(명령어) + 10비트(데이터)
•
한 줄이 16개의 비트로 이루어진 16비트 언어로 프로세서가 한 번에 처리할 수 있는 값이 16비트가 된다고 생각하면 된다.
•
위의 기계어는 RAM에 100~105번지에 저장되는데, RAM은 8bit씩 저장되기 때문에 위에 그림과 같이 2줄로 저장된다.
◦
32비트는 4줄, 64비트는 8줄이 된다고 생각하면 된다.
실제 CPU 동작 처리 순서
NOTE
1. 인출
100주소를 읽는 과정 (메모리 → CPU)
•
프로그램 카운터(PC) 레지스터에 현재 실행중인 다음에 실행할 코드의 메모리의 주소가 저장된다.
•
이 주소는 메모리 주소 레지스터(MAR)으로 전달되고, MAR은 100번지에 있는 데이터를 가져와 메모리 버퍼 레지스터(MBR)에 저장한다.
•
이렇게 메모리의 데이터를 CPU로 가져오는 과정을 인출이라 한다.
2. 해석
LOAD[10] 처리
•
명령어 레지스터에 LOAD[10] 값이 저장되고, 프로그램 카운터에 2가 더해진다.
◦
다음에 수행할 메모리는 전보다 2칸아래에 있기 떄문
◦
32비트의 프로세서는 메모리 4칸을 한번에 처리할 수 있어 4가 더해진다.
•
LOAD[10] 명령어는 10번지 주소에 있는 데이터를 읽어오라는 명령어이기 때문에, 메모리 주소 레지스터에 10이 입력되고, 10번지의 데이터를 읽어와서 메모리 버퍼 레지스터에 저장한다.
•
10번지의 값은, 명령어가 아닌 데이터이기 때문에, 누산기 레지스터에 저장된다.
•
여기까지가 LOAD[10] 명령어 한 줄을 완료되었다고 보면 된다.
ADD[11] 처리
•
이제 다음 줄을 처리하기 위해 PC에 지정된 주소를 가져온다.
•
MAR에 다음주소가 저장되고, 주소에 있는 정보가 MBR에 저장된다.
•
ADD[11]은 11번지 주소 값을 더하라는 명령어이기 때문에, 명령 레지스터로 이동해서 저장된다.
•
명령어는 제어장치로 저장되어 해석된다.
3. 실행
•
ADD[11] 더하기 명령을 실행하기 위해서는 누산기 레지스터에 저장된 데이터는 산술 논리 장치(ALU)로 전달되고, 다음 메로리 주소 레지스터에 11번지의 주소가 입력되고, 11번지에 있는 데이터를 메모리 버퍼 레지스터에 저장한다.
•
이 값은 명령어가 아닌 데이터로 역시 누산기 레지스터에 입렫괴며, ALU에서 처리되고, 결과값은 다시 누산기 레지스터에 저장된다.
•
산술 논리장치에서 계산되는 과정을 실행 단계라고 한다.
4. 저장
STORE[12] 처리
•
마지막으로 저장하는 명령어가 해석되고, 12번지의 메모리에 계싼된 값을 저장한다.
•
누산기 레지스터에 저장된 값은 MBR를 토앻서 12번지 메모리에 저장되며 프로그램이 종료된다.
애플리케이션에서 메모리 영역
NOTE
컴퓨터 프로그램이 실행될 때, 프로세스가 사용하는 메모리 영역은 크게 4가지로 분류된다!
1. 코드 영역
•
애플리케이션의 실행 코드를 저장한다.
◦
ex) 스프링부트 - Java Byte 코드
◦
컨트롤러 ,서비스 ,레포지토리와 같은 클래스의 메소드, Java 표준 라이브러리 함수, 스프링 프레임워크 코드 등이 포함된다.
2. 데이터 영역
•
전역 변수나, 정적 변수들이 저장된다.
◦
ex) Java - static 키워드 변수, 객체
◦
ex) 스프링부트 - Singleton Scope의 Bean, 정적선언 값
3. 스택 영역
•
함수나 메소드의 호출 정보와 지역 변수들이 저장된다.
◦
ex) HTTP 요청이 들어온다 → 해당 요청을 처리하는 변수들이 stack에 push된다.
◦
메소드나 함수의 실행이 완료되면 해당 정보는 stack에서 pop되어 제거된다.
◦
컴파일 타임에 크기가 결정된다.
4. 힙 영역
•
동적으로 생성된 객체들이 저장된다.
◦
ex) 스프링부트 - new 키워드로 생성된 객체, Spring bean, JPA 엔티티 등
◦
Java의 경우 가비지 컬렉터로 더이상 참조되지 않는 객체를 자동으로 회수하므로, 개발자는 직접적인 메모리 해제 작업을 할 필요가 없다.
◦
런 타임에 크기가 결정된다.
실제로 애플리케이션이 실행될 때 CPU가 메모리를 어떻게 사용할까?
NOTE
Springboot에서 Controller가 실행되는 과정에서 CPU와 메모리 영역이 어떻게 상호작용하는지 설명한다!
1.
요청 도착
•
클라이언트로부터의 HTTP 요청이 웹 서버에 도착하면, 서버는 요청을 처리하기 위해 쓰레드를 생성하거나 쓰레드 풀에서 가져온다.
2.
스택 영역 활용
•
요청을 처리하기 위한 쓰레드가 생성되면, 그 쓰레드는 스택 영역을 사용하여 메소드 호출 정보, 지역 변수등을 관리한다.
•
서버는 요청 정보, 헤더, 바디 등을 파싱하여 해당 정보를 메소드의 매개변수나 지역 변수로 스택에 저장한다.
3.
Controller 맵핑 및 호출
•
스프링은 요청의 URL, HTTP 메소드 등을 기반으로 적절한 Controller 메소드를 찾는다.
•
해당 Controller 메소드의 바이트코드는 코드 영역에 찾아져 CPU로 전달되어 실행된다.
4.
객체 생성 및 힙 영역 호출
•
Controller 메소드 실행 중 필요한 객체 (DTO, Service 객체 호출결과) 는 new 키워드를 사용해 동적으로 생성한다.
•
이런 객체들은 힙 영역에 저장된다.
5.
데이터 영역 활용
•
Controller나 다른 클래스에 static 키워드로 선언된 변수나 Singleton Scope의 Bean에 접근해야 하는 경우 데이터 영역에서 해당 정보를 가져온다.
6.
비즈니스 로직 실행 및 DB 접근
•
Controller는 필요한 비즈니스 로직을 처리하기 위해 Service나 Repository 레이어의 메소드를 호출한다.
•
이 때도 스택 영역은 메소드 호출 정보를 관리하는데 사용된다.
7.
응답 생성
•
로직 처리 후, Controller는 응답을 생성한다.
•
이 때 생성된 응답 객체도 힙 영역에 저장된다.
8.
요청 처리 완료
•
응답이 클라이언트에게 전송된 후, 사용된 스택 영역의 메모리는 해제되며, 더이상 참조되지 않는 힙 영역의 객체들은 가비지 컬렉터에 회수될 수 있다.