나의 알고리즘 공부 여정6 - 탐색 알고리즘, 코드 기능과 형태 개선

 

20210315_TIL

 

• 한층 심화된 알고리즘 문제들을 풀어나가며 기존에 알았던 자료구조, 알고리즘 개념을 좀 더 세부적이고 깊이 알 수 있었다. 특히 탐색 알고리즘 관련한 학습을 많이 진행했다.

 

• 팀원분과 코드 리뷰를 진행하면서, 시간 복잡도 낮추기와 같은 기능적 측면의 코드 개선뿐만 아니라 가독성과 같은 형태적 측면의 코드 개선을 생각해보기 시작했다. 결국, 협업을 위해서는 가독성 좋은 코드가 중요하고 형태적 측면의 코드 개선 역시 충분히 중요하게 고려해 보아야 하는 문제다.

 

1. 탐색 알고리즘

 

알고리즘에는 많은 종류가 있지만, 그 중에서도 정렬 알고리즘과 탐색 알고리즘이 가장 대표적이다.

오늘은 탐색 알고리즘에 대해 다뤄보고자 한다.

 

탐색 알고리즘은 알고리즘 문제 풀이에 참 많이 사용된다. 탐색 알고리즘의 종류는 다음과 같다.

 

완전 탐색 ( = 브루트 포스 )

 1. 선형 구조

  1) 순차 탐색

 

 2. 비선형 구조

  1) DFS

  2) BFS

  3) 백트래킹: DFS가 발전한 형태

 

이분 탐색

 1. 선형 구조

  1) 이분 탐색

 

백트래킹을 제외한 완전 탐색 알고리즘들의 예시를 소개하겠다. (백트래킹은 다음에 다시 다루겠다.)

저장된 데이터에 일정한 규칙이 없어 하나하나 다 찾아봐야 할 때 많이 쓰인다. 브루트 포스는 가능한 모든 경우의 수를 탐색하는 완전 탐색을 의미한다. 선형 구조에서는 반복문을 활용해 하나하나 순차적으로 모두 탐색하는 순차 탐색이 있다. 

1436번: 영화감독 숌

반복문을 돌려 데이터를 1씩 늘려 모두 확인해보는 순차탐색의 대표적 예이다.

 

 

 

DFS와 BFS 역시 완전 탐색법에 해당한다. 이 친구들은 탐색 과정에 나름의 규칙이 있어 무식하지 않을 것 같지만, 결국 이 친구들의 정체성도 완전 탐색이다. 무식한 방법이라는 소리다.

1260번: DFS와 BFS

 

인접 리스트를 활용해 DFS를 구현했다. 지난 주 소개했던 DFS 구조보다 조금 더 진화한 형태다.

지난 주 소개한 DFS 구현식은 완전이진트리 형태를 가정한 DFS 구조였는데, 오늘은 완전이진트리가 아닐 때의 DFS 구조다.

추가된 수식은 27~29번째 줄이다. 완전이진트리가 아니기 때문에 자식 노드들끼리 무작위로 연결되어 있다. 때문에 예시로 자주 활용되는 완전이진트리의 DFS 탐색 순서와도 살짝 결이 다르다.

 

 

 

완전이진트리 구조가 무너지고 5번과 6번 노드가 저런 형태로 연결되었을 경우, 6번 노드를 3번을 거쳐서 방문하기 전에 5번 노드를 통해 이미 방문하게 된다. 따라서 방문해 있는 노드가 이미 방문했던 노드는 아닌지에 대한 검사가 한 번 더 필요하게 된다. 완전이진트리는 인접노드가 방문한 노드인지 검사하는 것(31~33번쨰 줄)로 충분했지만, 이 경우는 아니다.

 

 

다음은 이어서 BFS 구조다. DFS와 방문한 곳을 저장하는 수단으로 이용되는 자료구조의 형태만 다르다.

DFS는 스택을 사용하지만 BFS는 큐를 사용한다.

 

 

백트래킹은 DFS 구조를 기반으로 하는 조오금 덜 무식한 방법이다. promising이라는 개념을 도입해, 노드를 방문하기 전 찾고자 하는 데이터가 있는지 없는지 판단하고 없다면 방문하지 않는다. 일단 DFS 구조를 기반으로 하고 있다는 점에서 완전탐색으로 분류되기도 하는데 이렇게 생각하면 될 거 같다. 10채의 집에 사람이 있는지 없는지 판단하기 위해 DFS는 문을 다 열고 사람이 있는지를 확인하는 반면, 백트래킹은 집에 불이 켜져 있다면 문을 열어 사람이 있는지 확인하는 방법이다.

 

탐색 알고리즘에 대한 문제들을 집중적으로 풀면서 발견한 사실이 있다면, 탐색 알고리즘은 정렬 알고리즘에 비해 알고리즘이 메인이되고 자료구조가 역선택되는 경우들이 많다. 아무래도 완전탐색을 진행해야 하는 상황이라면, 가지고 있는 데이터가 개판(?)이어서, 혹은 데이터가 없어서 하나하나 만들면서 확인해야 해서인 경우가 많다. 때문에 데이터를 저장해두는 자료구조가 상대적으로 덜 중요해지는 상황이 많아서인듯 하다. 이때 자료구조는 탐색 진행 상황을 저장하기 위한 수단으로서 많이 이용된다. (모든 상황에 들어맞는건 아니겠지만, 일단 탐색이 중요한 상황이라면 탐색 알고리즘을 선택하고 그에 맞는 자료구조를 역선택하자)

 

반면, 정렬은 가지고 있는 데이터를 더 잘 정리해 주는 개념인지라 자료구조가 메인이 되고 정렬 알고리즘은 이를 정리해주는 수단으로서 많이 활용된다. 아무래도 정리할게 있어야 정리를 할 수 있으니, 일단 자료구조가 있어야 하기 때문인 것 같다. (데이터 정리가 중요한 상황이라면 어떻게 데이터를 저장할 지 생각한 후, 자료구조를 먼저 선택하고 정리하기 위한 수단으로써 정렬 알고리즘을 고르자)

 

알고리즘 중 가장 많이 쓰이는 알고리즘이 정렬알고리즘과 탐색 알고리즘이기 때문에 이 정도 정리된 개념을 가지고 있으면 문제에 접근할 때 많은 도움이 될 것이다.

 

 

2. 코드 개선

 

1) 형태적 측면 (형식적 측면)

 

그간 코드 개선 하면 시간복잡도를 줄이는 기능적 측면에서만 생각해왔다. 팀과의 코드 리뷰를 하면서 코드의 형태적 측면에서의 개선도 중요하겠다는 사실을 배웠다. 이번 팀원분은 필드에서 일하는 개발자들과의 교류도 꽤 있으셨던 분이라, 조금 더 실제 개발 환경에 대한 이야기를 많이 들을 수 있었다. 띄어쓰기, 줄 간격 넣기, 변수 작명 등 다분히 형식과 관련한 코드 개선 역시 중요함을 알 수 있었다. 결국 '가독성'의 문제인데, 컴파일 과정에서는 전혀 영향을 미치지 않는 것들이지만 결국 코드는 사람이 짜고 사람이 수정하는 것이기 때문에 가독성이 무척 중요하다. 특히, 협업과정에서 가독성이 좋지 않은 코드는 일의 능률에 굉장한 악영향을 미친다. 

좋은 코드 형식이란..

결국 형식은 업계 종사자들 간의, 팀간의 약속이란 뜻이다. 그렇다면 실제 종사자들이 어떻게 쓰는지 그들의 코드를 형식적 측면을 고려하며 자주 살펴보면 좋을 듯하다. 실제 종사자의 자료 링크를 가져왔다. 참고하면 좋을 것 같다. 그리고 팀원분께 들은 것들을 간단하게 정리해보자면,

 

 (1) 빈 라인은 무조건 한줄만! (Enter)

 (2) 변수명은 이 변수가 무엇을 가리키는지 직관적으로 판단 가능한 수준으로! i 도 웬만하면 쓰지 말 것.

 (3) 불린 타입 조건문을 작성할 때에는, if list == True: 보다는 if list: 를 쓰는 것이 정석

 

 

2) 기능적 측면

 

시간 복잡도를 줄이기 위한 코드 효율화 작업은 오늘도 역시 계속되었고, 관련해서 몇 가지 배운 점들이 생겼다.

 

1. if 문 다음에 else 쓰는데 웬만하면 else 쓰지 말 것.

왼쪽은 else를 사용하였고, 오른쪽은 continue를 사용해 if 조건문에 걸리면 아래의 append 메쏘드가 적용이 안되도록 하였다. 이렇게 했을 때의 장점은 else에 해당하는 데이터들이 조건문을 한 번 "덜" 거칠 수 있다는 점이다. 오른쪽 코드의 경우 조건문 확인 없이 바로 append가 진행 된다.

 

2. Class 잘 활용하자.

알고리즘 문제 풀이에서는 몇 개의 테스트 케이스만 출력하면 되니까 Class를 잘 사용하지 않게 되는데, 꽤 큰 프로젝트 단위의 코드를 짜게 되면 Class를 얼마나 잘 사용하느냐에 따라 시간복잡도 뿐 아니라 코드 짜는 시간까지 줄일 수 있다. 알고리즘 문제에서는 Class를 잘 안쓰게 되는데 의식적으로라도 풀이과정 속에서 Class를 활용해보며 연습해 놓을 필요가 있다. 

 

 

3. 데이터를 여러 줄 입력받아 해당 줄에 입력된 데이터 별로 각각 출력값을 print 해줘야 한다면, for문 안에 입력을 받도록 하는 것이 더 효율성이 좋다.

 

오른쪽 14번쨰 줄을 보면 for 문안에 입력값을 받도록 되어 있다. 이 방법이 for문 바깥에 데이터를 미리 다 받아두고 인덱스 값으로 그 데이터를 각각 받아오는 것보다 시간복잡도를 줄여 준다. for문을 한번 덜쓰게 되고, 고려해야 하는 인덱스 갯수도 줄기 떄문이다.