코테는 DFS랑 BFS를 이해하기 시작했을 때가 진짜지 !

#코딩테스트가 너무 어렵고 힘들 때,,,

코딩테스트(알고리즘) 를 준비하면 수 많은 자료구조 및 알고리즘을 만나게 되는데 이때 드는 생각은 아이큐 180에 영재발군단 출신이 아니라면? 보통은 내가 할 수 있을까? 라는 생각이 들기 시작한다.

#먼저 코딩텍스트를 해야하는 이유?

2024년 현 시점의 개발자 취업과 AI의 발전!

매년 취업난은 오고 있지만, 학부생으로써 학년이 올라갈 때마다 점점 선배들의 취업에 대한 곡소리가 내 귀에 들려오기 시작했다. 물론, 기준을 낮추고..욕심을 버리면 갈 수 있다는 현실적인 말도 있지만!

현재 우리가 사는 이곳은 이상을 위해 공부를 하고 준비를 하고 있으니 조금 고점을 봐도 괜찮지 않을까?

솔직히 요즘 Chatgpt, Claud등과 같은 AI 도구들이 많이 나오면서 학교 과제를 진행하거나, 프로젝트를 만들 때 엄청난 도움을 받고 있는건 확실하다.

그러면서 동시에 드는 생각이 내가 정말 이걸 다 이해하고 있는걸까? 물론 이해하면서 코딩하는 분들도 있지만!!! 대부분의 학부생 그리고 개발자 분들도 한번 쯤은 일단 실행이 되면, 그냥 넘어간 적 이 있을 것이다.

그렇기 때문에 포트폴리오나 프로젝트의 완성도의 기준은 점점 높아져서 과제나, 프로젝트는 들은 상향 평준화의 시대 가 왔다.

또한 내가 모르는 것이 있다면 바로바로 물어봐서 정보의 질이나 상식? 같은 우리가 알아둬야하는 것들의 기준도 높아지고 있다. 그렇기 때문에 회사가 사람을 뽑을 때도 chatgpt보다 못하는 사람은 안 뽑으려고 할 것이다.

그럼 우리는 엄청 멋있는 포트폴리오를 준비해야하는가? 아니!!! 그러면 우리는 CS지식을 달달 외워야 하는가?? 아니!!!

물론 위에 두개도 매우매우 중요하지만, 회사는 바쁘고 영리를 목적으로 움직이는 집단이다. 그들은 나를 빠른 시간안에 회사에 필요한 사람을 찾아야한다. 우리가 마치 프로그램을 만들 때 시간복잡도를 고려하면서 코딩을 하는 것처럼 말이다...

그렇기 때문에 회사는 코딩테스트 를 통해 n차적으로 사람을 가려낸다..

#포트폴리오 준비도하고 CS도 공부하고 코딩테스트도 하라구요?

넵. 그게 당신이 선택한 개발자의 길 입니다. 그리고 코딩테스트가 아니라 사실은 알고리즘 공부 입니다 !

단지 여러분들이 테스트를 보는 것에 겁을 먹어서 그런 것이고, 개발자라면 알고리즘 파트는 정말 재미있는 부분입니다 ㅎㅎㅎㅎ

#알고리즘은 어떻게 공부할까요..너무 어려운데요..

알고리즘 파트는 학부생 기준으로 2학년이나 3학년 때 배우게 된다. 기본적으로 언어를 어느정도 다룰 줄 알아야하고, 코드를 읽는 법이나 흐름을 알아야 하기 때문이다.

-더닝크루거 효과 그래프 입니다-

위 사진처럼 개발자의 길을 걷는 사람은 알고리즘을 만나면 절망의 계곡에 오르게 된다.. 절망의 계곡에서는 "반드시 나만의 공부 방식을 찾아야한다" 입니다.

각자 사람마다 방법은 다르지만, 제가 공부하는 방법을 알려드리려고 합니다.

우선 저는 알고리즘을 공부할 때 언어(언어는 본인이 편한 것, 해야하는 것으로 하시면 됩니다)에 익숙해지기 위해 백준 단계 문제에서 브론즈 문제부터 문제를 풀었습니다.

#백준 문제 추천(브론즈~실버)

백준 추천 문제 Bronze ~ Silver

이 구간에서 일단 문제를 읽고 해석하는 문해력을 키워야 합니다. 그러면 점점 욕심이 나기 시작합니다! 사실 이 구간도 처음 시작하면 어렵고, 답지 보고 싶고 그러는데 처음에는 그래도 됩니다 !

그래도 흥미가 있어야 문제를 풀 수 있으니까요 ㅎㅎㅎㅎ

여기서 처음 핵심은 대충하는 것 입니다. ( 또 무슨 이상한 소리인가 싶겠지만) 대충하라는 것은 문제를 대충 풀라는 것이 아니고, 하루에 10~20개 정도 문제를 풀라고 하는 것이 아닙니다.

알고리즘은 Learning Curve가 있습니다. 이런 러닝커브가 있는 것들은 흥미를 잃지 않는 것이 중요합니다. 문제를 많이 풀고 시간이 지체될 수록 당연히 흥미를 잃게 됩니다. 풀기 싫을 때는 넘겨야 합니다.

단, 꾸준함 이 중요합니다.

#꾸준함이 생겼으면, 어려운 것도 천천히 해봅시다.

브론즈의 세계에서 탈출하시게 되면 이분탐색, 분할 정복, 스택, 큐, 우선순위 큐, 그래프, BFS, DFS, 위상정렬, 동적 프로그래밍, 그리디 등..이 여러분들을 찾아 올건데요.

겁먹지 말고 우리는 BFS, DFS, 그리디, 동적프로그래밍(DP) 이렇게 4개만 고집해서 풀어보는 겁니다!

엄청 많았던거에서 4개로 목표로 잡으니 할 만 하다고 느껴지지 않나요?

#공부 방법!!

"기록하지 않으면, 기억되지 않는다" 라는 말을 한번 쯤은 들어봤을텐데요. 저희는 사람이기 때문에 도구를 이용해 기록해야 합니다. 텍스트로 컴퓨터에 적으면 되지 않느냐? 라는 말을 하는데, 이것은 비추천 입니다.

손으로 적고 직접 실행 순서를 따라가보고 손코딩을 해봐야 기억이 되기 쉽고 무엇보다, 흥미가 생기게 됩니다. 일기를 쓰는 이유도 나중에 보면 괜히 뿌듯하고, 오늘의 일기를 적다보면 어제의 일기도 보고 그러면서 한번 더 기억하게 되고 그러지 않나요? ㅎㅎㅎ

기록하는 방법은 각자 스타일에 맞추면 됩니다. 저는 저는 좌측 상단에 문제 번호와 이름, 그리고 내려가면서 문제를 적고, 입력과 출력에 대한 예시를 적고 동작방식과 필요한 것들을 적습니다. 그리고 빈 공간에 손 코딩을 적어보고 컴파일을 해볼 수 있는 편집기를 사용해서 코딩하면서 문제를 풉니다.

저도 아직 초보단계라 흥미를 잃지 않기 위해 한 문제에 40분은 넘어가지 않습니다.

단, 처음부터 답지보고 푸는 것은 안 좋습니다!!!

#DFS와 BFS를 이해하기 시작했을 때?

깊이 우선 탐색(depth-first search), 너비 우선 탐색(breadth first search) 을 텍스트와 그림으로 접했을 때는

이 사진을 보고 3분을 멍 때렸다. 뭔가 알 것 같은데 몰랐기 때문이다.

알 것 같은데 모르는 느낌은 많은 사람들이 공감할거라 생각한다. 마치 머리로는 이해하는데 이걸 코드로 해보라고 하면 어떻게 사용하는지 정확하게 모르기 때문이다.

그 이유는 What? - Why? - How? 이 세 가지가 딜레마로 다가온다고 생각한다.

저 세 가지 물음 중에 하나라도 정확하게 모르면, 다시 처음으로 돌아온다.

#What?

깊이 우선 탐색 은 그래프 또는 트리의 각 노드를 깊이(depth) 우선으로 탐색하는 알고리즘입니다. 즉, 가능한 한 한 경로를 따라 계속 깊이 들어가다가 더 이상 갈 수 없을 때 다시 돌아와 다른 경로를 탐색합니다.

너비 우선 탐색 은 그래프나 트리에서 한 노드를 시작점으로 가까운 노드부터 탐색하는 알고리즘입니다. 즉, 루트에서 시작해 인접한 노드를 먼저 탐색하고, 그다음 레벨의 노드를 탐색해 나가는 방식입니다.

#Why?

DFS

• 그래프나 트리의 모든 노드를 방문하거나 경로를 탐색할 때 사용합니다.
• 연결된 경로를 깊게 탐색하면서 원하는 노드나 해를 찾을 때 유용합니다.
• 백트래킹(backtracking) 문제나 미로 찾기와 같은 문제에서 효율적으로 사용됩니다.

BFS

• 경로 탐색에서 가장 짧은 경로를 찾을 때 유용합니다.
• 그래프의 모든 노드를 레벨별로 탐색할 때 적합합니다.
• 네트워크 최단 경로 문제나 친구 추천 시스템 등에서 널리 사용됩니다.

#How?

DFS:

• 스택(stack)을 사용해 구현할 수 있으며, 재귀적으로도 구현 가능합니다.
• 동작 순서: 시작 노드를 스택에 추가하고 방문했다고 표시합니다. 스택에서 노드를 꺼내고, 해당 노드에 연결된 인접 노드들을 하나씩 확인합니다. 방문하지 않은 인접 노드를 스택에 넣고, 해당 노드에 대해 위 과정을 반복합니다. 더 이상 방문할 노드가 없으면 탐색을 종료합니다.

BFS:

• 큐(queue)를 사용해 구현합니다.
• 동작 순서: 시작 노드를 큐에 넣고 방문했다고 표시합니다. 큐에서 노드를 하나씩 꺼내고, 해당 노드에 인접한 방문하지 않은 노드를 모두 큐에 추가합니다. 더 이상 방문할 노드가 없을 때 탐색을 종료합니다.

이런식으로 먼저 정리를 하고 시작하면 코드를 이해하는데 더 도움이 된다

#이렇게 공부를 시작하고 DFS, BFS 관련 문제를 풀었을 때

• 기초적인 탐색 알고리즘 이해
  • 그래프 탐색의 대표적인 알고리즘이라서 트리, 그래프, 맵, 미로, 탐색등 다양한 유영을 알게 되었다.
• 문제 해결의 구조 이해
  • 하나의 문제를 두 가지의 방법으로 풀어보니 시야가 넓어진다. DFS로도 풀어보고 BFS로도 풀어보니 다양한 문제 해결의 구조를 이해할 수 있다.
• 재귀와 반복을 통해 핵심적으로 쓰이는 부분을 알 수 있었다.

DFS, BFS 문제 추천

모두 알고리즘을 행복하게 풀고 정보도 많이 공유했으면 좋겠다는 마음에 이렇게 내 생각을 정리해서 글을 써보았습니다!! 다들 화이팅 하세요 !