CS겸 취준까지

탐색 알고리즘 특정 데이터를 많이 가지고 있을 때, 원하는 데이터를 찾는 방식 난이도별 종류 이외 많은 탐색 알고리즘이 존재 난이도 알고리즘 초급 선형 탐색, 이진 탐색, DFS, BFS 중급 이분 탐색 트리, 다익스트라 알고리즘, A* 알고리즘 고급 유전 알고리즘, 몬테 카를로 트리 탐색 기초 탐색 알고리즘 한눈에 보기 탐색 알고리즘 시간 복잡도 [최고 평균 최악] 장점 단점 선형탐색 O(1)/O(n)/O(n) • 구현이 간단 • 정렬되지 않은 데이터에서도 사용 가능 • 데이터의 순서에 영향을 받지 않고 동작 • 큰 데이터 세트에서 성능이 저하 • 다른 탐색 알고리즘에 비해 느린 속도 이진탐색 O(1)/O(log n)/O(log n) • 빠른 속도와 메모리 효율적인 알고리즘 • 정렬된 데이터에서 원하는..

[ 삽입정렬 ] 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣음 과정 손 안의 카드를 정렬하는 방법과 유사함 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입 새로운 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬됨 알고리즘의 구체적인 개념 2번째 자료부터 시작하여 (즉 첫번째 key 값은 두번째 자료부터 시작함) 앞의 원소들과 비교하여 삽입할 위치를 지정한후 원소를 뒤로 옮기고 지정한 자리에 원소를 삽입하여 정렬 2번째 자료는 1번째 자료, 3번째 자료는 1-2번째 자료 ... 와 비교한후 원소가 삽입될 위치를 찾음 삽입될 위치를 찾았다면 그 위치에 자료를 삽..

1. 연결 리스트 연결 리스트는 선형적인 데이터 구조라는 점에서 배열과 유사하다. 하지만 배열과 달리, 연결 리스트의 요소(elements)들은 특정 메모리 주소나 인덱스에 저장되지 않는다. 오히려 각 요소는 포인터 또는 다음 객체에 대한 링크를 가지고 독립적인 개체에 가깝다. 연결 리스트의 각 요소를 노드(node)라 부른다. 노드는 일반적으로 데이터 그리고 다음 노드를 가리키는 링크, 이 2가지 아이템으로 구성된다. 참고로 데이터의 유형은 다양하게 올 수 있다. 연결 리스트의 가장 첫 번째 지점을 헤드(head)라 부른다. 헤드는 연결 리스트의 첫번째 노드를 의미한다. 마지막 노드는 null을 가리킨다. 만약 연결 리스트가 비어있는 경우, 헤드는 null을 참조하게 된다. 자바스크립트로 연결 리스트를..

1. 복잡도(Complexity) 복잡도란 알고리즘의 성능을 나타내는 지표이다. 복잡도는 가독성(Readability)와 다른 의미로 쓰인다. 즉, 코드가 얼마나 복잡하고 알아보기 어려운지를 의미하는 것이 아니라, 불특정한 함수의 성능적인 측면에서의 복잡도를 의미한다. 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 이때, 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도 가 낮은 알고리즘이 좋은 알고리즘이다. 2. 시간 복잡도(Time Complexity) 시간 복잡도란 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간을 의미한다. ..

스택(Stack) 스택(Stack)은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In Firist Out) 구조이다. 스택은 한쪽 방향에서만 데이터의 삽입과 삭제가 가능하다. 스택 용어 top(peek) : 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터이다. 그림상 요소4에 해당 push : 데이터를 삽입하는 것을 말하며, 삽입된 데이터는 삭제시 가장 먼저 삭제 될 데이터 pop : 데이터를 삭제 할 때 사용하며, 가장 최근에 저장된 데이터가 삭제된다. 사용되는 예 브라우저의 뒤로가기 실행 취소(Ctrl + z) 재귀 함수 : 자기 자신을 호출하는 함수 함수를 호출할 때마다 해당 함수의 지역변수, 반환주소, 매개변수 등의 정보를 호출 스택이라는 메모리 영역에 저장..