High-Quality-Coffee

다익스트라(dijkstra) 알고리즘은 최단경로를 구하는 알고리즘이다. 최단경로를 구하는 알고리즘 중에서는 벨만-포드, 플로이드 워셜, bfs, 다익스트라 등이 있는데, 이 알고리즘들은 최단 경로를 구하는 알고리즘 문제에 사용되긴 하지만 각각 구현 측면에서 차이가 있기 때문에 상황마다 사용되는 알고리즘이 다르다. 다익스트라(dijkstra) 알고리즘 한 정점에서 모든정점 까지의 최단경로를 각각 구하는 알고리즘이다. 문제를 해결할 수 있는 방법은 다양하지만, 시간복잡도와 공간복잡도를 고려하여 우선순위 큐를 사용하는 것이 보편적이다. 최단 경로 알고리즘 풀이 전략 최단경로 알고리즘을 사용해야 하는 문제를 마주했을 때,어떤 알고리즘을 써야할까라는 고민이 든적이 있을 것이다. bfs, 플로이드 워셜, ..

오늘은 탐색에 대해서 정리해보려고 한다 탐색문제는 항상 코테에서 자주 출제되는 문제이고, 모든 문제의 기본이 되는 알고리즘이니 잘 익혀두어야 한다.  탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘이다. 여기서 주어진 데이터는, 정렬 혹은 비정렬된 데이터로 볼 수 있고,이에 따라 적합한 탐색 알고리즘을 선택하면 된다.  깊이 우선 탐색 깊이 우선 탐색은 그래프의시작 노드 -> 탐색할 한쪽 분기 를 정하여최대 깊이까지 탐색 후,다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 이다.  말로는 이해하기 어려워서그림으로 설명하고자 한다.  그래프는 인접리스트로 표현하고,한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 visited[] 리스트를 사용할 것이다.스택 삽입은 ap..

정렬에 대해서 알아보자!버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 기수정렬레츠고  정렬 (sort)은, 데이터를 정해진 기준에 따라 배치하여의미 있는 구조로 재설정하는 것을 말한다. 먼저 각 정렬 알고리즘을 살펴보는 것이 좋을 거 같다! 정렬 알고리즘방식버블(bubble sort)데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식선택(selection sort)대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식삽입(insertion sort)대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식퀵(quick sort)pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식병합(merge sort)이미 정렬된 부분 집합..

스택, 큐, 우선순위 큐3가지의 자료구조는 전공자라면 알고있는 개념이다. 알고리즘을 본격적으로 학습하기 위해서 필수적으로 알고있어야 하는 자료구조인데,코테에서도 필수적으로 익혀두고 있어야 하는 자료구조이다. 크게 어렵지 않은 개념이기 때문에 빠르게 습득할 수 있을 것이다!   0. 앞서서, 나는 파이썬으로 코테를 준비하고 있으니, 파이썬을 기준으로 해서 자료구조를 설명하겠다!! 스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조이다.두 개는 비슷한 구조를 갖고 있지만, 처리 방식은 다르다는 것을 알고가자 1. 스택 스택은 "삽입"과 "삭제" 연산이 후입선출(LIFO:Last In First Out)로 이뤄지는 자료구조이다.후입선출 - 말 그대로 나중에 들어간게 먼저 나옴 그림을 보자! 우리는 새 값을..

1. 배열과 리스트 코딩테스트는 자료구조를 빼놓고는 논할 수 없다. 자료구조는 데이터를 효율적으로 저장,접근,수정하기 위한 그릇이자코테에서 데이터를 다루기 위한 전략이다. 사용해야 하는 알고리즘에 따라 적절한 자료구조를 선정해서 사용하는 것이 매우 중요하다!그 중에서도 우리는 먼저 기초 자료구조인 배열과 리스트를 살펴보자!  모두가 알겠지만 기본 자료구조인, 배열과 리스트는 비슷하지만 다르다. 배열(Array List)이란, 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.배열의 값은 인덱스를 통해서 참조할 수 있고, 선언한 타입의 값만 저장가능하다.  배열의 특징은 간략히 정리하면 아래와 같다. 1. 인덱스를 사용하여 값에 바로 접근 가능2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을..

알고리즘 문제를 풀다보면 디버깅 기능이 그렇게 편리할 수 없다.break point를 설정해서 뭐가 문제인지 알 수 있고, 현재 변수 값이 어떤 값을 가지고 있는지도 알 수 있어서너무 편리한 것 같다. 개발을 하면서 이런 편리한 기능을적극적으로 사용하지 않은 시절을 많이 후회하기도 합니다. 주변 많은 분들이 디버깅을 하지않고, 문제를 풀다가 반복문 범위를 잘못 설정하거나, 변수를 잘못 사용한것을 발견하지 못하여, 코테를 떨어지는 경우도 많이 보았기 때문에디버깅 기능을 적극적으로 사용하는 것이 중요합니다 코테를 진행할때, IDE 사용을 허락하는 경우, 디버깅 기능을 적극적으로 사용하여오류를 잘 잡아보도록 합시다! 디버깅 하는 방법1. 디버깅 하고자 하는 코드에 break point(빨간 점) 설정!2. 코..

기초 개념을 다시 연습하는 이유코테 준비를 하면서, 오류와 실수를 범하는 일이 많아지고, 그러면서 자연스럽게 문제도 시간내에 풀지못하는 일이 많이 발생하였습니다. 문제를 푸는 과정을 회상해 보니,1. 처음 부터 문제를 잘못 읽음 (제대로 안 읽음)2. 반복문 범위를 잘 못 설정함.3. 변수 이름을 이상하게 만들어서 변수 사용하는게 헷갈림등등 여러 많은 문제들... 논리적인 오류보다는 이런 잡다한 실수들이 많다는 것을 알게 되었습니다.이런 실수들이 지금 보기에는 별거 아닌거 같지만,점점 쌓이다보면 코테 탈락에 치명적인 요소로 적용한다는 것을 몸소 체감하였기에,기초를 바로잡아야 한다고 생각하였습니다. 그래서 가장 기본기인 시간복잡도 부터 포스팅 하려고 합니다. 시간복잡도코테 문제를 풀기 위해서는 시간 복잡도..