brunch

매거진 무늬만 블랙햇 해커

라이킷 3 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by Younggi Seo Jul 08. 2018

동명이인 찾기 알고리즘

Use a nested loop to find out same name

파이썬에서는 데이터 값이 중복되지 않고 자료의 순서도 의미가 없는 집합(set)을 사용하여 중복된 값을 찾을 수 있다. 입력은 n명의 이름이 들어 있는 리스트이고, 결과는 같은 이름들이 들어 있는 집합(set)이다.

빈 집합을 만들려면 set()을 이용하고, 집합에 자료를 추가하려면 add() 함수를 이용한다. 또한, 리스트와 마찬가지로 집합 안에 자료가 몇 개 있는지 알려면 len() 함수를 이용한다(이승찬, 2017).

동명이인을 찾는 알고리즘은 난이도의 순서 상 재귀보다 앞서 있지만 이전에 쉽게 풀어서 지금 다시 리뷰를 하는데, 의외로 헛갈렸다. 왜냐하면 리스트 값을 검색하는 인덱스(index, 색인)를 중첩 반복문 내부에서 지정하는 것이 처음에 스스로 쥐어짜 내었던 게 아니었기 때문이다. 이 알고리즘에서 주의할 점은 다음과 같다.

비교할 이름을 뽑은 다음에는 뽑은 이름보다 순서상 뒤에 있는 이름하고만 비교하면 된다. 자기 자신과 비교하는 것은 무의미하고 앞에 있는 이름과는 이미 비교가 끝났기 때문이다.

리스트의 마지막 이름을 기준으로는 비교하지 않아도 된다. 자신의 뒤에는 비교할 이름이 없고, 앞과는 이미 비교가 끝났기 때문이다.

같은 이름을 찾으면 결과(result) 집합에 그 이름을 추가한다.

여기서 두 번째 규칙이 중요하다. 왜냐하면 이미 비교가 끝났다는 말에서 비교하기 위해 돌리는 반복문이 하나가 아니라, 두 개여야 된다는 것을 끄집어내야 하기 때문이다. 즉 중첩 반복문(nested loop)이 쓰여야 차례로 중복 없이 비교가 가능한 프로그래밍이 가능하다.

동창 중에 이름이 같은 친구를 출력하는 프로그램을 실행해서 같은 동명이인을 result에 담는 것을 디버깅함.

첫 번째 반복문 for i in range(0, n-1)에서 범위 안의 첫 번째 값은 시작 위치, 두 번째 값은 종료 위치를 삽입한다. 그래서 i를 0부터 'n-2'까지 반복한다는 뜻이다. 왜 검색하는 끄트머리 위치가 n-1이 아니라 n-2라면, 컴퓨터의 배열(Array List)에서 색인(index) 하기 위한 첫 번째 값은 항상 0이기 때문이다. 그러므로 n개의 값을 가지고 있는 있는 List에서 index는 0부터 시작하고 끄트머리를 색인하기 위해서는 n-1이 된다.

1차원 배열 리스트(List)를 색인(index)할 시 첫 번째 값은 0, 끝 값은 -1부터 시작한다는 것을 알 수 있다.

첫 번째 반복문은 디버깅을 통해서 보면 실제로 이 반복문을 실행하는 가운데, 내부에 있는 두 번째 반복문을 통해서 서로 빠짐없이 비교한다. 첫 번째 반복문의 변수 i가 0일 때 하위의 반복문을 중첩하여 실행하므로 i=0일 때, j의 시작 값 i+1(비교 기준으로 정해진 i번째 위치에 1을 더한 위치의 값, 즉 중복되지 않게 하기 위해 i의 뒤의 값)부터 n까지, 즉 n-1(인덱스 상으로 끄트머리)까지 비교하는 것을 뜻한다.

첫 번째 반복문 for i in range(0, n-1)에서 보듯이 끄트머리의 앞(n-2)까지만 돌리는 까닭은 아래 표에서 알 수 있듯이 리스트의 마지막 값에 해당하는 my firstLove_youngmi는 변수 i가 두 번째 반복문의 변수 j을 통해 리스트의 서로 다른 자료를 이미 한 번씩 다 비교했으므로 제외해도 되기 때문이다(즉, 마지막 'my firstLove_youngmi'를 기준으로는 비교하지 않아도 된다. ~~첫사랑 이후의 여자는 모든 남자에게 비교가치가 없다~~).

n = 11일 때 비교 횟수

알고리즘을 분석하면, 같은 이름을 찾는 알고리즘이므로 두 이름이 같은지 '비교'하는 횟수를 따져 보면 된다(이승찬, 2017).

일반적인 입력 크기인 n에 대해서 볼까?

0번 위치 이름: n-1번 비교(자기를 제외한 모든 이름과 비교)

1번 위치 이름: n-2번 비교

2번 위치 이름: n-3번 비교

...

n-2번 위치 이름: 1번 비교

n-1번 위치 이름: 0번 비교

결국 전체 비교 횟수는 0 + 1 + 2 + 3 + 4 + ... + (n-1) 번, 즉 1부터 n-1까지의 합이다. 위의 프로그램에서는 1부터 10까지의 합(11 x 5)인 55번이 된다. 55번의 중복 없이 리스트의 이름을 비교하기 위해서 실제 중첩 반복문의 실행 순서를 보면, 변수 j의 반복문 돌림 횟수 11번 곱하기 변수 i의 반복문 돌림 횟수 11번으로 총 121번의 되풀이(Iteration) 된다.

1부터 n까지의 합을 구하는 가우스 공식에 n 대신 n-1을 대입한 것과 같은 비교 횟수의 공식은 다음과 같다.

1 + 2 + 3 + ... + (n-1) =

= (1/2 x n의 제곱 - 1/2 x n)

(1/2 x n의 제곱 - 1/2 x n)* 번 비교해야 한다는 것을 알 수 있다. 빅 O 표기법으로는 O(n의 제곱)이라고 표현한다. n의 제곱에 비례해서 계산 시간이 변하는 것이 핵심이므로 n의 제곱 앞의 계수 1/2이나 -1/2n은 무시하고 O(n의 제곱)으로 표현한 것이다.

계산 복잡도가 O(n의 제곱)인 알고리즘은 입력 크기 n이 커지면 계산 시간은 그 제곱에 비례하므로 엄청난 차이로 증가한다. 알고리즘 분석에 빅오 표기법이 중요한 이유는 이렇게 입력 크기가 커질 때 계산 시간이 얼마나 증가할지 가늠해볼 수 있기 때문이다(이승찬, 2017).

cf.) n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어보자. 예를 들어 입력이 리스트 [ "Tom", "Jerry", "Mike"]라면 다음과 같은 세 가지 경우를 출력한다.

Tom - Jerry
Tom - Mike
Jerry - Mike

Ans.)

List의 자료는 중복된 값을 구분하지 못해서 출력값 역시 중복된 값을 그대로 pairing 시킨다.

참고로 n명에서 두 명을 뽑아 짝으로 만들면 짝 조합이,

1부터 n까지의 합을 구하는 가우스공식과 달리 +가 아니라 -이다.

가지 출력된다. 이 경우의 수를 nC2라고도 표현한다.

빅오(대문자 O) 표기법의 정확한 수학적 정의에 따르면, 한 식에 대문자 O 표기법은 딱 하나만 정답이 아니다. 하지만 O뒤에 붙은 소괄호 안에 담긴 값을 최대한 간단히 적는 것이 가장 일반적인 방식이다. 빅오 표기법의 정의가 궁금하다면 다음 링크를 참고하기 바란다(이승찬, 2017).

https://ko.wikipedia.org/wiki/점근_표기법

* 포스트 창에서 분수 표현을 할 수 없어서 수식을 말 그대로 표현하였다.

참조

1) 이승찬 저. (2017). 모두의 알고리즘 with 파이썬, 서울:(주)도서출판 길벗.

keyword