개발자 배트맨의 일상🦇

안녕하세요 배트맨🦇 입니다 ! 오늘은 투 포인터 알고리즘의 개념과 파이썬으로 구현하는 방법에 대해 정리해보겠습니다. 얼마 전 Kakao기업의 겨울 인턴 채용 코딩테스트에 투 포인터 문제가 출제되었습니다. 개념과 구현 방법을 미리 알고 있으면 좋을 것 같습니다. 그럼 시작해보겠습니다 ! 투 포인터 알고리즘이란? 말 그대로 2개의 포인터를 사용하는 알고리즘입니다. 프로그래밍에서 포인터라는 용어는 변수의 메모리 공간 주소를 가리키는 변수를 말합니다. C언어 같은 low level 언어를 다룰 때는 메모리 주소에 직접적으로 접근해서 구현해야 하지만 Python은 리스트 자료형을 제공하고 인덱스 값만을 이용해서 구현할 수 있습니다. 투 포인터 알고리즘은 배열의 인덱스를 가리키는 2개의 포인터를 설정하고, 이를 옮..

Computer Science/Algorithm 2022. 11. 11. 01:56

안녕하세요 배트맨🦇 입니다 ! 오늘은 최단 경로를 찾을 때 자주 사용되는 다익스트라(Dijkstra) 알고리즘에 대해 정리해보려고 합니다. 알고리즘의 개념과 우선순위 큐를 이용한 파이썬 코드를 구현하는 것으로 내용을 구성하려 합니다. 시작해보겠습니다! 다익스트라 알고리즘이란? 음의 가중치가 없는 그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다. - 나무 위키 - 즉, 모든 간선에 음수가 아닌 가중치가 있는 그래프가 존재할 때, 한 노드에서 도달할 수 있는 모든 노드까지 최단 거리를 구할 수 있는 알고리즘입니다. 다익스트라 알고리즘을 공부하면서 느꼈던 부분은 원리가 쉽게 이해되는 반면에 구현하는 것은 ..

Computer Science/Algorithm 2022. 11. 9. 08:27

안녕하세요 배트맨🦇 입니다 ! 오늘은 동적 프로그래밍(이하 DP)이 무엇이고 어떻게 구현해야 하는지에 대해 정리해보려고 합니다. 동적 프로그래밍이란? 최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 조금 장난스럽게 말해서 답을 재활용하는 거다. 앞에서 구했던 답을 뒤에서도 이용하고... -나무 위키- 나무 위키의 정의를 보면 앞의 범위에서 구해진 답을 활용하여 해당 지점의 답을 구하는 알고리즘이라는 것을 파악할 수 있습니다. 더 정확히 말하자면 DP의 포인트는 답을 구하는 과정 중 한 번 수행했던 과정은 다시 반복하지 않기 위해 결과를 메모리에 저장한 후, 필요할 때 그 값을 가져와 쓰는 것입니다. 여기..

Computer Science/Algorithm 2022. 9. 25. 15:47

안녕하세요 배트맨🦇 입니다 ! 오늘은 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다. 또 백트래킹 문제인 "BOJ 15649번 - N과M" 을 풀어보려고 합니다. 시작해보겠습니다! 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘. 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘. - 나무 위키 - 나무 위키의 정의만 보고는 이해가 쉽지 않습니다. 즉, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘입니다. DFS를 사용하여 조건에 맞지 않으면 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하며 원하는 조건을 찾아갑니다. BOJ 15649 - N과 M (1) http://www.acmicpc.net/probl..

Computer Science/Algorithm 2022. 9. 21. 21:42