TIL 2023.03.29

알고리즘 세션

 

자료구조/알고리즘

기본적인 자료구조와 알고리즘 어떻게 되는 지만 알고 가도 성공

정말 많은 시간투자 필요

개발자로서 취업하려면 포트폴리오 만큼이나 더 큰 비중을 가지고 준비

이틀동안 어떤 걸 배울지

왜 배우는 지

파이썬 기반으로 코드를 작성할 때 어떤 자료구조아 ㅁㄴㅇㄹ

데이터스트럭터/알고리즘

 

연결리스트(링크드리스트)

꼬리에 꼬리를 무는 형태로 관리해야 효율적으로 관리 가능

스택(후입선출)

트리

 

 

알고리즘:효율적으로 연산하는 방법

자료구조와 알고리즘은 상호보완적인 관계

 

내가 원하는 목적을 구하기 위해 어떤 순서로 연설을 하느냐

즉석퀴즈? 1280원 짜리 빵 500원 100원 50원 10원 동전 최소한의 동전을 사용하여 이 빵을 살 수 있는 방법 몇 개? 한개지 뭐

 

문법에 맞고 실행만 되면 되는 코드는 잘 짠 코드일까요? NO

유지보수 최적화 효율 성능 -> 성능, 용량, 비용 고려한 코드!

 

• 시간복잡도 & 공간복잡도
• 기본 코드 작성 능력
• 배열과 연결리스트
• 스택과 큐
• 정렬

 

코딩 테스트 공부 순서

1. 프로그래밍 언어 기초 학습
2. 자료구조/알고리즘 핵심 개념 - 반드시 코드로 표현할 수 있어야 함
3. 자료구조/알고리즘 기초 문제풀이
4. 자료구조/알고리즘 문제풀이 (양치기)

 

백준이 유명한 코딩테스트 플랫폼 백준 기준으로 골플 정도면 오케이

 

코테 문제풀이 기본

1. 눈이 마주치는 순간 풀어야하는 문제 = 쉬운문제
2. 생각을 쪼개서 자/알 개념을 녹여내야하는 문제

 

어떤 문제든지 반드시 고려해야하는 두가지 사항

1. 시간복잡도(성능)
2. 공간복잡도(용량)

 

성능과 용량에 대한 이야기

 

시간복잡도

“어떤 10만개 중에서 어떤 값을 찾아라!”

최선일 경우(best case): 빅-오메가 표기법

보통일 경우(average case): 빅-세타 표기법

최악의 경우(worst case): 빅-오 표기법

 

그냥 알고리즘의 성능은 최악의 상황을 표현하는 빅-오 표기법이 많이 쓰인다.

 

빅오표기법 알파벳O

• O(1)
• O(log n)
• O(n)
• O(n log n)
• O(n^2)
• O(2^n)

 

시간제한 메모리제한 제한사항 시간복잡도를 신경쓰지 않는다면 시간 초과

염두는 하고 있어야 해

 

대략 연산 1억번에 1초

• for문 1 개: O(n)
• for문 2 개: O(n^2)
• for문 3 개: O(n^3)

 

공간복잡도

최선 평균 최악 

빅-오

 

중요도: 시간복잡도>>>공간복잡도

 

 

배열과 연결 리스트

배열은 O(1)상수의 시간복잡도를 가짐

 

꼬리의 꼬리를 물고 자료를 저장할 수 있는 자료구조 연결리스트

유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조

노드: 맨위의 예제에서 각 화물칸 맨 앞의 노드를 head 맨 뒤의 노드를 tail

포인터: 현재 노드가 가리키는 다음 화물 칸

 

배열이 빠르게 값을 갖고 오는 것이 장점이라면 연결리스트는 원소의 삽입/삭제에 강점이 있는 자료구조 대신 검색은 느려

 

요약하자면 좋은 회사 들어가려면 코딩테스트를 봐야하고

코딩테스트를 준비하려면 오랜기간 꾸준히 연습해야한다.

코딩테스트 유형은 계속 나왔던 거 나오는데 난이도가 계속 올라간다.

코딩테스트 정말 중요하니까 자료구조/알고리즘 잘 알아둬라.