[자료구조와 알고리즘] #1. 배열

프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?'를 학습하며 정리한 내용입니다. 

선형배열 

문제1. 정렬된 리스트에 원소 삽입하기 

문제 : 오름차순으로 정렬된 리스트에 x가 주어졌을 때 순서에 맞게 해당 x 삽입하기 

def solution(L, x):
    answer = []
    
    if max(L) < x:       #리스트에 존재하는 모든 원소보다 x가 클 경우 끝에 바로 삽입 
        L.append(x)
    else:
        
        for i in range(len(L)):  #리스트 순환하며 x와 같거나 큰 원소 위치i에 삽입 
        
            if L[i] >= x:
                L.insert(i,x)
                break
           
    
    answer = L
    
    return answer

 

문제2. 리스트에서 원소 찾아내기 

문제 : 리스트 L에서 원소 x가 발견될 경우 해당하는 인덱스를 구해서 인덱스로 이루어진 리스트를 반환 

def solution(L, x):
    
    answer=[]
    idx = []
        
    for idx in range(len(L)):
        
        if x in L :              #x가 리스트에 없을 경우 else -> -1 반환 
            if L[idx] == x:             #리스트에 원소가 x와 같을 경우 해당 인덱스 반환 
                answer.append(idx)                
            else : pass
        else :
            answer = [-1]
    
    return answer

다른사람 풀이 (enumerate)

def solution(L, x):
    if x in L:
        return [i for i, y in enumerate(L) if y == x]
    else:
        return [-1]

 

정렬과 탐색 

1. 정렬 

• 파이썬 내장함수 : sorted()
• 리스트 메서드 : .sort() 

2. 탐색

• 선형탐색(순차탐색) : 차례대로 반복문을 통해 훑어보는 것 
• 이진탐색 : 배열이 정렬되어 있는 경우, 가운데 원소와 찾는 값 비교하고 왼쪽/오른쪽에 있을 지 판단한 후 반으로 쪼개서 계속 이를 반복하는 것 

 

문제1. 이진탐색 

문제 : 리스트L, 원소 x 주어졌을 때 x와 같은 값을 가진 값의 인덱스를 리턴, 만약 없을 경우 -1 리턴 

 

def solution(L, x):
    answer = 0
    lower = 0          #첫번째 값의 인덱스 값 
    upper = len(L)-1   #마지막 값의 인덱스값 
    
    while lower <= upper :    #upper>lower가 되는 경우 해당 값이 리스트에 없음 
        middle = (lower + upper)//2   

        if L[middle] == x:
            answer = middle 
            break 
        elif L[middle] >x:      #중간 값이 x보다 큰 경우 > 왼쪽애들만 남기기 
            upper = middle-1    #마지막값은 Middle 값 앞의 값으로 
        else:                
            lower = middle+1    #중간값이 x보다 작은 경우 > mid 뒤의 값부터 오른쪽 남기기 
    else : answer = -1 
        
    
    return answer