나의 알고리즘 공부 여정1 - 우리는 왜 알고리즘을 공부하는가?

 

20210308_TIL

 

• 금, 토, 월 3일간 백준 알고리즘 문제들을 풀어나가며, 문제풀이에 필요한 개념들을 구글링해 공부했다.

 

• 그때 그때 필요한 자료들을 찾아 공부하며 머릿 속에 쌓은 파편적인 지식들을 파이썬 문법, 자료구조, 알고리즘이라는 큰 구조에 분류해 집어넣는 작업을 진행했다. 머릿속에 굴러다녔던 정보들이 좀 정리가 된 기분이다.

 

0. 선 문풀 후 개념정리

 

지난 주 금, 토 그리고 오늘까지 3일간 백준 알고리즘 문제를 풀었다. 노베이스이지만, 문제를 풀기위해 문제풀이에 필요한 개념들을 하나 하나 검색하며 문제를 풀었다. 직접적인 풀이를 검색한 것은 아니다. 내가 했던 검색 방법의 예를 들면,

 

"알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다."

 

라는 문제를 풀 때에는 '최빈값 찾기'를 검색 하였다. 그렇게 최빈값을 찾았다. 이후, 찾은 최빈값이 딕셔너리 형태로 표현됨을 확인한다. 딕셔너리는 key 값으로 value 값을 불어오는 것이라는 것을 검색을 통해 학습한다. 이후, 내 상황이 value 값으로 key 값을 찾아야 하는 상황임을 인지한다. 그럼 다시 key 값과 value 값을 뒤집을 수 있는 코드를 구글링 하는 것이다. 그럼 또 그렇게 뒤집힐 시, 같은 key 값에 해당하는 value 값이 두 개 생기면 value 값은 하나 남고 다 삭제 됨을 학습한다. 이런 식이다. 꼬리에 꼬리를 물고 계속 학습이 진행된다.

 

3일간 이런 방식으로 학습을 진행한 뒤, 머릿속에 꽤 많은 정보가 파편적인 형태로 굴러다니고 있음을 인지하였다. 한번 큰 구조를 만들어 정리해야 할 필요성을 느꼈다.

 

1. 전체 구조 잡기

 

1-0. 파이썬 문법

 

파이썬 기본 문법을 3일간 어느 정도 익혔는지 테스트 하기 위해 파이썬 기본 문법 자료의 목차를 쭉 보면서 내가 문제를 풀면서 익힌 개념들을 떠올렸다. 문제를 풀면서 기본적인 파이썬 문법은 거의 익힌 것 같다. 목차에서 1~2개 말고는 생소한 개념이 없었다. 다만, 정확한 언어로 개념을 기억하고 있기는 힘들기 때문에 파이썬 문법 목차를 아래에 정리해두겠다. 나중에 구글링하기 편하도록...

 

• 변수선언
• 숫자형 자료형
• Bool 자료형
• 문자열
• 문자열 연산 (문자열 더하기, 문자열 길이 구하기, 대소문자 구하기, 문자열 나누기)
• 문자열 인덱싱 [ ] , 슬라이싱 [ : ]
• 리스트 (리스트 길이 구하기, 인덱싱 및 슬라이싱, 중첩, 덧붙이기, 정렬하기, 요소 찾기)
• 딕셔너리 (딕셔너리 값 넣기, 키를 통한 검색, 리스트와 딕셔너리 조합)
• 조건문 - if 문, else 와 elif
• 반복문 - for 문, while 문
• 함수
• 튜플 (리스트와 비슷하지만 불변인 자료형)
• 집합 (중복이 제거되고, 교집합/합집합/차집합을 구할 수 있다)
• f-string
• try-except문
• 파일 불러오기 (from main import *)
• 한줄로 코드 줄이기 (if문 삼항연산자, for문 리스트 안에서 for문 돌리기)
• map, filter, lambda식
• 함수의 매개변수
• 클래스

 

 

으음.. 파이썬 기본 문법은 정리가 다 되었다. 이 정도 기억하고 있으면 응용은 구글링을 통해 하는것이 효율적일 것이라 생각한다. 사실, 저기서 자료형과 명령어를 나누어서 더 구분해 놓고 싶지만 다음기회에...ㅎㅎ

 

 

 

1-1. 우리는 왜 알고리즘을 공부하는가?

 

가장 중요한 부분이다. 우리는 왜 알고리즘을 공부하는가? 무언가를 할 때에는 항상 그 목적을 생각해야 한다.

 

알고리즘: 문제 해결 순서

자료구조: 컴퓨터에 정보를 효율적으로 저장하고 관리하는 방법

파이썬: 프로그래밍 언어

 

(* 제가 이해한대로 정리한 부분이라 틀린 개념이 있을 수 있습니다. )

결국 '자료구조'란 정보저장형태가 존재한다. 정보 저장 형태는 여러 개 존재한다. 우리는 이를 '알고리즘'으로 구현한다.

 

하나의 자료구조를 만들기 위해서는 입력, 저장, 출력 등등 여러 가지의 동작들이 필요하다. 이런 동작들이 단계별로 쌓여 하나의 큰 Flow가 만들어지고 동작하는 기능이 된다. 이게 알고리즘이다.

 

우리는 컴퓨터로 하여금 이러한 알고리즘을 동작하게 해야 한다. 우리는 이걸 파이썬이라는 프로그래밍이란 언어로 컴퓨터에게 명령을 내려 컴퓨터로 하여금 알고리즘 대로 동작을 수행하게 만든다.

 

그렇다면, 상황별로 데이터 간 관계에 따라 그에 적합한 자료구조가 달라진다. 이러한 자료구조를 최적으로 실행시키는 알고리즘 역시 달라진다. 결국 우리가 자료구조와 알고리즘을 배우는 이유는 '최적화' 때문이다. 상황에 맞는 자료구조를 선택하고, 최적화된 알고리즘을 선택해 코딩하기 위해 우리는 자료구조와 알고리즘을 공부해야 한다. 한 예로써, 어떠한 정보를 찾으려 할 때, 자료구조와 알고리즘을 배우지 않으면 for문 중첩으로 풀 문제를, 자료구조와 알고리즘을 공부하면 hash 함수로 간단하게 해결할 수 있다.

 

 

다음은 자료구조와 정렬을 정리해 놓았다.

저 도표에 있는 개념들과 정렬 개념들은 이번 주 안에 다 알도록 공부하는 것이 목표다. 단순 구조는 문제를 풀 때 input 값을 가져오기 위해서 구글링하며 많이 배웠다. 또한,  무수히 많은 typeErorr들을 고치면서도 꽤 많은 지식을 습득한 부분이다. 선형구조와 비선형 구조에 집중해서 개념 공부를 진행해야 겠다.

 

공부하면서 가장 헷갈렸던 부분은, 자료구조의 개념과 파이썬 언어가 100%일치하지 않는다는 사실이었다. 해쉬함수 개념은 딕셔너리를 통해 구현되고, 스택이라는 자료구조는 리스트를 통해 구현되는 식이다... "자료구조, 알고리즘, 파이썬 언어가 개별 개념으로 존재한다." 이거를 기억하면 좋을 것 같다. 앞으로 경험이 쌓으면, 코드를 짤 때에 세 개를 정확하게 분리해 이해하고 내가 지금 어떤 자료구조, 알고리즘, 파이썬 언어를 쓰고 있는 지 명확히 이해할 수 있었으면 한다.

 

 

출처: https://wayhome25.github.io/cs/2017/04/17/cs-18/

 

 

정렬

 

• 버블정렬
• 선택정렬
• 삽입정렬
• 병합정렬
• 힙
• 퀵

 

 

 

1-2. 알고리즘 문제풀이 실전

 

1. 입력

 

어떤 형태로 입력을 받을 지를 정해야 한다.

[Python 문법] 파이썬 입력 받기(sys.stdin.readline)

 

2. 자료구조 선택

 

적합한 자료구조를 선택했다면, 자료구조에서 일반적으로 사용하는 개념과 method들을 이용하여 코드를 짠다.

관련해서 이번주에 열심히 공부해서 이번주 TIL에 다뤄보겠다.

 

 

3. 반례 찾기

 

test case를 통과했는데도 백준 홈페이지에서 답안이 틀렸다고 뜬 다면 케이스는 두 가지다.

 

1. 오타: 제발 확인하자.. 오늘 오타 때문에 답안 틀린건데 로직 틀린줄 알고 로직만 봤다.. ㅠ

 

2. 반례: test case가 생각보다 그렇게 친절하게 주어지지 않는다. 알아서 반례를 찾아야 한다. 그렇기에 test case에 맞춰서 되는대로 코드를 짜는 게 아니라 내가 짠 코드 로직은 충분히 숙지하고 있어야 한다.

 

아래는 오늘 푼 문제인데, 반례 케이스 연습하기 좋아서 가져와봤다. : )

 

10250번: ACM 호텔