본문 바로가기
Python

[Python] python 자료구조 - 문제 풀면서 배우기

by 잼들리 2022. 11. 26.

Python은 tuple, list, dictionary 등 많은 자료구조를 가지고 있습니다.

저 또한 c++, java를 쓰다가 python을 쓰니 신세계가 열린 느낌이었는데요 :)

편리한 python을 이용하여 "python 다운 코드"를 짜는 방법을 배워봅시다.

  • List = [대괄호]
    • 리스트 구조는 C나 Java의 Array(배열) 구조와 비슷하다고 할 수 있습니다. ex) [1, 2, 3] 
# 1~100 사이의 7의 배수
a = list(range(7, 101, 7))
# -> 

# 리스트 a의 인덱스 4~7 까지 출력
print(a[4:8]) -> # [35, 42, 49, 56]

# 리스트 a의 끝에서 3번째 값 출력
print(a[-3]) # -> 84

# 리스트 a의 길이
print(len(a)) # -> 14

 

  • Tuple = (소괄호)
    • 리스트 처럼 배열되어 있지만, 원소의 값을 수정할 수는 없습니다. ex) (1, 2, 3) 
a = (1, 2, 3)
a # (1, 2, 3)
b = 3, 4, 5 # (3, 4, 5)
c = ('a', 'b', ('ab', 'cd')) # ('a', 'b', ('ab', 'cd'))

 

  • Dictionary = {중괄호}
    • key와 value의 쌍으로 이루어진 자료형입니다. key:value  ex) {1 : 'a', 2 : 'b', 3 : 'c'} 
d = {'v1': [1,2,3], 'v2': {'a':23, 'b':[4,5]}}

print(d['v1']) # -> [1, 2, 3]
print(d['v2']['a']) # -> 23
print(d['v2']['b'][1]) # -> 5
# key='newKey', value=tuple(1,2)를 d에 추가
d['newKey'] = (1,2)

🔷 리스트 (list)

1. 리스트 원소의 최댓값 구하기

def max_of(a:list):
    maximum = a[0]
    for i in range(1, len(a)):
        if(a[i] > maximum):
            maximum = a[i]
		return maximum

t = (4, 7, 5.6, 2, 3.14, 1)
s = "string"
a = ['DTS', 'AAC', 'FLAC']

print(f'{max_of(t)}')
print(f'{max_of(s)}')
print(f'{max_of(a)}')

[mini 실습1] 리스트 원소의 최솟값 구하기

def min_of(a:list):
    minimun = a[0]
    
    for i in range(1, len(a)):
        if(minimun > a[i]):
            minimun = a[i]
            
    return minimun

t = (4, 7, 5.6, 2, 3.14, 1)
s = "string"
a = ['DTS', 'AAC', 'FLAC']

print(f'{min_of(t)}')
print(f'{min_of(s)}')
print(f'{min_of(a)}')

2. 입력한 리스트에서 최댓값 구하기

  • for문
def max_of(a:list):
    maximum = a[0]
    for i in range(1, len(a)):
        if(a[i] > maximum):
            maximum = a[i]
    return maximum
    
print('리스트의 최댓값을 구합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}] 값을 입력하세요.: '))
    
print(f'최댓값은 {max_of(x)} 입니다.')
  • while문
def max_of(a:list):
    maximum = a[0]
    for i in range(1, len(a)):
        if(a[i] > maximum):
            maximum = a[i]
    return maximum

print('리스트의 최댓값을 구합니다.')
print('주의: "End"를 입력하면 원소 입력을 종료합니다.')
i = 0
x = []

while True:
    s = input(f'x[{i}]값을 입력하세요.: ')
    if s == 'End':
        break
    x.append(int(s))
    i += 1
    
print(f'최댓값은 {max_of(x)}입니다.')

3. 리스트의 모든 원소 스캔하기

  • for문
# 원소 수 파악

x = ['John', 'George', 'Paul', 'Ringo']

for i in range(len(x)):
    print(f'x[{i}] = {x[i]}')
  • enumerate함수 → 엄청 많이 씁니다!! 기억해두시면 좋아요.⭐⭐
# enumerate 함수로 스캔

x = ['John', 'George', 'Paul', 'Ringo']

for i, name in enumerate(x):
    print(f'x[{i}] = {name}')

  • 인덱스 값 사용하지 않고 출력 → 이것도 엄청 많이 씁니다!! 꼭 기억해두세요.⭐⭐⭐⭐
# 인덱스 값을 사용하지 않음

x = ['John', 'George', 'Paul', 'Ringo']

for i in x:
    print(i)

4. 원소를 역순으로 정렬하기 (입력의 역순)

def reverse_list(a:list):
    n = len(a)
    for i in range(n//2):
        a[i], a[n-i-1] = a[n-i-1], a[i]

a = [2, 5, 1, 3, 9, 6, 7]
reverse_list(a)
print(a)

[mini 실습2] 리스트를 입력받고, 역순으로 정렬하기

def reverse_list(a: list):
    n = len(a)
    for i in range(n//2):
        a[i], a[n-i-1] = a[n-i-1], a[i]

print('리스트를 역순으로 출력합니다.')
n = int(input('원소 수를 입력하세요.: '))
arr = [None] * n

for i in range(n):
    arr[i] = int(input(f'x[{i}] 값을 입력하세요.: '))

print('리스트를 역순으로 출력합니다.')
reverse_list(arr)
print(arr)

🔷 검색 알고리즘

: 원하는 값을 가진 원소를 찾아내는 알고리즘

  • 선형 검색 (linear search) : 원하는 값을 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
    • 검색할 값과 같은 원소를 찾은 경우 → 검색 성공
    • 검색할 값과 같은 원소를 찾지 못하고, 리스트의 맨 끝에 도달한 경우 → 검색 실패

1. 선형검색 (while)

# while 문으로 작성한 선형 검색 알고리즘
def seq_search_while(a, key):
    i = 0
    
    while True:
        if i == len(a):
            return -1
        if a[i] == key:
            return i
        i += 1

a = [2, 5, 1, 3, 9, 6, 7]

index = seq_search_while(a, 3)

if index == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'검색값은 a[{index}]에 있습니다.')

2. 선형검색 (for)

# for 문으로 작성한 선형 검색 알고리즘
def seq_search_for(a, key):
    
    for i in range(len(a)):
        if a[i] == key:
            return i
    return -1
        
a = [2, 5, 1, 3, 9, 6, 7]

index = seq_search_for(a, 3)

if index == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'검색값은 a[{index}]에 있습니다.')

3. 선형검색 - 보초법 (while)

보초법 : key값을 리스트 맨 끝에 붙이고(보초값) 찾아진 key 값이 보초값 위치라면 → 검색 실패로 간주함

def seq_search_sentinel(b, key):
    a = b.copy()
    a.append(key)
    
    i=0
    while True:
        if a[i] == key:
            break
        i += 1
    
    return -1 if i == len(b) else i

a = [2, 5, 1, 3, 9, 6, 7]

index = seq_search_sentinel(a, 10)

if index == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'검색값은 a[{index}]에 있습니다.')

[mini 실습3] 선형검색 while문과 보초법 사용 시, if문의 실행 횟수

# while 문으로 작성한 선형 검색 알고리즘
def seq_search_while(a, key):
    i = 0
    count = 0
    while True:
        count+=1
        if i == len(a):
            return (-1, count)
        
        count+=1
        if a[i] == key:
            return (i, count)
        
        i += 1

# 보초법(while)으로 작성한 선형 검색 알고리즘
def seq_search_sentinel(b, key):
    a = b.copy()
    a.append(key)
    
    i = 0
    count = 0
    while True:
        count+=1
        if a[i] == key:
            break
        i += 1
    
    count+=1
    return (-1, count) if i == len(b) else (i, count)
    

a = [2, 5, 1, 3, 9, 6, 7]
index0, count0 = seq_search_while(a, 7)
index1, count1 = seq_search_sentinel(a, 7)

if index0 == -1 and index1 == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'선형검색 While 문에서 검색값은 a[{index0}]에 있습니다.')
    print(f'선형검색 보초법에서 검색값은 a[{index1}]에 있습니다.')
    print(f'선형검색 While 문에서 if문은 {count0}만큼 실행되었습니다.')
    print(f'선형검색 보초법에서 if문은 {count1}만큼 실행되었습니다.')

  • 이진 검색 (Binary search) : 중앙 인덱스 값과 비교하여 key 값을 찾는 방식
    • 이진 검색은 리스트이 데이터가 오름차순이나 내림차순으로 정렬되어 있어야 적용 가능
    • 이진 검색은 선형 검색에 비해 빠르게 검색 값을 찾을 수 있음

1. 이진검색

def binary_search(a:list, key):
    start = 0
    end = len(a)-1
    
    while start<=end:
        index = (start+end)//2
        if(a[index] == key): # 검색 성공
            return index
        elif(a[index] < key):
            start = index+1
        elif(a[index] > key):
            end = index-1
            
    return -1
    
a = [5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95]

index = binary_search(a, 31)

if index == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'검색값은 a[{index}]에 있습니다.')

🔶 실습문제

▶ [실습문제1] 2~1000 사이의 소수를 찾고 리스트로 출력하기

# 2~1000 사이의 수 중에서 소수를 리스트에 입력하고 출력하여라.

prime = []

for i in range(2, 1001):
    isPrime = True
    for j in range(2, i):
        if(i % j == 0):
            isPrime = False
            break
    if(isPrime == True):
        prime.append(i)

print(prime)

▶[실습문제2] 리스트를 입력받고, 역순으로 정렬하여 출력하기

# 리스트를 사용자로부터 입력받아서 역순으로 정렬하여 리스트의 원소를 출력하여라.
# 원소 수를 미리 묻지 말고 코드가 실행될 수 있도록하라.

def reverse_list(a:list):
    n = len(a)
    
    for i in range(n//2):
        a[i], a[n-i-1] = a[n-i-1], a[i]

print('리스트를 역순으로 정렬하여 출력합니다.')
print('주의: "End"를 입력하면 원소 입력을 종료합니다.')
arr = []
i = 0
while True:
    s = input(f'arr[{i}]를 입력하세요.: ')
    
    if(s == 'End'): break
    arr.append(int(s))
    i+=1

reverse_list(arr)
print(arr)

▶[실습문제3] 리스트와 검색할 값을 입력받고, 검색값이 있는 인덱스 출력하기

# 리스트와 검색할 값을 사용자로부터 입력받아서 검색값이 있는 인덱스를 출력하라.
# 검색방안은 어떤 방안을 사용하여도 됩니다.

def binary_search(a:list, key):
    start = 0
    end = len(a)-1
    
    while start<=end:
        index = (start+end)//2
        if(a[index] == key):
            return index
        elif(a[index] < key):
            start = index+1
        elif(a[index] > key):
            end = index-1
    
    return -1

print('리스트와 검색할 값을 입력받아 검색값이 있는 인덱스를 출력합니다.')
print('주의: "End"를 입력하면 원소 입력을 종료합니다.')
arr = []
i = 0

while True:
    s = input(f'arr[{i}]값을 입력하세요.: ')
    
    if(s == 'End'): break
    arr.append(int(s))
    i += 1

key = int(input('검색할 값을 입력하세요.: '))
index = binary_search(arr, key)
print(f'검색값 {key}는 a[{index}]에 있습니다.')

▶[실습문제4] 리스트를 입력받고, 최댓값과 최댓값이 있는 인덱스 출력하기

# 리스트를 사용자로부터 입력받아서 최댓값과 최댓값이 있는 인덱스를 출력하라.

def find_max(a:list):
    maximum = a[0]
    max_index = 0
    for i in range(1, len(a)):
        if(maximum < a[i]):
            maximum = a[i]
            max_index = i
            
    return(maximum, max_index)

print('리스트와 검색할 값을 입력받아 검색값이 있는 인덱스를 출력합니다.')
print('주의: "End"를 입력하면 원소 입력을 종료합니다.')
arr = []
i = 0

while True:
    s = input(f'arr[{i}]값을 입력하세요.: ')
    
    if(s == 'End'): break
    arr.append(int(s))
    i += 1

maximum, max_index = find_max(arr)
print(f'최대값은 {maximum}이고 a[{max_index}]에 있습니다.')

▶[실습문제5] X보다 작은 수

# https://www.acmicpc.net/problem/10871
# X보다 작은 수

N, X = map(int, input().split())
A = list(map(int, input().split()))

for i in A:
    if(i < X): print(i, end = " ")

▶[실습문제6] 로또의 최고 순위와 최저 순위

# https://school.programmers.co.kr/learn/courses/30/lessons/77484
# 로또의 최고 순위와 최저 순위

def solution(lottos, win_nums):
    lottos.sort()
    win_nums.sort()

    correct = 0
    count = 0
    for i in lottos:
        if(i==0): count+=1
        for j in win_nums:
            if(j==i): correct+=1
            elif(j>i): break

    high = 7-(correct+count)
    low = 7-(correct)

    if(high>=7): high = 6
    if(low>=7): low = 6
    answer = [high, low]
    return answer

lottos = [44, 1, 0, 0, 31, 25]
win_nums = [31, 10, 45, 1, 6, 19]
answer = solution(lottos, win_nums)
print(answer)

▶[실습문제7] 없는 숫자 더하기

# https://school.programmers.co.kr/learn/courses/30/lessons/86051
# 없는 숫자 더하기

def solution(numbers):
    sum = 0
    for i in numbers:
        sum+=i
        
    answer = (9*10)//2 - sum
    return answer

numbers = [1,2,3,4,6,7,8,0]
answer = solution(numbers)
print(answer)

▶[실습문제8] 부품 찾기

def solution(store, customer):
    answer = []
    for c in customer:
        flag = False
        for s in store:
            if(c==s):
                flag = True
                break
        if(flag): answer.append('yes')
        else: answer.append('no')
            
    return answer

store = [1,2,3,7,8]
customer = [1,5,8,4,6]
answer = solution(store, customer)
print(answer)

▶[실습문제9] 여러 수의 최소공배수 구하기

def LCM(a, b): # 최소공배수 구하는 함수
    answer = a*b
    for i in range(min(a,b), a*b+1):
        if(i%a==0 and i%b==0):
            answer = i
            break
    return answer

def solution(arr): # solution
    lcm = arr[0]
    for i in range(1, len(arr)):
        lcm = LCM(lcm, arr[i])

    answer = lcm
    return answer

arr = [2,6,8,14]
answer = solution(arr)
print(answer)

▶[실습문제10] 최고의 집합 찾기

def solution(n, s):
    answer = []
    
    max = -1 # 각 원소의 곱 중 max값
    for i in range(1, s//2+1):
        set = [i, s-i] # 합이 s가 되는 원소들
        if(max < i*(s-i)):
            max = i*(s-i)
            answer = set
    
    if(max==-1): answer.append(-1)
    return answer

n = 2
s = 9
answer = solution(n, s)
print(answer)

▶[실습문제11] 제일 작은 수 제거하기

# https://school.programmers.co.kr/learn/courses/30/lessons/12935
# 제일 작은 수 제거하기

def solution(arr):
    min = arr[0]
    min_index = 0
    for i in range(1, len(arr)):
        if(min > arr[i]):
            min = arr[i]
            min_index = i
    
    answer = arr[0:min_index]+arr[min_index+1:len(arr)]
    if(len(answer)==0):
        answer.append(-1)
    
    return answer
    

arr = [10]
answer = solution(arr)
print(answer)

▶[실습문제12] 같은 숫자는 싫어

# https://school.programmers.co.kr/learn/courses/30/lessons/12906
# 같은 숫자는 싫어

def solution(arr):
    answer = []
    
    prev = arr[0]
    answer.append(arr[0])
    for i in range(1, len(arr)):
        if(prev==arr[i]):
            continue
        else:
            prev = arr[i]
            answer.append(arr[i])
        
    return answer

arr = [1,1,3,3,0,1,1]
# arr = [4,4,4,3,3]
answer = solution(arr)
print(answer)

저작자표시 (새창열림)

'Python' 카테고리의 다른 글

[Python] python 라이브러리 - numpy 총 정리  (0) 2022.11.26
[Python] python 기초 - 문제 풀면서 배우기  (0) 2022.11.26

관련글

댓글

티스토리툴바