목록전체 글 (46)
altair의 프로젝트 일기
오징어 게임에 대한 스포일러가 포함되어 있습니다. 넷플릭스에서 볼 수 있는 이 한창 인기몰이를 하고 있습니다. 재작년 기생충의 인기를 떠올리게 합니다. 가히 코리안 신드롬이라 할만하군요. 얼마 전, 흥미로운 소식을 접하게 되었습니다. 유튜브와 같은 소셜 미디어에서 많은 사람들의 입에 오르내리는 미국의 우파 정치 평론가, 밴 샤피로가 오징어 게임에 대해 이야기한 것입니다. 오징어 게임을 리뷰한 밴 샤피로의 유튜브 영상 대강 요약하자면 드라마가 돈이 많은 VIP들은 더럽고 추악한 모습을, 돈이 없는 가난한 참가자들은 고결함을 보여준다는 것입니다. 게다가 VIP들은 모두 서양인들이며, 프론트맨은 'Fly me to the moon'을 들으며 고상하게 앉아있습니다. 이 모든 것들이 서양 자본주의에 대한 고정관념..
학기 중에 DFS를 사용하여 주어진 미로의 최단 경로를 탐색하는 과제를 한 적이 있었다. 그리고 학기의 마지막 즈음에 다익스트라 알고리즘으로 그래프의 최단 경로를 탐색하는 것도 구현했었다. 그러다가 든 의문이 "다익스트라 알고리즘이 그래프에서 최단거리를 찾을 수 있다면 미로에서도 찾을 수 있을까?"였다. 이번 글에서는 여러 최단 경로 탐색 알고리즘으로 미로의 최단 경로를 구하고 알고리즘들을 비교해볼 것이다. 모든 코드는 Clion을 사용해 C++로 작성되었으며 개발환경은 macOS Big Sur 11.4 이고, 실행 환경은 라즈베리파이 OS와 g++ 8.3이 설치된 라즈베리파이 4B이다. 미로와 다익스트라 다익스트라는 기본적으로 "음이 아닌 가중치를 가진 간선들과 정점들로 구성된 그래프"에서 특정 정점에..
학기 중에 미로 탐색 과제를 했었다. 주어진 미로의 최단경로와 그 개수를 탐색하는 DFS 알고리즘을 만들었다. 스택을 사용하여 길이 막힐 때마다 갈림길로 돌아오고, 도착점에 이르렀을 경우 다시 이전 갈림길로 돌아가 다른 길이 존재하는지, 존재한다면 이전의 경로보다 짧은지 탐색하는 알고리즘이었다. 더 이상 찾아볼 경로가 존재하지 않을 때 이 알고리즘은 종료된다. 결과적으로 알고리즘은 잘 작동했다. 하지만 내가 만족스럽지 못했던 점은 알고리즘을 테스트할 수 있는 환경이 미리 주어진 미로 밖에 없었다는 점이다. 물론 미로를 약간 수정하여 입력할 수 있었지만 어디까지나 약간의 수정에 불과했고 더 큰 미로에서 얼마나 이 알고리즘이 잘 작동하는지 알고 싶었다. 그런 의미에서 완전히 무작위적인 미로를 만드는 방법을 ..
정렬 알고리즘을 살펴보다보면 C언어에서 라이브러리에 퀵 정렬 함수가 있다는 것을 알게 된다. 이번에 정렬 알고리즘을 배우면서 qsort 함수를 실행하고 내가 직접 구현한 퀵 정렬과 그 실행시간을 비교할 기회가 있었다. 가장 간단한 퀵 정렬 알고리즘은 최악의 경우 \(O(n^2)\) 의 시간 복잡도를 갖는다. 정렬되지 않은 배열을 정렬할 때 $$log_{2}n$$의 재귀 단계를 가지지만, 피벗을 기준으로 파티션이 극단적으로 나뉠 때는 $$n^2$$의 단계를 갖는다. 많이 쓰이는 힙 정렬은 비록 퀵 정렬보다 살짝 느리지만 이런 최악의 경우를 갖지 않고 항상 안정적인 시간 복잡도를 갖는다는 장점이 있다. 이번 프로젝트에서 확인했던 일반적인 퀵 정렬 알고리즘의 실행시간은 다음과 같다. 데이터 개수는 5만개로 하..