[코딩테스트 ALL IN ONE]코딩테스트 🍯 TIP

# 자료구조

: 데이터를 저장하고 관리하는 방식

자료구조는 데이터를 체계적으로 저장하여 메모리를 효율적으로 사용할 수 있게 하고, 빠르고 안정적으로 데이터를 처리할 수 있도록 도와준다.

 

메모리구조를 잘 알고 있어야 자료구조의 중요성을 알게된다.

 

example)

num1 = 10
num2 = 16
num3 = 17
num4 = 5
num5 = 11
num6 = 14
num7 = 1
num8 = 4
num9 = 20
num10 = 20

지금은 10개지만, 데이터를 100개, 1000개를 저장해야하는 상황이 온다면 변수를 하나하나 지정해서 저장하는건 무리가 있다.

이런 경우, 비슷한 성질의 데이터를 모아서 저장을 하면 좋겠다.

 

이렇게 변수를 하나하나 지정해서 데이터를 저장하기보다는, Array 자료구조를 사용하면 데이터를 더 효율적으로 저장하고 관리할 수 있다.

num = [10, 16, 17, 5, 11, 14, 1, 4, 20]

 

array는 쉬운 자료구조이기때문에 '나도 그정도는 알지', 라고 생각할 수 있지만

tree, graph, heap, link list는 언제 사용할지 등, 하나하나 이론 공부를 할 때 '이럴 때 사용하면 좋구나' 라는걸 알 수 있다.

 

'자료구조를 잘 사용하면 데이터를 효율적으로 저장하고 관리할 수 있겠구나'를 이해할 수 있다.

 

우리가 앞으로 배울 자료구조들은

• Linear(선형 자료 구조) : array, dynamic array, linked list, queue, stack, hash table
• non-linear(비선형 자료구조) : tree, graph

이것들을 통틀어서 자료구조라고 한다.

 

 

# 자료구조를 배워야 하는 이유

자료구조를 학습하는 것이 알고리즘 코딩 테스트 문제푸는 것에 도움이 될까? → 자료구조와 알고리즘은 긴밀한 관계가 있다. 특정 알고리즘을 구현하기 위해서 꼭 사용해야하는 자료구조가 있을 수 있다. 또한 어떤 자료구조를 선택했는지에 따라서 사용할 수 있는 알고리즘이 달라진다.

ex: BFC 알고리즘을 쓰고 싶다 → Queue 자료구조가 필요하다

ex: Dijkstra 알고리즘을 쓰고 싶다 → Heap 자료구조가 쓰인다.

 

코딩테스트가 주어졌을 때, 복잡한 알고리즘 필요없이 내가 어떤 자료구조를 선택했는냐에 따라서 문제풀이 방법, 결과값, 시간복잡도, 실행시간 등이 전혀 달라지게 된다.

한 문제를 다양한 방식으로도 풀어봐야하고, 다른 사람은 어떤식으로 푸는 지도 볼 수 있어야 한다.

 

 

# 알고리즘 algorithm

: 문제 해결 방법 ; 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법

• 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화
  • BFS, DFS, Binary Search, Dijkstra 등

• 한 문제를 해결할 수 있는 알고리즘은 다양하다
  • 각 문제에 적합한 알고리즘을 선택할 수 있어야 한다.
  • 알고리즘을 평가할 수 있어야 한다.

 

문제를 많이 해결하다보니, 자주 쓰이는 문제해결방법이 있더라.

그런 것들을 패턴화해서 사람들에게 이름을 붙인것 뿐.

한 문제를 해결할 수 있는 알고리즘은 사람마다 너무 다양하고 문제마다 다양하다.

적합한 알고리즘인지 알려면 알고리즘을 '평가'할 수 있어야 한다.

이게 더 좋은지, 더 안좋은지. 물론 상황에 따라서 같은 알고리즘이라 하더라도 달라질 수 있다.

 

# 알고리즘의 평가기준

• 시간 복잡도(Time Complexity) : 굉장히 중요하다. 우리나라 기업에서 코딩테스트를 볼 때 가장 많이 물어보는 것.
• 공간 복잡도(Space Complexity) : 우리나라에서는 거의 안물어본다.
• 구현 복잡도 : 코드로 구현을 해야하는데, 구현이 너무 복잡하면 당연히 안좋다. 코딩을 작성하는 시간을 줄이는데 중요하다.

 

시간복잡도와 공간복잡도는 보통 trade-off 관계.

실행시간(시간복잡도)을 줄이기 위해서는 메모리(공간복잡도)를 더 사용해야하고, 메모리 사용량을 줄이다보면 실행시간이 늘어나게 된다.(공간복잡도↑ → 시간복잡도 ↓, 공간복잡도↓ → 시간복잡도 ↑)

 

코딩테스트에서는 보통 실행시간을 줄이는게 중요. (시간복잡도를 낮추는게 중요)

또한, 시간복잡도를 미리 계산하여 문제 조건을 딱 맞추면서도 구현하기 쉬운 알고리즘을 선택하는 방법!

 

우리는 공간복잡도를 신경쓸 필요가 거의 없다. 시간 복잡도만 고려하면 된다.

 

**출처 : 코딩테스트[ALL IN ONE] 강의 : 코딩테스트 TIP

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC/dashboard