🤔 생각해보기
1. 일반적인 배열 자료구조에 대해서 설명할 수 있나요?
2. 자바스크립트의 배열에 대해서 설명할 수 있나요?
3. 연결리스트 자료구조에 대해서 설명할 수 있나요?
- 싱글 연결리스트를 구현해보세요.
- 더블 연결리스트를 구현해보세요.
- 환형(원형) 연결리스트를 구현해보세요.
4. 스택 자료구조에 대해서 설명할 수 있나요?
[1] 자료구조와 알고리즘
[1-1] 자료구조
빠르고(시간) 메모리(공간)를 효율적으로 사용하여 안정적으로 데이터를 처리하는 것이 궁극적인 목표, 상황에 따라 사용될 수 있는 다양한 자료구조들이 있음. 대표적으로 선형과 비선형으로 나뉜다.
1. 선형 : 큐, 스택, 연결리스트 등
2. 비선형: 그래프, 트리, 트라이 등
현실(real-time)의 문제, 혹은 프로세스를 소프트웨어 관점으로 옮기는 것 (전산화)
ex) 대기행렬이론(queuing theory)
[1-2] 알고리즘
어떤 문제를 효율적으로 해결하기 위한 방법.
1. 존재하는 알고리즘은 매우 많다. 산업공학과를 나왔기 때문에, 산업공학적 관점으로 바라보자면 구체적으로 정의된 알고리즘이 아니더라도 어떤 목적을 위한 행위 자체가 알고리즘이라고 할 수 있을 것 같다.
- 출근 알고리즘 : 아침 몇 시에 씻고(씻을 수도 있고 안 씻을 수도 있고, 샤워를 할 수도 있고 없고) 어떤 옷을 입고(옷을 안입을 수도?) 회사까지 어떻게 갈 것이고(재택근무 일 수도 있고?).... > 알고리즘은 그저 어떤 문제를 해결하는 과정
2. 절대적으로 좋은 자료구조와 알고리즘은 없다. 어떤 상황에서, 어떤 목적을 위해 적절한 자료구조, 알고리즘을 채택하는 것.
3. 하지만 상대적으로 좋은 알고리즘은 있을 수 있음. 같은 문제를 해결하더라도 시간과 공간을 얼마나 적게, 덜 쓰는가?
4. 때로는 공간(메모리)를 시간과 바꿔서 높은 성능을 낼 수 있음. (다이나믹 프로그래밍, ex.피보나치수열)
5. 결국 자료구조, 알고리즘도 도구. 문제를 해결하기 위해 그때 그때 상황에 맞는 것을 채택하는 것. (BFS 문제를 DFS로 접근했다면 잘못된 채택)
[2] 시간복잡도
알고리즘의 효율을 판단하는 척도에는 시간복잡도, 공간복잡도가 있다. 기술의 발전으로 하드웨어, 소프트웨어의 메모리 용량이 늘어나면서 공간복잡도 보다는 시간복잡도를 좀 더 중요하게 생각하는 경향이 있음.
시간복잡도를 표기하는 방법은 점근적 표기법 으로 한다.
[2-1] 점근적 표기법
점근적 표기에서 상수항은 무시한다. (처리해야할 데이터의 수를 무한으로 가정하기 때문에)
점근적 표기법에는 3가지 종류가 있다. 컴퓨터과학에서는 일반적으로 빅-오 표기법을 채택한다.
1. Big-Θ (빅 세타) 표기법 (점근적으로 근접한 한계값)
Big-θ (빅 세타) 표기법 (개념 이해하기) | 알고리즘 | Khan Academy
ko.khanacademy.org
2. Big-O (빅 오) 표기법 (점근적 상한)
Big-O (빅 오) 표기법 (개념 이해하기) | 알고리즘 | Khan Academy
ko.khanacademy.org
3. Big-Ω (빅 오메가) 표기법 (점근적 하한)
Big-Ω (빅 오메가) 표기법 (개념 이해하기) | 알고리즘 | Khan Academy
ko.khanacademy.org
[2-2] 소프트웨어에서 시간복잡도
프로그램의 성능을 정확히 알 수 있는 방법이 있을까? → NO. 프로그램의 성능은 유저의 컴퓨터의 성능, 컴파일러 혹은 인터프리터의 성능, 어떤 프로그래밍 언어(시간으로만 비교할 때 같은 코드일지라도 C로 작성된 코드는 파이썬보다 매우 빠르다)로 작성되어있는가에 영향을 받을 수 있음.
참고) 자바스크립트에서 성능을 측정하기 위해 Date 객체를 이용할 수 있겠음.
[3] 배열
1. 원소에 접근 : O(1)
2. 원소 삭제 : O(N), 인덱스를 다시 조정해주는 작업이 이루어진다.
3. 맨 끝에 원소 추가 or 삭제 : O(1)
자바스크립트의 shift, unshift의 성능
shift, unshift는 배열 맨 앞에 요소를 추가하거나 삭제하는 Array.prototype 메서드이다. 일반적인 배열 자료구조는 이 두 메서드의 시간복잡도는 O(N)이라고 생각할 수 있다. 하지만 자바스크립트의 배열은 실제로 배열이 아닌 Object이고, 자바스크립트는 지속적인 성능 최적화로 이 메서드들의 성능은 O(N)보다 빠르다. 코딩테스트에서 데이터의 수가 적다면 shift, unshift를 사용해도 괜찮을 수준이지만 데이터의 수가 많다면 좋지 않은 성능을 보여줄 것이다.
[4] 연결리스트
1) 싱글 연결리스트 : 단방향, 포인터를 1개 가지고 있고 다음 객체를 가리킨다.
2) 더블 연결리스트 : 양방향, 포인터를 2개 가지고 있고 각각 이전, 다음 객체를 가리킨다.
3) 원형 연결리스트 : tail(마지막 노드)는 head(첫번째 노드)를 가리킨다.
[5] 스택
LIFO 정책을 따르는 자료구조 (큐는 FIFO)
💡 오늘의 회고
❓ 왜 기업은 알고리즘 코딩 테스트를 볼까?
(개인적인 생각입니다)
1. 지원자가 너무 많다. 모든 인원의 서류를 검토하고 면접을 하는 것은 비용이 너무 많이 든다. 때문에 어느 정도 '걸러내는' 작업이 필요하다.
2. 알고리즘 코딩 테스트는 기초 코딩 능력을 검증할 수 있는 아주 간편한 수단이다. 따라서 '어느 정도의 수준'을 커트라인으로 정해서 코딩 실력을 판가름 하기에 안성맞춤인 듯 하다.
3. 비용적인 문제와 별개로, 자료구조와 알고리즘을 모르는 개발자보다 알고 있는 개발자의 실력이 더 낫다.
4. 주니어 개발자에게 있어서 자료구조, 알고리즘을 공부해서 코딩 테스트를 잘 보는 것은 성실함의 척도가 될 수 있다. (재능의 영역이 아니라고 생각한다.)
5. 알고리즘, 자료구조를 공부하지 않는 것과 별개로, 필요성 자체를 느끼지 못하는 개발자는 실력없는 개발자일 확률이 클 것이다.
조엘 테스트에 의하면 코딩 테스트를 실시하지 않는 기업은 안 좋은 기업이라고 한다. 아마 현재 많은 기업들은 알고리즘 코딩 테스트가 아니더라도 개발 실력을 판단할 수 있는 테스트 과제를 많이 내고 있는 걸로 알고 있다. 조엘이 말하는 코딩 테스트가 반드시 알고리즘 테스트 인지는 모르겠으나, 어쨌든 코딩 테스트는 중요하고, 난 개인적으로 높은 수준의 알고리즘 문제를 풀 수 있을 정도는 아니더라도 "개발자라면" 어느정도 자료구조와 알고리즘은 알고 있어야 한다고 생각한다. 그리고 알고리즘 문제... 잘 풀고 싶다...
🔗 참고
생각해볼만한 재미있는 문제들
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=tirupopo&logNo=60040320744
[알고리즘]빨간눈 승려 패러독스
어느 외진 섬이 있는데 거기는 오직 승려들만이 살고 있다.승려들중에는 빨간눈을 가진승려가 있고 갈색눈...
blog.naver.com
https://m.blog.naver.com/2gumin14/220946148714
거짓말쟁이 패러독스
안녕하세요. 이번에는 간단하면서도 매우 특이한 패러독스를 알아보려고 합니다. 한 사람이 이렇게 말했습...
blog.naver.com
'프로그래머스 데브코스' 카테고리의 다른 글
| [데브코스 5일차] 트리, 이진 트리, 힙, 이진 탐색 트리, 트라이 (2) | 2022.03.26 |
|---|---|
| [데브코스 4일차] 큐, 해시테이블, 그래프 (4) | 2022.03.24 |
| [데브코스 2일차] CS (0) | 2022.03.23 |
| [데브코스 1일차] JS 배열과 객체 (0) | 2022.03.22 |
| 프로그래머스 데브코스 2기 합격기념 기술블로그 오픈 (짤막한 후기 있음) (0) | 2022.03.21 |
