GW LABS

한동안 그래프 탐색 문제를 다뤄보지 않아서 복습겸, C++ 공부겸 기본적인 DFS 문제를 풀어봤다. 백준 2644번 촌수계산 문제는 인접 리스트 형태의 자료구조에서 DFS를 통해서 노드의 연결 깊이를 계산하는 문제였다. 인접 리스트이기 때문에 vector를 사용해서 풀었는데 파이썬 보다는 코드가 길어지는 경향이 있다. 아래는 소스코드이다. #include #include #include using namespace std; int search(int searchStart, int searchEnd, vector graph, bool visited[101], int count) { if (searchStart == searchEnd) return count; int answer = -1; visited[s..

두번째 포스팅은 대표적인 선형 자료구조인 연결리스트이다. 알고리즘과 자료구조를 공부하면서 장벽이었던 녀석이기도 하다. 구현과 더불어 연결리스트를 알고리즘 문제에서 다룰 때 하지 말아야할 실수를 정리한다. 1. LinkedList (연결리스트) 연결리스트는 자료를 저장하고 포인터를 이용해서 다음 자료를 가르키는 형식으로 구성된 선형 자료구조이다. 처음 연결리스트를 공부할 때 동적배열과 차이점을 파악하지 못했다. 가장 큰 차이점은 바로 메모리에 저장방식에 있다. 배열 혹은 동적배열의 경우 메모리에 자료를 저장할때 순서대로 저장된다. 연결리스트는 현재 메모리에 비어있는 곳에 랜덤하게 저장되고 자료를 접근할 때에는 포인터로만 접근을 한다. 2. 연결리스트를 다룰 때 주의할 점 연결리스트를 다룰 때 주의할 점은 ..

나는 C++와 같은 unmanaged 언어를 실무에서 다뤄볼 수 있는 기회가 지금까지 없었다. 컴퓨터 공학의 기본기를 익히기 위해서 C/C++같은 언어를 꾸준히 수련하는 것이 필요하다고 생각되어 이 포스팅을 시작해보려고 한다. C++로 기본적인 자료구조를 구현해보면서 컴퓨터 공학의 기본기를 수련해보자! 1. ArrayList (동적배열) 오늘의 주제는 동적배열이다. 동적배열은 크기가 가변적으로 늘어나는 배열이다. 초기화한 배열의 크기가 모자르게 되면 현재 배열보다 2배 큰 배열을 할당하고, 기존에 있던 값을 복사한다. 이렇게 배열크기를 조정하면 삽입과 인덱스 접근에서 시간복잡도 O(1)을 보장할 수 있다. 여기서 중요하게 볼 점은 동적배열의 크기가 입력에 비례해서 커진다는 점이다. 그렇기 때문에 입력과 ..