✔️ 알고리즘을 왜 해야할까…?

유진호 멘토님의 커리어 코칭(원티드 6기 인턴십)을 마치며 정리하는 시간을 가져보려고 합니다.
멘토님의 글을 많이 참고한터라 문제가 된다면 삭제할 예정입니다.

🎯 취업목적

요즘 같은 개발자 취업난 시대에 기업들은 좋은 개발자를 뽑기 위해서 코딩테스트를 한다. 기업에서는 감당하기 벅찰 정도로 지원자들이 몰리는 상황이다.
지원자들의 포토폴리오는 각 각 다르기 때문에 자동화 된 코딩 테스트 만큼 짧은 시간에 많은 지원자를 효과적으로 걸러낼 수 있는 방법이 현실적으로 없다고 한다.
좋든 싫든, 코딩 테스트는 현재 업계에서 관행처럼 굳어진 채용 과정 중 일부이기 때문에 개발자로서 코딩테스트를 피하는것이 어려운것이 현실이다.

🎯 시대가 바뀌어서

클라우드, 빅데이터, 인공지능, 블록체인 등 IT는 점점 고도화되고 있다. PC와 HW 성능이 높아지면서 수학도 필요하고 알고리즘 해결능력도 필요해지게 된다.
일반 기업체에서 IT 근무를 하다보면 수학적 능력 혹은 알고리즘을 쓸 곳이 없지만, 기술을 요하는 기업으로 취업이직을 원하던 IT트랜드를 따라가기 위해서라도 알아야한다.
채용 담당자가 코딩 테스트를 통해서 얻고자 하는 것은 지원자의 문제 해결능력을 보고자 하는것이지, 순수하게 소스코드를 화려하게 잘 짜는것을 보는것과 거리가 멀다.

🎯 어떻게 공부해야 할까?

언어가 상관없다면 Python으로 하거나 사용하는 언어로 하면된다.
알고리즘을 짜는 방법 이론 등을 학습한다.
학습을 바탕으로 문제풀이를 여러번 돌린다.

⚡ 정리

알고리즘을 하는이유는 결국 모르는 것을 어떻게 접근해서 어떤 방법으로 풀것인가?를 고민하며 개발적인 사고를 확장시키는 것이다.

알고리즘 정의와 특징에 대해서 알아보자

✨ 알고리즘 정의

수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한것이라고 한다.

✨ 어떠한 문제가 뭐길래?

데이터 정렬, 최단 경로 찾기, 문자열 검색하기, 2개의 자연수 최대 공약수 구하기, 배열에서 특정 요소 제거하기등등…

알고리즘으로 설계해서 해결할 수 있는 문제들을 의미한다.

1️⃣ 알고리즘은 명확한 명령이어야 한다.

알고리즘은 일련의 명령으로 구성되며, 각 단계에서 명령은 구체적이고 모호하지 않아야 한다.

✨ 모호한 명령 vs 명확한 명령

모호한 명령 ❌

여러 해석이 가능하도록 만들어 문제의 해결 방식이나 구체적인 접근 방법에 대한 힌트를 제공하지 않기 때문에 구현자에게 많은 해석의 여지를 남긴다.

사과 그려줘(추상적인 명령)
어떤 색, 어떤 구도, 어떤 장소인지 그리는 사람(컴퓨터) 마다 해석을 다르게 할 수 있다.

모호한 의사 코드 ❌

문제: 주어진 정수 배열에서, 합이 0이 되는 서로 다른 세수를 찾아 반환하라.

함수 findElements(배열):
	배열 안의 숫자들을 조합하여
		합이 0이 되는 세 수를 찾아서
			그 세 수를 반환하라

명확한 명령 ⭕

명확하며 각 단계를 구체적으로 제시하여 구현하기 쉬워진다.

스타벅스주문.png

“과수원에 빨간 사과나무를 정면에서 보는구도로 그려줘”
사과의 색, 배치, 장소에 대한 구체적인 지시가 포함되어 있다.

명확한 의사 코드 ⭕

문제: 주어진 정수 배열에서, 합이 0이 되는 서로 다른 세 수를 찾아 반환하라.

함수 findElements(배열):
	결과 = 빈 리스트
	배열을 오름차순 정렬

	for i = 0, to 배열의 길이 - 3, do
		//중복 값 건너뛰기
		if i>0 and 배열[i] == 배열[i-1] then
			countinue

		 좌 = 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
		결과 반환

2️⃣ 알고리즘 입력과 출력

🎯 Input (입력)

알고리즘은 0개 이상의 입력을 받을 수 있다.(비어 있을수 있음)

🎯 Output (출력)

하나 이상의 출력을 반환한다. 이출력은 입력에 대한 해답이며, 원하는 결과를 나타낸다.

3️⃣ 알고리즘은 유한한 시간을 가진다.

알고리즘이란 항상 종료되어야 한다.
무한히 반복되는 것은 알고리즘이 아니다.
유한한 시간 안에 원하는 결과를 반환해야 한다.

⚡ 정리

알고리즘은 어떠한 문제를 해결하기 위해서 명확한 명령으로 원하는 결과를 받는 특징을 가지고 있다.

✔️ 알고리즘을 제데로 학습하는 방법

모든 언어에 공통되는 연산만 사용한다.
(하드웨어 기계어/어셈블리어 수준에서 지원하는 것들로 알고리즘을 설명하는 것이 좋다.)
컴퓨터의 작동원리를 이해한다.

✔️ 컴퓨터의 작동원리를 알자

✨ 하드웨어가 지원하는연산

🎯 산술연산

덧셈, 뺄셈, 곱셈, 나눗셈 등의 작업을 포함한다.
숫자들은 레지스터라는 작은 저장공간으로 부터 ALU로 전달되어 연산을 수행하고 결과를 레지스터로 전달된다.

🎯 논리연산

AND, OR, NOT, XOR 등의 논리 연산을 포함한다.
ALU에서 처리되며, 비트 단위의 입력 값을 받아서 논리 연산을 수행한 후 결과를 반환한다.

🎯 비교 연산

두 값의 크기를 비교하여 크고 같고 작은지 등의 관계를 판단한다.
ALU에서 처리되며, 연산 결과에 따라 플래그 레지스터에 특정 비트들이 설정되어, 결과를 프로그램이나 다른 하드웨어가 해석할 수 있다.

🎯 데이터 전송

메모리와 레지스터간, 레지 to 레지, CPU와 I/O 디바이스 간에 데이터를 이동시킨다.
데이터 버스를 통해 전송되며, 명령어의 종류와 연산 코드에 따라 데이터의 출발지와 목적지가 결정되며, 컨트롤 유닛은 이러한 전송을 조정한다.

🎯 점프 연산

프로그램 실행 흐름을 변경하기 위해 사용된다. (조건부 점프, 무조건 점프 등)
명령어의 일부로 지정된 주소로 프로그램 카운터(PC) 값을 변경하여 실행 흐름을 변경한다.

⚡ 알고리즘을 제데로 학습하지 못하는 이유

이미 존재하는 함수만 호출

언어 문법이 틀리는데 컴파일 오류로 유추를 못하는 경우

컴퓨터에 데이터가 어떻게 저장되는지 모를경우

힙과 스택 메모리 차이에 대해서 모를경우

✔️ 컴퓨터가 명령어들을 처리하는 과정

✨ CPU 동작 원리(명령어 처리 과정)

CPU의 산술논리 연산장치, 제어장치, 레지스터가 어떻게 협업하여 작업을 진행하는지 CPU 명령어 처리 과정을 살펴보자.(컴퓨터 내부는 비트로 0과 1로 이루어져있다.)

🎯 C언어 -> 어셈블리어 -> 기계어

CPU는 0과 1의 2진수로 이루어진 기계어(machine code)만 인식한다.
C언어는 컴파일러를 이용하여 사람이 이해하기 쉬운 기호와 일대일 대응시켜 어셈블리어로 변환된다.

// C
01 int A= 2, B= 3, C;
02 C = A + B;

// 어셈블리어(C -> 어셈블리어)로 변환된 덧셈 프로그램
01 LOAD mem(10), register 2;  //10번 메모리
02 LOAD mem(11), register 3;  // 11번 메모리
03 ADD register 5, register 2, register 3; // 2,3을 더해서 5레지에 저장
04 MOVE register 5, mem(12) // 12번 메모리를 레지 5에 저장

// 기계어(어셈블리어 -> 기계어)
01 100110 0000001010
02 110011 0000001011
03 111010 0000001100

🎯 기계어

우리가 사용하는 소프트웨어는 명령어와 데이터의 집합체
100110 0000001010 앞자리 개수가 6개인 6비트와, 뒤에 오는 값 데이터는 10비트로 한줄이 16개의 비트로 이루어진 비트 언어이다.
한줄은 프로레서가 한 번에 처리할 수 있는 값을 표현한다.

🎯 RAM

RAM은 8비트씩 저장되기 때문에 두 줄로 저장된다.

// 기계어는 10비트
100110 0000001010
// RAM은 8비트씩 저장되어 두줄로 바뀌며 각각의 주소에 저장된다.
100110 00
00001010

🎯 프로세서

위 처럼 두줄이 프로세서가 한번에 처리할 수 있다.
(32비트는 4줄, 64비트는 8줄)

✔️ CPU

✨ CPU 용어정리

🎯 PC(프로그램 카운터 - Program Counter)

다음에 인출할 명령어의 주소를 가지고 있는 레지스터
각 명령어 인출 이후, 자동적으로 일정크기 만큼 증가
분기 명령어가 실행되는 경우 목적지 주소로 갱신

🎯 AC(누산기 - Accumulator)

데이터를 일시적으로 저장하는 레지스터(tmp 변수를 담는 버퍼 역할)
레지스터 길이는 CPU가 한 번에 처리할 수 있는 데이터 비트수와 동일

🎯 MAR(기억장치 주소 레지스터 - Memory Address Register)

PC에 저장된 명령어 주소가 시스템 주소 버스로 출력되기 전에 일시적으로 저장되는 주소 레지스터

🎯 MBR(기억장치 버퍼 레지스터 - Memory Buffer Register)

기억장치에 쓰여질 데이터, 혹은 읽혀진 데이터를 일시적으로 저장하는 버퍼 레지스터

🎯 IR(명령어 레지스터 - Instruction Register)

가장 최근에 인출된 명령어 코드가 저장되어 있는 레지스터

✔️ 덧셈프로그램이 실제 CPU가 동작하는 과정을 살펴보자

✨ 인출 -> 해석 -> 실행 -> 저장

1️⃣ 인출

메모리의 데이터를 CPU로 가져오는 과정을 인출이라고 한다.
(PC 레지스터에 현재 실행중인 다음에 실행할 코드가 메모리의 주소에 저장된다. 이 주소는 메모리 주소 레지스터(MAR)로 전달되고 MAR는 주소에있는 데이터를 가져와 메모리 버퍼 레지스터(MBR)에 저장한다.

2️⃣ 해석

명령어 레지스터에 저장된 명령은 제어장치로 이동되어 해석된다.
(명령어 레지스터(IR)에 값이 저장되고, 프로그램 카운터에 2가 더해진다. 그 이유는 다음에 수행할 메모리는 전에 주소보다 두칸 아래에 있기 때문에 2가 더해지는것 100 => 102, 32비트 프로세서는 4칸을 한 번에 처리하기 떄문에 4가 더해진다.)
LOAD[10] 명령어는 10번지 주소에 있는 데이터를 읽어오라는 명령어이다.

메모리 주소 레지스터에 10이 입력
10번지의 데이터를 읽어옴
메모리 버퍼 레지스터에 일시적으로 저장됨

10번지에 저장된 값은 명령어가 아닌 데이터이기 때문에 누산기 레지스터(AC)에 저장된다.
다음줄을 처리하기 위해 PC에 저장된 주소를 가져온다.(ADD[11])
메모리 주소 레지스터에 다음 주소가 저장((ADD[11]))되고, 주소에 있는 정보가 메모리 버퍼에 저장된다.
ADD[11] 명령어는 11번지 주소 값을 더하라는 명령어이기 때문에 명령 레지스터로 이동해서 저장된다. (PC에 2가 더해지고 명령어는 제어장치로 저장되어 해석된다.)

3️⃣ 실행

ALU에서 계산되는 과정을 실행 단계라고 한다.
ADD[11] 더하기 명령을 실행하기 위해서는 누산기 레지스터(AC)에 저장된 데이터는 산술 논리장치(ALU)로 전달되고, 다음 메모리 주소 레지스터에 11번지의 주소가 입력되고 11번지에 있는 데이터를 메모리 버퍼 레지스터에 저장한다. 이 값은 명령어가 아닌 데이터로 AC에 입력된다.
그 값은 ALU에서 처리되고, 결과 값은 다시 AC에 저장된다.

4️⃣ 저장

마지막으로 저장하라는 명령어가 제어장치에서 해석되고, 12번지 메모리에 계산된 값을 저장하기 위해서 메모리 주소 레지스터에 12를 저장한다.
누산기 레지스터에 저장된 값은 메모리 버퍼 레지스터를 통해서 12번지 메모리에 저장되며 프로그램이 종료된다.

⚡이처럼 CPU는 데이터를 인출하고 해석하고 실행한 뒤 저장하는 과정을 거친다.

CPU내부동작.png

✔️ 알고리즘 이해에 도움되는 메모리 개념

✨ 애플리케이션에서 메모리 영역

컴퓨터 프로그램이 실행될 때, 프로세스가 사용하는 메모리 영역은 크게 4가지로 분류된다.

🎯 코드 영역

애플리케이션의 실행코드를 저장하는 영역.
(Spring boot의 경우, Java 바이트 코드가 이 영역에 위치한다.)
컨트롤러, 서비스, 레포지토리와 같은 클래스의 매서드들, Java 표준 라이브러리 함수들, 스프링 프레임워크의 코드 등이 포함된다.

🎯 데이터 영역

전역 변수나 정적 변수들이 저장된다.
(Java에서는 static 키워드를 사용하여 정의된 변수나 객체 등이 이 영역에 할당된다.)
스프링에서 싱글톤 스코프의 Bean이나 정적으로 선언된 설정 값들이 이 영역에 위치할 수 있다.

🎯 스택 영역

함수나 매서드의 호출 정보와 지역 변수들이 저장되는 영역이다.
HTTP 요청이 들어오면 해당 요청을 처리하는 컨트롤러 매서드가 호출될 때, 해당 매소드의 매개변수, 지역 변수, 리턴 주소 등이 스택에 push 된다.
매서드나 함수의 실행이 완료되면 해당 정보는 스택에서 pop 되어 제거된다.

🎯 힙 영역

동적으로 생성된 객체들이 저장되는 영역이다.
스프링 부트 애플리케이션에서 new키워드로 생성된 객체, Spring Bean, JPA 엔티티 객체 등 다양한 객체들이 이 영역에 할당된다.
Java는 GC를 통해 더 이상 참조되지 않는 객체를 자동으로 회수하므로, 개발자가 직접적인 메모리 해제를 하지 않는다.

✔️ Spring Boot App에서 CPU가 메모리를 사용하는 과정

1️⃣ 요청 도착

클라이언트로부터 HTTP 요청이 웹 서버(Tomcat)에 도착하면, 서버는 요청을 처리하기 위한 스레드를 생성하거나 스레드 풀에서 스레드를 가져온다.

2️⃣ 스택 영역 활용

요청 처리를 위한 스레드가 생성되면, 그 스레드는 스택 영역 을 사용하여 매서드 호출 정보, 지역 변수 등을 관리한다.
서버는 요청 정보, 헤더, 바디 등을 파싱하여 해당 정보를 매서드의 매개변수나 지역 변수로 스택 에 저장한다.

3️⃣ 컨트롤러 맵핑 및 호출

스프링은 요청 URL, HTTP 매서드 등을 기반으로 적절한 컨트롤러 매서드를 찾는다.
해당 컨트롤러 매서드 바이트 코드는 코드 영역 에서 찾아져 CPU로 전달되어 실행된다.

4️⃣ 객체 생성 및 힙 영역 활용

컨트롤러 매서드 실행 중 필요한 객체(DTO, Service 객체 호출 결과 등)는 new 키워드를 사용해 동적으로 생성될 수 있다.
이런 객체들은 힙 영역 에 저장된다.

5️⃣ 데이터 영역 활용

컨트롤러나 다른 클래스에서 static 키워드로 선언된 변수나 싱글톤 스코프의 Bean에 접근해야 하는 경우 데이터 영역 에서 해당 정보를 가져온다.

6️⃣ 비즈니스 로직 실행 및 DB 접근

컨트롤러는 필요한 비즈니스 로직을 처리하기 위해 Service나 Repository 레이어의 매서드를 호출할 수 있는데 이 때도 스택 영역 은 매서드 호출 정보를 관리하는 데 사용된다.

7️⃣ 응답 생성

로직 처리 후, 컨트롤러는 응답을 생성한다. 이 때 생성된 응답 객체도 힙 영역에 저장될 수 있다.

8️⃣ 요청 처리 완료

응답이 클라이언트에게 전송된 후, 사용된 스택 영역의 메모리는 해제되며, 더 이상 참조되지 않는 힙 영역 의 객체들은 GC 에 의해 회수될 수 있다.

🖇️ 참고자료

원티드 6기 유진호 멘토님 알고리즘 참고
좋은 개발자의 5가지 기준
코딩테스트를 하는 기업의 관점
대세가된 코딩테스트
알고리즘 공부보다 훨씬 중요한것 - 유튜브
알고리즘이 필요한 ‘진짜’ 이유에 대해서
CPU 내부 구조 - 유튜브
CPU 레지스터와 CPU동작방법

'CS > 알고리즘 & 자료구조' 카테고리의 다른 글

빅오 표기법 (big-O notation)이란? (2)	2023.10.10
[자료 구조] 자바 컬렉션(Collection)에 대해 알아보자 - Java (7)	2023.08.31
알고리즘을 처음 시작하며, 정렬된 배열을 병합해보자 (LeetCode - 88) (0)	2023.08.24

알고리즘 학습과 메모리 상관관계를 알아보자

✔️ 알고리즘을 왜 해야할까…?

🎯 취업목적

🎯 시대가 바뀌어서

🎯 어떻게 공부해야 할까?

⚡ 정리

알고리즘 정의와 특징에 대해서 알아보자

✨ 알고리즘 정의

✨ 어떠한 문제가 뭐길래?

1️⃣ 알고리즘은 명확한 명령이어야 한다.

✨ 모호한 명령 vs 명확한 명령

모호한 명령 ❌

모호한 의사 코드 ❌

명확한 명령 ⭕

명확한 의사 코드 ⭕

2️⃣ 알고리즘 입력과 출력

🎯 Input (입력)

🎯 Output (출력)

3️⃣ 알고리즘은 유한한 시간을 가진다.

⚡ 정리

✔️ 알고리즘을 제데로 학습하는 방법

✔️ 컴퓨터의 작동원리를 알자

✨ 하드웨어가 지원하는연산

🎯 산술연산

🎯 논리연산

🎯 비교 연산

🎯 데이터 전송

🎯 점프 연산

⚡ 알고리즘을 제데로 학습하지 못하는 이유

✔️ 컴퓨터가 명령어들을 처리하는 과정

✨ CPU 동작 원리(명령어 처리 과정)

🎯 C언어 -> 어셈블리어 -> 기계어

🎯 기계어

🎯 RAM

🎯 프로세서

✔️ CPU

✨ CPU 용어정리

🎯 PC(프로그램 카운터 - Program Counter)

🎯 AC(누산기 - Accumulator)

🎯 MAR(기억장치 주소 레지스터 - Memory Address Register)

🎯 MBR(기억장치 버퍼 레지스터 - Memory Buffer Register)

🎯 IR(명령어 레지스터 - Instruction Register)

✔️ 덧셈프로그램이 실제 CPU가 동작하는 과정을 살펴보자

✨ 인출 -> 해석 -> 실행 -> 저장

1️⃣ 인출

2️⃣ 해석

3️⃣ 실행

4️⃣ 저장

⚡이처럼 CPU는 데이터를 인출하고 해석하고 실행한 뒤 저장하는 과정을 거친다.

✔️ 알고리즘 이해에 도움되는 메모리 개념

✨ 애플리케이션에서 메모리 영역

🎯 코드 영역

🎯 데이터 영역

🎯 스택 영역

🎯 힙 영역

✔️ Spring Boot App에서 CPU가 메모리를 사용하는 과정

1️⃣ 요청 도착

2️⃣ 스택 영역 활용

3️⃣ 컨트롤러 맵핑 및 호출

4️⃣ 객체 생성 및 힙 영역 활용

5️⃣ 데이터 영역 활용

6️⃣ 비즈니스 로직 실행 및 DB 접근

7️⃣ 응답 생성

8️⃣ 요청 처리 완료

🖇️ 참고자료

'CS > 알고리즘 & 자료구조' 카테고리의 다른 글

관련글

티스토리툴바