이것이 코딩테스트다 - 1일차

지환·2023년 8월 1일
0

알고리즘-파이썬

목록 보기
1/6
post-thumbnail

출처 | https://www.youtube.com/watch?v=Mf0pYO8VAZk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81
https://m.hanbit.co.kr/store/books/book_view.html?p_code=B8945183661

해당 영상 및 내용을 정리했습니다. 문제 시 삭제하겠습니다.

리스트 컴프리핸션

array = [i for i in range(10)]
print(array)


결과 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


array = [i for i in range(20) if i % 2 == 1]

print(array)

결과 
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]



array = [i * i for i in range(1,10)]

print(array)

결과 
[1, 4, 9, 16, 25, 36, 49, 64, 81]

  • i라는 변수의 값을 차례대로 리스트의 원소로써 리스트에 담는다.

  • 리스트 컴프리핸션은 2차원 리스트를 초기화할 때 효과적으로 사용 가능하다.

  • 특히 N x M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 유용하다.
    ex) 좋은 예시는 -> array = [[0] + n for __ in range(n)]

  • 위 코드는 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식된다.

리스트 컴프리헨션(good)

good 예시

n = 5
m = 4
array = [[0] * m for _ in range(n)]
print(array)

결과 
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

bad 예시

n = 5
m = 4
array = [[0] * m] * n
print(array)


array[1][1] = 5
print(array)

결과 

[[0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0]]
  • 하나의 객체로 인식해서 한 줄이 바뀌어 버린다. 잘못된 방법중 하나다.

파이썬에선 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 사용한다.

문자열 자료형

  • 문자열 변수를 초기화 할 떄는 큰 따옴표나 작은 따옴표를 이용한다.
  • 문자열 안에 큰 따옴표나 작은 따옴표가 포함되어야 하는 경우야 있다.
    • 전체 문자열을 큰 따옴표로 구성하는 경우, 내부적으로 작은따옴표를 포함할 수 있다.
    • 전체 문자열을 작은따옴표로 구성하는 경우, 내부적으로 큰따옴표를 포함가능하다.
    • 혹은 백슬래시를 사용하면, 큰따옴표나 작은따옴표를 원하는 만큼 포함시킬 수 있다.

문자열 연산

  • 문자열 변수에 덧셈(+)을 이용하면 문자열이 더해져서 연결이 된다.

  • 문자열 변수를 특정한 양의 정수와 곱하는 경우, 문자열이 그 값만큼 여러 번 더해진다.

  • 문자열에 대해서도 마찬가지로 인덱싱과 슬라이싱을 이용할 수 있다.
    - 다만 문자열은 특정 인덱스의 값을 변경할 수 없다.

a = "Hello"
b = "world"


print(a + " " + b)

a = "String"
print(a * 3)


a = "ABCDEF"
print(a[2:5])

[결과]

Hello world
StringStringString
CDE

튜플

  • 튜플은 리스트에 비해 상대적으로 공간 효율적이다.

  • 튜플은 한 번 선언된 값을 변경할 수 없다.

  • 리스트는 대괄호([])를 사용하지만, 튜플은 소괄호(())를 이용한다.

  • 서로 다른 성질의 데이터를 묶어서 관리해야 될 때
    - 최단 경로 알고리즘에서는 (비용,노드 번호)의 형태로 튜플 자료형을 자주 사용한다,

  • 데이터의 나열을 해싱의 키 값으로 사용해야 할 떄

  • 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다.

  • 리스트보다 메모리를 효율적으로 사용해야 할 떄

사전자료형

  • 사전 자료형은 키와 값의 상을 데이터로 가지는 자료형이다.
    - 앞서 다루었던 리스트나 튜플이 값을 순차적으로 저장하는 것과는 대비된다.

  • 사전 자료형은 키와 값이 쌍을 데이터로 가지며, 원하는 변경 불가능한 자료형을 키로 사용 할 수 있다.

  • 파이선의 사전 자료형은 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다. 

date = dict()
date['사과'] = 'Apple'
date['바나나'] = 'Banana'
date['코코넛'] = 'Coconut'


print(date)

if '바나나' in date:
    print("바나나를 키로 가지는 데이터가 존재합니다.")

  • 사전 자료형에선느 키와 값을 별도로 뽑아내기 위한 메서드를 지원한다.

  • 키 데이터만 뽑아서 리스트로 이용할 땐 keys()함수를 이용한다.

  • 값 데이터만을 뽑아서 리스트로 이용할 때는 values() 함수 를 이용한다. 

date = dict()
date['사과'] = 'Apple'
date['바나나'] = 'Banana'
date['코코넛'] = 'Coconut'


key_list = date.keys()

value_list = date.values()

print(key_list)
print(value_list)

for key in key_list:
    print(date[key])
    
 
 
결과
 
dict_keys(['사과', '바나나', '코코넛'])
dict_values(['Apple', 'Banana', 'Coconut'])
Apple
Banana
Coconut

집합자료형

data = set([1,1,2,3,4,4,5])
print(data)

결과 

{1, 2, 3, 4, 5}

  • 중복 제거한다.

  • 합집합 : 집합 A에 속하거나 b에 속하는 원소로 이루어진 집합 (A U B)

  • 교집합 : 집합 A에도 속하고 B에도 속한 원소로 이루어진 집합

  • 차집합 : 집합 A의 원소 중에서 B에 속하지 않는 원소들로 이루어진 집합(A-B)

표준입출력

  • input() 함수는 한줄의 문자열을 입력 받는 함수다.
  • map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용한다.
  • 예시1) 공백을 기준으로 구분된 데이터를 입력 받을 때 다음과 같이 사용한다.
    - list(map(int, input().split()))
  • 예시2) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면 단순히 다음과 같이 사용한다.
    - a,b,c = map(int, input().split())
n = int(input())
data = input().split()

print(n)
print(data)

결과 
5
1 2 3 4 5
5
['1', '2', '3', '4', '5']

map함수로 출력하게 된다면 

n = int(input())
data = list(map(int,input().split()))

print(n)
print(data)


4
1 2 3 4
4
[1, 2, 3, 4]

변수의 개수가 정해져 있을 때

a,b,c = map(int, input().split())

print(a, b, c)

1 2 3
1 2 3
  • 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우가 있다.
  • 파이썬의 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 이용한다.
    - 단 입력 후 엔터(Enter)가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용한다.
  • print()는 기본적으로 출력 이후에 줄 바꿈을 수행한다. 줄 바꿈을 원하지 않는 경우 'end' 속성을 이용할 수 있다.
a = 1
b = 2

print(a,b)
print(7, end =" ")
print(9, end = " ")


answer = 8

print("정답은" + str(answer) + "입니다.")

결과

1 2 < 줄바꿈 실행됐음
7 9 정답은8입니다.

f-string 예제

  • 파이썬 3.6부터 사용가능하며, 문자열 앞에 접두사 'f'를 붙여 사용한다.

  • 중괄호 안에 변수명을 기입하며 간단히 문자열과 정수를 함께 넣을 수 있다.

answer = 8
print(f"정답은 {answer}입니다."}

결과 
정답은 8입니다.

조건문

반복문

for문

  • for문에서 연속적인 값을 차례대로 순회할 때는 range()를 주로 사용한다.
    - 이때 range(시작 값, 끝 값 + 1) 형태로 사용한다.
    • 인자를 하나만 넣으면 자동으로 시작 값은 0이 된다.
result = 0

# 1~10까지의 모든 값을 순회한다.
for i in range(1, 11):
    result += i
    
    
print(result)

결과 
55
  • 반복문에서 남은 코드의 실행으 건너뛰고, 다음 반복을 진행하고자 할 때 continue를 사용한다.
  • 즉시 탈출 할 땐 braek를 작성한다.

예제1) 점수가 85점 넘으면 합격

scores = [72, 95, 82, 99, 87]


for i in range(5):
    if scores[i] >= 85:
        print(i+1, "번 학생은 합격이다")
        
        
2 번 학생은 합격이다
4 번 학생은 합격이다
5 번 학생은 합격이다

2) 특정 번호의 학생은 제외하기

scores = [72, 95, 82, 99, 87]
cheating_list = {3,4}


for i in range(5):
    if i+1 in cheating_list:
        continue
    
    if scores[i] >= 85:
        print(i + 1, "번 학생은 합격이다")
        
2 번 학생은 합격이다
5 번 학생은 합격이다

그리디 알고리즘

  • 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
  • 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
  • 그리디 해법은 정당성 분석이 중요하다.

거스름돈 문제

문제)

카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정하자. 손님에게 거슬러 주어야 할 돈이 N원일 떄 거슬러 주어야 할 동전의 최소 개수를 구하라. 단) 거슬러 줘야 할 돈 N은 항상 10의 배수다.

key)

  1. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면된다.
  2. N원을 거슬러 줘야 할 떄, 가장 먼저 500원으로 거슬러 줄 수 있으 만큼 거슬러 준다.
  3. 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러준다.

N = 1,260일 때의 예시

n = 1260
count = 0
coin = [500, 100, 50, 10]


for c in coin:
    count += n // c # 1260 // 500 --> 몫 갑을 count에 저장하고 n값을 나눈 c값을 
    n %= c
    
print(count)

결과 
6
profile
지환
아는만큼보인다.
다음 포스트

이코테 - 2일차 (그리디)

0개의 댓글