개발자 꿈나무의 블로그

* 개요 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 표현되며, 이 때 노드를 정점이라고 말한다. 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접한다.'라고 표현한다. * 인접 행렬 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같이 연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될 수 없는..

* 개요 Binary Search(이진 탐색)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 또한 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점(start), 끝점(end), 그리고 중간점(mid)이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 순차 탐색의 시간복잡도가 O(N)인 것에 비해, 이진 탐색의 시간복잡도는 O(logN)이다. 따라서 데이터의 양이 많은 경우에는 이진 탐색을 활용..

* 개요 파이썬으로 코테, 자료구조, 알고리즘 공부를 진행하다보니, 리스트 선언의 중요성이 더욱 와닿는다는 것을 느꼈다. 오늘 소개할 List Comprehension(리스트 컴프리헨션)은 리스트를 초기화하는 방법 중 하나이다. 리스트 컴프리헨션은 간단히 0부터 19까지의 수 중에서 홀수만 포함하는 리스트를 만들고자 할 때는 다음과 같이 리스트를 초기화할 수 있다. 이 경우 한 줄의 소스코드로 리스트를 초기화할 수 있어 매우 간편하다. # 0부터 19까지의 수 중에서 홀수만 포함하는 리스트 array = [i for i in range(20) if i % 2 == 1] print(array) # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 참고로 위 소스코드를 일반적인 소스코드로 작성..

* 개요 수학, 특히 그래프 이론에서 회로가 없는 연결된 무향의 그래프를 Tree(트리)라고 한다. 트리의 각 부분의 명칭과 용어는 다음과 같다. 트리는 항상 root 노드에서 시작된다. 루트 노드는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리 구성을 띤다. 레벨은 0부터 시작한다. 트리는 항상 단방향이기 때문에(단방향이 아니면 순환 참조가 발생하여 문제 발생) 간선의 화살표는 생략이 가능하다. 일반적으로 방향은 위에서 아래로 향한다. 루트 노드(root node/root): 트리에서 부모가 없는 최..

* 개요 원래 카카오뱅크 인턴쉽 서류를 넣을 생각이 없었지만, 최근 자료구조와 알고리즘 공부를 열심히 하기도 했고, 카카오 코딩테스트는 어렵기로 악명이 자자하기에, 한번 풀어보고 싶은 마음에 지원하게 되었다. 필자는 포트폴리오라고 해봤자 졸작이 다였는데, 심지어 졸작도 희망하고자 하는 직무(백엔드)와는 아예 다른 AI와 관련된 프로젝트였다. 하지만 인턴쉽이기도 하고, 면접으로 가는 갈림길은 코테라고 생각을 했기에 넣어보았다. 하지만 결과는... 설마 하던 광탈이었다... 인턴쉽이라고 하여 만만히 보았던 내가 큰 착각을 했던 것 같다. * 부족했던 점 왜 떨어졌나 곰곰히 생각을 해보니, 포트폴리오가 너무 부실했던 것은 아닌가 생각이 들었다. 필자의 github 주소나 백엔드 관련 프로젝트는 포트폴리오에 포..