8_3 - syh39/ProblemSolving GitHub Wiki

리스트에서 원소 찾아내기

출처: (https://school.programmers.co.kr/learn/courses/57/lessons/13774)

난이도 : 기분

유형 : 선형탐색

풀이 방법

def solution(L, x):
    answer = []
    a = 5
    if x in L:
        while True:
            if x not in L:
                break
            
            else:
                a = L.index(x)
                L = L[a+1:]
                if len(answer) !=0 :
                    a = a + answer[len(answer)-1] + 1
                answer.append(a)
    else : 
        answer = [-1]
    return answer

다른 사람의 풀이 방법:

def solution(L, x):
    idx = []
    for i in range(len(L)):
        if L[i] == x:
            idx.append(i)
    if len(idx) == 0:
        idx.append(-1)
    return idx

결론

설명이 답이 아닐 수 있다 문제의 해결책을 객관적으로 찾는게 중요하다

이진탐색 구현해보기

출처: (https://school.programmers.co.kr/learn/courses/57/lessons/13775)

난이도 : 기본

유형 : 이진탐색

풀이 방법

def solution(L, x):
    lo = 0
    hi = len(L)

    while lo<hi:
        mid = (lo + hi) // 2
        if x == L[mid]:
            return mid
        elif x > L[mid]:
            lo = mid + 1
        elif x < L[mid]:
            hi = mid - 1
        
    return -1

다른 사람의 풀이 방법:

결론

효율성 문제에서 한개가 틀리는데 뭔지 도통 모르겠다

피보나치 순열 구현하기

출처: (https://school.programmers.co.kr/learn/courses/57/lessons/13776)

난이도 : 기본

유형 : 재귀

풀이 방법

def solution(x):
    return recursive(x)

def recursive(n):
    if n == 0 or n == 1:
        return n
    else:
        return recursive(n-1) + recursive(n-2)

def iterative(n):
    list = []
    for i in range(0, n+1):
        if i == 0 or i == 1:
            list.append(i)
        else:
            list.append(list[i-2] + list[i-1])
    return list[n]

다른 사람의 풀이 방법:

def solution(x):
    answer = 0
    fa = 0
    fb = 1
    while x > 0:
        x -= 1
        fa, fb = fb, fa+fb
        answer = fa
    return answer

결론

굳