들어가기

알고리즘 문제를 풀다 보면 시간복잡도를 생각해야 하는 경우가 종종 생긴다. 특히 codility는 문제마다 시간복잡도 기준이 있어서, 기준을 넘기지 못하면 문제를 풀어도 score가 50 이하로 나오는 경우가 많다.

찾아보니 파이썬 주요 함수, 메소드의 시간복잡도를 정리한 페이지가 있었다. (Complexity of Python Operations) 자주 사용하는 것들을 이곳에 정리하고 종종 참고하려고 한다.

list

Dict

reference

• Python wiki’s Time Complexity
• Python Set Slice Complexity
• Complexity of Python Operations

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

0 represents a car traveling east,
1 represents a car traveling west.
The goal is to count passing cars.
We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers,
returns the number of pairs of passing cars.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

For example, given:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
the function should return 5, as explained above.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer that can have one of the following values: 0, 1.
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1),
beyond input storage (not counting the storage required for input arguments).

풀이코드 - O(n^2)

• Detected time complexity: O(N)
• 조합 가능한 (0,1) pair의 갯수를 찾는다
• 조건
  • 0의 index < 1의 index
  • pair의 갯수가 100만이 넘으면 -1 리턴
  • 시간 복잡도 O(N)

def solution(A):
    index_zero = [i for i, x in enumerate(A) if x == 0]
    result = 0
    for i in index_zero:
        result += A[i+1:].count(1)

    if result > 1000000000:
        return -1
    return result

다른사람 풀이

• 리스트를 순회하면서, 0의 갯수를 누적해서 더하고, 1을 만나면 누적 값을 result에 합산한다

def solution(A):
    result = 0
    count_zero = 0
    for i in A:
        if i == 1 and count_zero == 0:
            continue
        elif i == 0:
            count_zero += 1
        elif i == 1:
            result += count_zero

    if result > 1000000000:
        return -1
    return result

문제출처

문제

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M. For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function: def solution(N) that, given a positive integer N, returns the number of its factors. For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Assume that: N is an integer within the range [1..2,147,483,647]. Complexity: expected worst-case time complexity is O(sqrt(N)); expected worst-case space complexity is O(1).

풀이코드

• 시간복잡도 : O(sqrt(N))
• 1 ~ 루트 N 까지의 숫자만 검색하여 시간복잡도 O(sqrt(N)) 으로 연산

def solution(N):
    i = 1
    result = 0
    while i**2 <= N:
        print(i)
        if i ** 2 == N:
            result += 1
        elif N % i == 0:
            result += 2
        i += 1
    return result

다른사람 코드

def solution(N):
    candidate = 1
    result = 0
    while candidate * candidate < N:
        # N has two factors: candidate and N // candidate
        if N % candidate == 0:      
          result += 2

        candidate += 1

    # If N is square of some value.
    if candidate * candidate == N:  result += 1

    return result

6월 18일 (일)

오늘 한 일

• Django를 활용하여 인스타그램 기능을 가진 웹어플리케이션 연습을 시작했다.
  • 인증기능 구현 (built-in view, form 활용)
  • built-in User Model 확장
  • 비밀번호 수정 구현

6월 17일 (토)

오늘 한 일

• 어제 연습한 서울대 웹벤처창업프로그래밍 기말고사 풀이영상을 참고하여 같은 페이지를 반복해서 구현했다.
• 자바를 활용하여 간단한 알고리즘 문제를 풀었다.

6월 16일 (금)

오늘 한 일

• django를 활용하여 comment 입력, 수정, 삭제 기능 구현을 연습했다. 강의를 보기만 하고, 보고 따라하고, 혼자 다시 만들어보고 이런식으로 3번을 반복해보았다. 최근 집중 할 다른 일이 생겨서 3주 정도를 django에 소홀히 했는데 이제 다시 열심히 해야지!
• 이진석님이 공유해주신 서울대 웹벤처창업프로그래밍 기말고사를 풀어보았다. 수동적으로 강의 영상을 보는 것보다 학습 효율이 좋은 것 같다. 확실히 고민을 더 많이하게 되고 그만큼 찾아서 배우는 것도 많았다. 강의도 좋지만 이런 식의 문제가 주어지는 것도 찾아서 공부할 동기부여가 되는 것 같다.
  • 문제내용
  • 풀이영상

6월 15일 (목)

오늘 한 일

• askdjango를 통해서 django를 연습했다.

6월 14일 (수)

오늘 한 일

• 생활코딩 - Java의 다형성 에 대한 강의를 다시 들었다.
  • 다형성(Polymorphism)이란 같은 이름의 메소드나 클래스가 다양한 방법으로 동작하는 것을 의미
  • overloading과 다형성 : 인자의 데이터 타입, 인자의 갯수에 따라서 같은 이름의 메소드 이지만 서로 다른 동작방법을 가질 수 있다.
  • class와 다형성 : (전제)클래스 B는 클래스 A를 상속받은 클래스이다.
    부모 클래스 A의 데이터 타입으로 클래스 B를 인스턴스화 했을 때,
    클래스 A에 존재하는 맴버만이 클래스 B의 맴버가 된다. (외부에서 제어할 수 있는 조작 장치를 클래스 A의 멤버로 제한하는 효과)
    동시에 클래스 B에서 오버라이딩한 맴버의 동작방식은 그대로 유지한다.
• Hello Coding 그림으로 개념을 이해하는 알고리즘) 를 읽었다.
  • 배열과 연결리스트를 결합한 복합 자료구조에 대한 예시가 있었다. 컴퓨터 공학 수업때 잠깐 다뤘던 내용 같은데 오랜만에 책으로 다시 접하니 새로웠다.
  • Q. 페이스북과 같은 서비스에서 사용자 이름 목록을 저장하려면 배열을 사용해야할까 연결리스트를 사용해야할까?
  • A. 두개를 섞어서 쓴다.
    • A~Z 까지 26개의 크기로 구성된 배열이 존재하고, 각각의 칸은 다른 연결리스트를 가르킨다.
    • 예를 들어 배열의 첫번째 칸은 A로 시작하는 모든 사용자 이름을 담은 연결리스트를 가르킨다.
    • siwa 라는 사용자가 페이스북에 새로 등록하면 19번째 칸으로 가서 연결 리스트를 찾아 “siwa” 라는 이름을 마지막에 추가한다.
    • monkey 라는 사용자를 검색하고 싶다면, 13번째 칸으로 가서 M으로 시작하는 모든 이름을 가진 연결리스트에서 검색한다.
  • 위와 같은 복합 자료구조의 속도는 아래와 같다.
    • 검색 속도 : 배열 > 복합 > 연결리스트 (배열보다 느리고, 연결리스트 보다는 빠름)
    • 추가 속도 : 연결리스트 = 복합 > 배열 (배열보다 빠르고, 연결리스트와는 같음 )

6월 13일 (화)

오늘 한 일

• tryhelloworld java 중급 강의를 들었다.
  • java.lang 패키지, java.util 패키지에 대해서 따로 다루고 있어서 유용한 것 같다.
  • 결국에는 Java API 문서를 읽고 필요한 정보를 스스로 얻을 수 있도록 연습해야겠다.
  • 생활코딩 - API와 API 문서 보는 법

6월 12일 (월)

오늘 한 일

• tryhelloworld java 강의를 들었다.
• codility 알고리즘 문제를 풀었다.
• askdjango를 통해서 오랜만에 Django 를 연습했다. 반복해서 2번정도 만들면서 감을 다시 찾아야겠다.

문제

reverseStr 메소드는 String형 변수 str을 매개변수로 입력받습니다. str에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 String을 리턴해주세요. str는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다. 예를들어 str이 “Zbcdefg”면 “gfedcbZ”을 리턴하면 됩니다.

풀이코드 (java)

import java.util.Arrays;
import java.util.Collections;

public class ReverseStr {
  public String reverseStr(String str){
    String[] array = str.split("");
    Arrays.sort(array);
    Collections.reverse(Arrays.asList(array));
    return  String.join("",array);
  }

// 아래는 테스트로 출력해 보기 위한 코드입니다.
  public static void main(String[] args) {
    ReverseStr rs = new ReverseStr();
    System.out.println( rs.reverseStr("Zbcdefg") );
  }
}

다른사람 코드

import java.util.Arrays;

public class ReverseStr {
    public String reverseStr(String str){
      char[] sol = str.toCharArray();
      Arrays.sort(sol);
      return new StringBuilder(new String(sol)).reverse().toString();
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        ReverseStr rs = new ReverseStr();
        System.out.println( rs.reverseStr("Zbcdefg") );
    }
}

import java.util.Arrays;
import java.util.Collections;

public class ReverseStr {
    public String reverseStr(String str){
        String[] array = str.split("");
        Arrays.sort(array,  Collections.reverseOrder());

        return String.join("", array);
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        ReverseStr rs = new ReverseStr();
        System.out.println( rs.reverseStr("Zbcdefg") );
    }
}