TIL - algorithm - 01

# 알고리즘 공부하기

며칠 전부터 알고리즘(algorithm) 공부를 하고 있다. 알고리즘은 취업을 준비하는 개발자들이 입사 과정에서 치르는 코딩 테스트를 위해 연습하는 일종의 문제 풀이다. 나의 경우 특별히 코딩 테스트를 하는 기업 취직을 목표로 하는 것은 아니지만, 초보 개발 입문자로서 지금껏 배웠던 python 문법을 실제 코드에 적용하는 공부를 하고 싶어 알고리즘 문제를 풀게 됐다.

현재 풀고 있는 문제들은 '프로그래머스'라는 사이트에서 제공되는 것들이다. 예상했던 일이지만, 문제의 난이도가 개인적으로 어렵게 느껴진다.(Lv1부터 어렵다ㅠ) 문제에서 요구하는 능력은 논리적, 수학적 사고력인데, 문과 출신인 내가 소화하기엔 아직까진 조금 버거운(?) 능력치라는 생각이 든다. 다행인 점은 문제 풀이를 위해 고민하고, 어려운 문제를 통해 부족한 부분을 보완하는 등의 과정이 제법 흥미롭다는 사실이다. 앞으로 알고리즘 문제를 통해 새롭게 알게 된 개발 지식을 정리해볼 생각이다.

오늘 정리할 문제는 '완주하지 못한 선수(Lv1)'이다. 문제는 웹 사이트를 참고하는 것으로 하고, 따로 적진 않을 생각이다.

# 완주하지 못한 선수(Lv1) - 오류 코드

• 오류 코드

    def solution(participant, completion):
        for v in participant:
            if v in completion:
                completion.remove(v)  # 동명이인이 있을 경우를 고려해야 함
            else:                     # 이를 위해 remove()를 활용하여 비교가 끝난 참가자 이름을 완주자 명단에서 삭제                          
                answer = v            # 문제점: 삭제하면 코드의 효율성이 떨어진다
        return answer     


print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))

• 문제점

  • 참가자 모두가 완주자 명단에 존재하는지를 확인해야 하므로 코드의 효율성이 떨어진다.

# 완주하지 못한 선수(Lv1) - 정답 코드

• 정답 코드

    def solution(participant, completion):       # participant와 completion은 요소 값 하나를 빼곤 모든 것이 같은 리스트 객체
        participant.sort()                       # 정렬 뒤 값을 비교하는 것이 요소 값 삭제보다 효율성이 높다
        completion.sort()                        # 같은 인덱스의 요소 값이 달라지는 시점 : 완주하지 못하는 선수의 등장
        i = 0
        while participant[i] == completion[i]:
            i += 1
        return participant[i]


print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))

• 해결 방법

  • 코드의 효율성을 높이려면, 참가자 명단의 모든 요소를 확인(비교)하는 대신 완주하지 못한 선수가 발견될 때까지만 확인(비교)이 진행되도록 코드를 짜야 한다.

  • 그러려면, 우선 리스트 객체의 정렬이 필요하다.

  • 그 다음, for문 대신 while문을 활용하여 두 리스트 객체 요소의 값이 일치하지 않을 때 반복문이 멈추도록 해야 한다.

# review

• 코드의 효율성을 고려하여 코딩하는 것이 중요하다.

• for문 내부에서 in 혹은 not in을 활용하여 iterable 객체의 요소를 일일이 확인하는 코드는 코드의 효율성을 떨어뜨릴 수 있다.

• 이 경우, while문을 고려해보는 것이 효율성 측면에서 좋을 수 있다.

• except 안에 pass 입력하기(번외)

  • 단순히 error를 잡아내기 위해 예외처리를 하는 경우, except 내부에 pass를 입력해주면 된다.

    def solution(numbers):
        answer = []
        for i in range(len(numbers)):
            try:
                for j in range(i+1, len(numbers)):
                    value = numbers[i] + numbers[j]
                
                    if value in answer:
                        continue
                
                    answer.append(value)
            except IndexError:        # error 발생 막기 위해 예외처리 막는 경우엔, except절에 (continue도 가능, but continue는 반복문 루프에서만 사용 가능) pass를 입력하면 된다.
                pass

        answer.sort()

        return answer

    print(solution([5,0,2,7]))