title: "Nossi.DEV" # 카카오톡 등 공유 시에 활용되는 제목 텍스트 입니다.
description: "개발자 취업의 모든 것" # 카카오톡 등 공유 시에 활용되는 설명 텍스트 입니다.
scrollProgressBar: # 페이지 가로 스크롤바를 표시합니다
	show: true
  color: "#000000"
fonts: # 페이지의 폰트를 설정합니다
	headerFont: "Rubik"
  defaultFont: "Rubik"
imageBorderRadius: 20 # 이미지를 둥글게 만듭니다
calloutBorderRadius: 12 # 콜아웃을 둥글게 만듭니다
pageMaxWidth: 1000 # 페이지 최대 너비를 설정합니다 (노션 기본값 900)

1. 알고리즘 algorithm

<aside> 📍 알고리즘이란

어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법; 문제를 해결하는 방법
한 문제를 해결하는 방법은 한 가지만 있는게 아니라 무수히 많을 수 있다.
자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화; BFS, DFS, DP, 다익스트라 등등
각 상황에 적합한 알고리즘을 선택할 수 있어야 한다. </aside>

알고리즘은 수학과 컴퓨터과학 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법입니다. 알고리즘은 “**문제를 해결하는 방법”**이기 때문에 언어는 상관없습니다. 같은 원리에 따라 동작한다면 다른 언어로 작성되었더라도 같은 알고리즘을 사용했다고 볼 수 있습니다.

개발자는 현실의 문제를 해결하기 위해 코드를 작성하여 프로그램을 개발합니다. 한 문제를 해결하는 방법은 한 가지만 있는게 아니라 무수히 많을 수 있습니다. 그 중에서 자주 쓰이는 문제 해결 방법에는 BFS, DFS, DP, 다익스트라 등과 같이 이름을 붙여서 문제 해결 방법을 패턴화 하였습니다. 이렇게 패턴화된 문제 해결 방법을 보통 알고리즘이라고 부릅니다. 알고리즘을 학습하여 응용, 적용할 수 있게 된다면 비슷한 문제를 보다 쉽게 해결할 수 있습니다.

같은 문제상황에서도 개발자마다 해결 방법으로 내놓은 알고리즘이 다를 수 있습니다. 문제만 해결하면 되므로 아무 알고리즘으로 코드를 작성하면 될까요? 그렇지 않습니다. 문제를 해결할 수 있는 알고리즘이 여러 가지가 있더라도, 상황에 맞는 알고리즘을 잘 선택해야 합니다. 잘 선택할 수 있으려면 알고리즘을 평가할 수 있어야 합니다. 평가 기준에 대해서 간략히 살펴보도록 하겠습니다.

2. 알고리즘 평가기준

<aside> 📍 좋은 알고리즘이란

시간 복잡도
공간 복잡도
구현 복잡도 </aside>

시간 복잡도

적은 시간을 잡아먹는 알고리즘일수록 당연히 좋겠죠. 동일한 코드로 작성되어도 실행 환경에 따라서 매번 실행시간이 달라질 수 있습니다. 하지만 걸리는 시간의 경향성은 계산할 수 있습니다. 앞으로 배워볼 시간복잡도(Big-O)를 통해서 알고리즘마다 실행시간 경향성을 살펴보도록 하겠습니다.
공간 복잡도 (메모리)

메모리는 한정적이기 때문에 최대한 적은 용량의 메모리를 사용하는 것이 좋습니다. 하지만 컴퓨터의 메모리 용량이 커짐에 따라서 메모리를 크게 신경쓰지 않고 알고리즘을 작성하는 경우도 있습니다. 공간복잡도를 통해 특정 알고리즘이 얼마만큼의 메모리를 차지하게 될 지를 나타냅니다.
구현 복잡도

꽤 괜찮은 알고리즘을 떠올렸더라도 구현이 너무 복잡하고 알아보기 힘들다면 다시 생각해볼 필요가 있습니다. 개발자는 대부분의 경우 협업을 해야하고, 구현이 너무 복잡해지면 다른사람은 물론 미래의 나도 알아볼 수 없게 됩니다.

시간과 공간은 보통 trade-off 관계입니다. 꼭 그렇진 않지만, 실행시간을 줄이려면 메모리를 더 사용해야 하고, 메모리 사용량을 줄이려면 실행시간이 늘어나게 됩니다. 또한 실행시간이 적게 걸리고 메모리를 적게 차지하는 알고리즘이 무조건 좋은 것은 아닙니다. 결국 개발자가 알고리즘을 코드로 구현해야하는데, 너무 복잡한 알고리즘이라면 개발시간이 너무 늘어날 수 있습니다. 시간과 공간을 좀 더 차지하더라도 간단한 코드를 작성하는 편이 더 좋을 수 있습니다. 따라서 시간복잡도와 공간복잡도를 미리 계산하여 요구상황에 맞으면서도 간단한 알고리즘을 적절히 사용하는 것이 중요합니다.

한국 기업들의 알고리즘 코딩테스트에서는 공간보다는 시간을 더 중요하게 생각합니다. 메모리를 사용하더라도 실행시간을 줄이는 방법들을 강의에서 최대한 소개드리고자 합니다. 또한, 시간복잡도를 미리 계산하여 문제 조건을 딱 맞추면서도 가장 간단한 알고리즘으로 문제를 해결할 수 있도록 훈련을 해볼 것입니다.

3. 시간복잡도 Time Complexity

Runtime (실행 시간)

시간복잡도에 대해서 공부하기 전에, 실행시간(runtime)에 대해 알고 있어야 합니다. 우리는 코드를 한 줄 한 줄 작성하여 프로그램을 완성하죠. 그렇게 완성된 프로그램을 실행시키면 컴퓨터(CPU)는 한 줄 한 줄 코드를 처리하게 됩니다. 모든 코드를 처리하면 우리가 원하던 값을 얻을 수 있게 되고 프로그램은 끝나게 됩니다. 이렇게 프로그램이 시작되고 모든 코드를 실행하는데 걸리는 시간을 runtime(실행시간)이라고 합니다.

실행시간에 영향을 주는 요소는 크게 두 가지로 볼 수 있습니다.