추상 자료형과 알고리즘, 의사 코드

추상 자료형?

학교에서 자료구조 & 알고리즘 수업을 들으면서 추상 자료형(Abstract Data Type, ADT)이라는 개념을 알게 됐다.

언어에서 제공하는 원시 타입(primary type)들로는 해결이 어려운 문제들이 있다. 그럴 땐 기존의 원시 데이터 타입을 응용해서 새로운 자료 구조를 만들어야 하는데, 자료 구조를 만드는 방법은 상황마다, 언어마다 다양하다.

추상 자료형은 어떤 자료형을 값과 연산들의 집합으로 정의한 것이다. 구체적인 언어나 명령어가 아닌 한 단계 추상적으로 구현 방법을 설명한다. 구현에 의존하지 않는다.

즉, 추상 자료형은 how(구체적인 구현 방법)가 아닌 what(집합과 연산들의 목록)을 추상적으로 명시해놓은 것이다.

음식 레시피와 같다. 내가 어떤 환경(어떤 프라이팬을 쓰는지 등)에서, 어디서 산 닭고기를 쓸지는 알려주지 않는다. 어떤 음식이 완성되어야 하는지와 그 과정을 설명하는데 집중한다.

추상 자료형과 의사 코드

The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented.
The process of providing only the essentials and hiding the details is known as abstraction.

ADT라는 개념은 추상적인 사고를 도와준다. 이러한 추상화를 다른 과정으로 확장하고 싶었다.

그러다 평소에 풀던 알고리즘에 눈길이 갔다. 매일 1문제씩 풀고 있었는데, 알고리즘에 추상화를 적용시킨다면 어떨까 생각했다. 아무리 알고리즘 문제들이 다양하다지만 결국 문제들도 '유형', '과정' 등 문제들의 기반이 되는 추상적인 원리가 있지 않을까?

의사코드는 ADT와는 개념 자체가 달랐지만, 구체적인 구현 결과 이전에 추상적인 레시피를 생각한다는 부분에서 같았다.

그리고 알고리즘을 풀기 전에 의사코드(pseudo code)를 쓰는 습관을 들이기 시작했다.

알고리즘과 의사코드

어떤 문제가 주어져 있고 이것을 컴퓨터로 해결하려고 한다고 치자.

첫번째 해야 할 일은 문제를 해결할 수 있는 방법을 고안하는 것이다.

두번째 해야 할 일은 이 방법에 따라 컴퓨터가 수행해야 할 단계적인 절차를 자세히 기술하는 것. 이 절차를 알고리즘이라고 부른다.

알고리즘을 기술하는 데는 다음 4가지 방법이 있다.

1. 한국어, 영어 같은 자연어
2. 도식(diagram, flowchart)
3. pseudo code(의사 코드)
4. 프로그래밍 언어

1번은 모호성이 존재한다. 2번은 전체 구도를 이해하기엔 좋은 방법이지만 매번 작성하긴 어려울 것이다. 3번, 의사코드는 자연어보다 체계적이고 프로그래밍 언어보단 덜 엄격하다.

내 의사코드 풀이 방법

1. 문제 정의

입력과 출력까지 포함해서, 문제가 요구하는 것이 무엇인지를 정의한다. 이 과정에서 내가 문제를 제대로 파악하고 있는지, 내가 알고 있는 개념인지 알 수 있었다. (수학 문제를 풀 때와 비슷하다. 결국 문제에서 물어보는 개념은 한정되어있고, 그걸 찾는 것이 문제풀이의 큰 힌트가 된다.)

2. 브레인 스토밍(해결 방법 떠올리기)

사실상 아무말 대잔치.

우선 문제의 요구사항을 충족하려면 어떤 과정을 거쳐야 할지 러프하게 생각한다.

이 과정이 반복되면 나중에는 직관력을 얻을거라 생각한다.

1. 구체적인 로직들

자주 쓰이는 로직들이 있다. 반복문, 조건문 등.

반복문은 loop, 조건문은 if 등으로 쓰고 있다.

4. 데이터 정의(입력값, 함수의 인자값같은 사소한 데이터도 포함)

데이터를 생각하는 과정에선 내가 불필요한 변수를 쓰고 있지는 않은지 고민해보게 된다. 그리고 문제가 요구하는 조건을 어기진 않는지 확인해보게 된다.

아래는 평균과 최댓값을 이용해서 학생 성적을 조작하는 문제였다. 백준 1546. C언어.

1. 입력: 학생 수 N
2. loop(N): 
    2-1. 입력: 학생 성적
    2-2. 성적을 배열에 저장
    2-3. 해당 성적이 가장 높을 경우, 최대값을 갱신
3. loop(N): 
    3-1. 성적 조작하는 연산
                total += arr[i] / maximum * 100
4. 출력: 그 평균값(total / N)을 출력

데이터:
int 학생 수 N
int 각각의 학생 성적 score
float 성적들의 총합 total
float 출력할 값 

의사코드는 백준에서 문제풀이할 때 크게 도움이 되고 있다. 확실히 이 방법을 도입하고 난 후에 한번에 통과되는 빈도수가 높아졌다.

이젠 생각하는 과정 없이 코드를 치면 어딘가 불안하다. 분명 내 머리가 이렇게 똑똑할 리 없을텐데..라는 생각부터 든다. 그리고 실제로 그럴 때가 많다.

프로그래밍 과정에 대한 생각

의사코드를 꼼꼼히 쓸 수 있다면 사실상 문제 풀이는 50% 이상 끝난 셈이다.

나머지는 문법, 코드의 효율성, 컴파일 에러, 실행 속도 등을 신경쓰는 일들이다.

프로그래밍의 과정을 생각했을 때, 코드가 물리적으로 타이핑되는 과정은 생각의 부산물이 되어야 한다고 생각한다. 프로그래밍의 본질에 가까운 것은 문법, IDE 등을 신경쓰는 과정보다는 생각하는 과정과 로직이지 않을까.

참고:

C언어로 풀어쓴 자료구조

https://www.youtube.com/watch?v=RDzsrmMl48I&t=128s

https://www.geeksforgeeks.org/abstract-data-types/