강의로 돌아가기
조재훈

슬라이스를 이용할 경우

안녕하세요
저는 for문을 돌려 하나씩 꺼내 x와 비교 후 같을 경우 해당 주소값을 리스트에 넣는 형식으로 답을 구현했습니다만

문제에 보니 슬라이스를 이용하는 방법도 설명 해주셨는데
주어지는 리스트가 길어질 경우 제가 해결한 방식은 비효율적인거 같더라구요

아래 답변 중 슬라이스 이용하는 답변엔
index 함수를 이용하여 주소 발견 후 주소 이후부터 다시 잘라서 index 함수를 이용하여 발견
없을 경우 대비하여 exception 처리 를 말씀 하셨는데

이 방법도 마찬가지로 찾을려고 하는 값이 많이 분포 되어 있을 경우 계속 돌아 갈 수 있어서 시간이 걸릴 것 같은데요

위에 방법 처럼 순차적으로 index 함수를 이용하여 값을 찾은 후 다시 슬라이스 하는 방법이 시간이 덜 걸리는지

아님 임의의 방법 (ex: 리스트 길이가 100 일 경우 30씩 쪼개어 답을 찾는 다는식) 으로 하는 방법이 시간이 덜 걸리는지
어떤게 좋은 방법인지 궁금합니다.

1 개의 답변
이시윤

리스트 L 에 대하여 메서드 index() 를 적용하면 (L.index(x)) 특정 원소 (x) 가 리스트 내에서 발견되는 첫 인덱스를 리턴합니다. 예를 들어, L = [63, 72, 54, 83, 72, 58] 일 때 L.index(72) 의 리턴 값은 1 이며, 이것을 알았으므로 L[2:] 에 대해서 또 index() 메서드를 적용하면 (L[2:].index(72)) 그 리턴 값은 2 입니다 (왜냐면, 슬라이스된 리스트 내에서의 인덱스이므로).

이것을 이용하여, 순환문을 반복하면서 슬라이싱과 index() 메서드를 활용하여 주어진 문제에 대한 해결책을 마련할 수 있습니다. 한번 (연습 삼아) 코드를 작성해보는 것도 좋을 듯합니다.

그런데, 효율성 얘기를 하게 되면, 이 방법이 위에 언급한 방법 (for 순환문을 이용해서 하나씩 검사하는 방법) 에 비하여 나을 것은 없습니다. 단지 프로그래밍하는 (코드를 구현하는) 방법 또는 방식이 조금 달라질 뿐입니다. 어느 쪽이 더 나은 방법이냐에 대해서는 딱히 잘라 말하기는 어려울 것 같습니다.

하나 생각해보기로 하죠. L.index(x) 와 같은 연산을, Python 내부에서는 어떻게 구현했을까요? 이것을 아는 (또는 짐작할 수 있는) 것이 전체 효율성 (보다 정확히 얘기하자면 복잡도) 을 논하는 데에는 중요할 것 같네요. 리스트에 들어 있는 원소들의 순서가 규정되어 있지 않다면 (무작위 순서를 따른다면), 제 3 강에서 얘기하는 선형 탐색 (linear search) 보다 나은 방법은 존재하지 않습니다. 즉, 리스트의 원소들을 하나씩 따라가면서 비교하는 방법 이외에 더 효율적 인 방법은 있을 수가 없습니다. 이러한 것을 컴퓨터과학에서는 문제의 복잡도 라는 식으로 표현합니다. (알고리즘의 복잡도에 대해서는, 이후의 제 6 강을 참고하세요.)

바꾸어 말하면, 여기에서 주어진 연습문제에 대해서는 복잡도 O(n) 보다 나은 알고리즘은 있을 수 없으며, 그것은 수학적으로도 증명 가능합니다. 이렇게 얘기하고 나면, 질문에서 말한 for 순환문을 이용한 방식과, 이 답변에서 얘기하는 슬라이싱과 index() 메서드를 이용한 방식의 복잡도는 O(n) 으로서 동일합니다.

  • 조재훈
    아 그렇군요 제가 index() 함수에 대한 로직을 모른 상태에서 효율을 논하는게 조금 어불성설 이었네요 말씀대로 단지 구현의 차이 이지 언급하신 문제의 복잡도 에선 같다 라는 말씀이 맞는거 같네요 개인적으로 알려주신 슬라이스 방식으로 코드를 구현 해보고 좀 더 생각을 해보겠습니다 조재훈 2018.09.21 02:06
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.