d라이브러리

수호가 ‘컴퓨팅 사고’에 대해 조금씩 깨닫기 시작했어요. 컴퓨팅 사고는 일을 논리적이고 효율적으로 처리하는 과정을 말하지요. 이때 꼭 필요한 과정이 ‘알고리즘’이랍니다.

컴퓨팅 사고에서는 주어진 문제들을 분석하고 가장 최선의 해결 방법을 찾는 과정이 있어요. 알고리즘은 이렇게 찾은 해결 방법 다른 문제들에도 바로 적용할 수 있도록 정리한 절차이지요. 컴퓨터 프로그래밍이나 컴퓨팅 사고에서는 여러 가지 알고리즘을 사용해 일을 효율적으로 처리해요. 이번 화에서 이야기할 것은 순서를 정하는 알고리즘이에요.

세상 대부분의 일에는 순서가 있어요. 예를 들어 아침에 일어나서 학교에 가려면 세수 또는 샤워를 하고, 옷을 입고, 밥을 먹고, 가방을 들고 집을 나서서 학교까지 이동을 하지요. 그런데 순서가 섞여 버리면 어떻게 될까요? 옷을 모두 입은 채 샤워를 하거나 잠옷 차림으로 학교에 가는 상황이 생길 거예요. 옷을 입을 때도 바지 위에 속옷을 입거나 신발 겉에 양말을 신을 순 없죠. 이처럼 일상생활에서 순서는 매우 중요한 역할을 차지하고 있어요.

컴퓨터나 기계에게 일을 시킬 때는 순서가 더욱 중요해요. 컴퓨터나 기계는 주어진 대로 일을 하기 때문에 자신에게 주어진 프로그램이나 코드만 보고 순서가 잘못됐는지 알아낼 수가 없어요. 그래서 컴퓨터에게 순서가 정해진 일을 시킬때에는 컴퓨터가 작업을 순서대로 정렬할 수 있게 하는 과정이 필수랍니다. 이때 필요한 것이 바로 ‘위상정렬 알고리즘’이지요.

위상정렬 알고리즘은 일의 작업을 순서에 맞게끔 나열하는 알고리즘이에요. 1960년대 초반, 회사에서 진행하는 업무의 일정을 순서대로 배치하기 위해 개발됐지요. 지금은 컴퓨터가 순서대로 처리해야 할 일
을 지시하거나 복잡한 기계를 제조하는 과정에 유용하게 쓰인답니다.

예를 들어 자동차는 자동차를 움직이는 데 필요한 전기 부품들과 운전할 때 필요한 부품들이 정확하게 맞아 떨어져야 해요. 그런데 컴퓨터가 순서를 제대로 인지하지 못해서 바퀴를 굴러가게 하는 전선에 엑셀 대신 브레이크를 연결해 버렸다고 해요. 그럼 차가 제대로 움직이지 않겠죠? 이런 문제를 방지하기 위해 제작 공정을 정렬해 놓는 거랍니다.

위상정렬 알고리즘은 게임에도 많이 쓰여요. 게임에서 캐릭터가 레벨 업을 하는 과정을 생각해 보세요. 보통 ‘A라는 미션에서 성공해 B라는 아이템을 얻고, 그걸 몬스터 C와 이겼을 때 받는 D라는 아이템과 합체해야 레벨이 올라갈 수 있다’는 식으로 조건이 붙을 거예요. 게임에 따라서는 제작자가 짠 순서대로 가면 가장 효율적으로 레벨 업을 할 수 있는 경우도 있고, 사용자가 맵을 보고 두 아이템을 가장 빨리 얻는 길을 결정해야 할 때도 있어요. 앞은 제작자가, 뒤는 사용자가 위상정렬 알고리즘을 이용하는 경우랍니다.