[AI 부트캠프] DAY 40 - 코딩 테스트 1

[오늘의 일지]

코딩 테스트 - 시간 복잡도, 리스트, 큐&스택 공부하기

[상세 내용]

코딩 테스트 사전 지식

- 우선 코딩 테스트라는 것이 단어적으로 봤을 때는 일반적으로 프로그래밍 언어 코딩 공부한 것을 연습하기 위해서 하는 것이 맞기는 하나 실제로 이루어지는 테스트는 조금 다르게 느껴졌습니다. 그냥 무작정 코드를 짜서 원하는 결과를 얻는 것에서 끝나는 것이 아니라 좀 더 시간복잡도 측면에서 실용적이고 남들이 보기에도 이해하기 쉽게 코드를 짜는 것이 중요한 결과를 찾는 것이라고 생각합니다. 그럼 여기서 말하는 시간 복잡도에 대해서 설명하겠습니다. 

 

시간복잡도

- 시간 복잡도는 컴퓨터 분야에서 알고리즘의 수행 시간이 입력 크기에 대한 함수로서 표현된 것입니다. 다시 말해, 알고리즘의 수행 시간이 입력 크기에 어떻게 의존하는지를 설명하는 것입니다. 시간 복잡도는 일반적으로 Big O 표기법으로 표현되며, 입력 크기에 대한 알고리즘의 성능 상한을 제공합니다. 즉 시간 복잡도 분석은 알고리즘의 효율성을 평가하고 비교하는 데 매우 중요한 도구이며, 다양한 문제에 대한 최적의 알고리즘을 선택하는 데 도움을 줍니다. 그럼 다시 여기서 말하는 Big O 표기법에 대해서 궁금증이 생길 것입니다. 

 

Big O 표기법

- Big O 표기법은 접근 표기법의 한 종류입니다. 점근 표기법은 컴퓨터 과학 및 알고리즘 분야에서 알고리즘의 성능과 효율성을 분석하고 설명하는 데 사용되는 수학적인 표기법입니다. 즉 Big O 표기법은 알고리즘의 최악의 경우일 때의 실행 시간을 나타냅니다. 입력 크기 n에 대한 함수로 표현되며, 가장 큰 영향을 미치는 항만을 고려합니다. 예를 들면 n의 제곱과 그냥 n이 존재한다면 n의 제곱이 시간적으로 표현될 때 더 영향을 미치기 때문에 n의 제곱의 항만을 고려한다는 것입니다. 이것은 그래프와 영향 순위 표를 보면 더 이해가 잘됩니다. 그리고 중요한 것은 코딩 테스트에서는 시간 복잡도가 

 

출처:https://pub.towardsai.net/big-o-notation-what-is-it-69cfd9d5f6b8

 

출처:https://www.ml-science.com/big-o-notation

 

리스트

- 리스트는 순서를 가지고 원소들을 저장하는 자료구조입니다. 구현방법으로는 Array List로 구현할 수 있고, Linked List로 구현할 수 있습니다. python에서 사용하는 list 자료구조는 Array List로 구현되었습니다.

 

- Array List : ArrayList는 Java와 같은 몇몇 프로그래밍 언어에서 사용되는 동적 배열(dynamic array) 자료 구조입니다. ArrayList는 배열과 유사하게 연속된 메모리 위치에 요소들을 저장하지만, 크기를 동적으로 조정할 수 있습니다. 즉, ArrayList는 배열의 크기를 변경하면서 요소를 추가하거나 삭제할 수 있어 더 편리하게 사용할 수 있습니다.

 

- Linked List : Linked List는 데이터 요소(Node)와 각 요소가 다음 요소를 가리키는 링크(참조)로 이루어진 선형 자료 구조입니다. 링크드 리스트는 각 요소(Node)가 데이터와 다음 요소를 가리키는 링크(참조)로 구성되어 있어 데이터의 삽입과 삭제가 배열과 달리 상대적으로 효율적으로 이루어질 수 있습니다.

 

출처:https://medium.com/@yk392/what-is-a-linked-list-linked-list-vs-array-92f0db4015cc

큐 & 스택 (Queue & Stack)

- 큐(Queue) : 큐(Queue)는 데이터를 저장하는 자료 구조로, 데이터가 먼저 들어온 것이 먼저 나가는 선입선출(First-In-First-Out, FIFO) 원칙을 따릅니다. 큐는 일상생활에서 줄을 서서 기다리는 상황과 유사하게 동작하는 자료 구조입니다.

 

- 스택(Stack) : 스택(Stack)은 데이터를 저장하는 자료 구조로, 데이터가 나중에 들어온 것이 먼저 나가는 후입선출(Last-In-First-Out, LIFO) 원칙을 따릅니다. 스택은 데이터를 저장하고 검색, 삽입, 삭제 등의 연산을 수행하는 데 사용됩니다.

 

출처:https://gohighbrow.com/stacks-and-queues/

 

연습문제

- 리스트

Two Sum - LeetCode

 

- 큐 & 스택

Daily Temperatures - LeetCode

 

[마무리]

 지난주 EDA 프로젝트가 마무리되고 새롭게 한 주가 시작되었습니다. EDA가 끝난 만큼 새로운 코딩테스트라는 수업을 시작하게 되었습니다. 코딩테스트라는 것이 사실 예전에 sql을 공부할 때 sql과 관련된 코딩테스트를 해커랭크에서 몇 번 해본 적은 있는데 파이썬 관련 테스트는 이번이 처음이라 매우 생소하게 느껴지고 있습니다. 또 요즘 컴퓨터공학 쪽에서 중요하게 생각하는 자료구조나 알고리즘과 관련된 문제들을 풀려고 하니 난이도도 꽤 높은 거처럼 느껴졌습니다. 코딩테스트는 기업에서 개발자들의 기본 소양을 평가하기 위한 지표로 직접적인 연결이 되어 있는 만큼 꾸준히 문제를 많이 풀어보면서 실력을 쌓아 나갈 수 있도록 노력해야 될 거 같습니다.