다이나믹 프로그래밍이란 한 번 계산하여 해결한 문제를 메모리에 저장하여 다음에 같은 문제를 만났을때 계산하지 않고 메모리에 저장한 값을 가져와 답을 반환하여 효율성을 높이는 방식이다.

 

해당 다이나믹 프로그래밍에서의 다이나믹은 다른 상황에서 쓰이는 의미가 담기진 않았다.

 

다이나믹 프로그래밍(DP)의 두 가지 방법

- 탑다운

하향식, 구현 과정에서 재귀함수를 사용한다. 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출

- 바텀업

상향식, 구현 과정에서 반복문를 사용한다. 아래쪽부터 작은 문제를 하나씩 해결해나가며 다음의 문제까지 차례로 해결 

 

위 처럼 두 가지의 방법을 다이나믹 프로그래밍을 구현할 수 있다.

 

DP를 이용할 수 있는 조건

1. 최적 부분 조건

- 작은 문제들의 답을 모아 큰 문제를 해결할 수 있어야 한다.

2. 중복되는 부분 문제

- 동일만 문제를 반복적으로 해결하는 상황

 

DP로 효과적으로 계산할 수 있는 문제들 

 

[피보나치 수열]

앞 두 수의 합으로 이루어진 수열

이러한 인접한 항들 사이의 관계식으로 표현한 것을 점화식이라고 하는데 피보나치 수열을 점화식은 다음과 같다

피보나치 수열이 계산되는 과정을 표현해보면

 

이렇게 표현된다.

코드로 작성해보자

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)

 

하지만 단순 재귀함수로 피보나치 수열을 해결하면 아래 그림과 같이 되어 지수 시간 복잡도를 가지게 되기 때문에 더 효율적인 방법이 필요하다.

>>  중복되는 부분문제라고 볼 수 있다.

그리고 특정 값을 구할려고 하면 그 값이 작은 문제로 분해되는데 이는 최적 부분 구조이기 때문에 

DP를 이용해 해결할 수 있다.

 

먼저 탑다운 방식인 메모이제이션으로 구현해보자

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.

- 같은 문제를 다시 호출할 경우 메모했던 결과를 가지고 온다.

- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.

 

# f(99)를 구하고 싶다

dp = [0]*100

def fibo(x):
	# 종료조건
    if x == 1 or x == 2:
    	return 1
    # 계산한 적이 있는 문제라면 저장한 값 반환
    if dp[x] != 0:
    	return dp[x]
    # 계산한 적이 없는 문제라면 계산하여 dp 테이블에 저장
    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]
    
print(f(99))

재귀함수를 사용하는 것을 확인할 수 있다.

 

 

바텀업 방식으로도 DP를 구현해보자

dp = [0]*100

dp[1] = 1
dp[2] = 1
n = 99

for i in rnage(3, n + 1):
	dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

반복문을 사용하는 것을 확인할 수 있다.

 

메모이제이션 동작 분석

 위와 같이 계산이 되기 때문에 효율적인 것을 알 수 있다 또한 호출된 것만 남긴다면 

이렇게 함수가 호출된다.

 

피보나치 수열로 다이나믹 프로그래밍의 기초 개념을 알아봤다. 다이나믹 프로그래밍은 거의 알려진 문제에서 나오는 경우가 많기 때문에 문제를 많이 접하고 해결하며 익숙해 지는 것이 중요한것 같다

 

푸는 과정은 일단 다 풀어보고 이해하게 된 점 정리와 사용된 자료구조를 정리하는 방식으로 진행할 것이다.

 


폰켓몬 문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

  1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
  2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
  3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
  4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
  5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
  6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
  • nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
  • nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
  • 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
  • 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예numsresult
[3,1,2,3] 2
[3,3,3,2,2,4] 3
[3,3,3,2,2,2] 2
입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

 

문제 풀이

풀이1

def solution(nums):
    setNums = list(set(nums))
    countMonster = len(setNums)
    
    if countMonster <= (len(nums)/2):
        return countMonster
    elif countMonster > (len(nums)/2):
        return (len(nums)/2)

 

처음에는 뽑는 경우의 수를 모두 가져오고 종류를 확인할려고 했는데, 코드를 작성하는 과정에서 너무 복잡하다는 생각에 다시 문제를 확인했다. 결론적으로 뽑을 수 있는 폰켓몬의 수는 정해져 있으므로 그 이상으로 여러 종류의 폰켓몬을 뽑을 순 없다.
따라서 뽑을 수 있는 수보다 종류가 적거나 같으면 가장 많이 뽑는 수는 뽑을 수 있는 수 그 자체가 될것이고,

뽑을 수 있는 수보다 종류가 적다면 무조건 파라미터로 받는 나열에 있는 종류의 수가 가장 많이 뽑은 종류의 수가 될것이다.

이 생각으로 위와 같이 풀었다.

 

풀이 2

근데 이는 더 간다한게 min 내장 함수를 통해 풀 수 있는데 그 풀이는 다음과 같다.

def solution(nums):
	return min( len(set(nums)), (len(nums)/2) )

 

위에서 작성한 코드와 똑같은 기능을 하지만 min을 이용에 훨씬 간결하게 짤 수 있다.


완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예participantcompletionreturn
["leo", "kiki", "eden"] ["eden", "kiki"] "leo"
["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko"
["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"
입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

문제 풀이

그 전 포스팅에서 적긴 했는데, 문제를 풀면서 느낀 것이 먼저 문제의 의도를 정확히 파악하고 머리로 알고리즘을 설계하는 것이 더 중요한 것 같다.

 

처음에는 set 함수를 이용해서 풀려고 했는데 set을 이용하면 동명이인을 잡아낼 수 없어 문제가 됐다. 그 다음에는 참여자 명단이랑 완주자 명단을 비교하며 참여자 명단에서 완주자 명단에 있는 사람을 없애려고 했는데, 이는 설정한 len(참여자명단)이 실시간으로 바뀌기 때문에 for문에서 에러가 나 실행하지 못했다.

 

그래서 hash를 이용해 풀었다.

주어지는 선수의 수는 100000이하기 때문에 O(NlogN) 이하의 시간으로 풀어야한다.

 

풀이 1

특정 문자열은 고유한 해시값으로 변환되기 때문에 이를 이용했다.

참여자 명단의 이름들을 해시로 변환해 더하고, 똑같이 완주자 명단의 이름들을 해시로 변환해 더했다.

그리고 빼면 특정 해시값이 나오고 그 해시값에 해당하는 이름을 가져오면 완주하지 못한 사람이다.

   

틀린 처음 풀이

def solution(participant, completion):
    mydict = dict()
    
    for i in participant:
        mydict[hash(i)] = i
    
    sumPartKey = sum(mydict.keys())
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

이 방식은 오류가 났었다. 그 이유는 반복문으로 딕셔너리를 만들때 동명이인은 같은 키로 들어가기 때문에 위에서 만들어진 mydict은 동명이인을 받아도 하나로 넣어버린다. 그렇기 때문에 sumPartKey에서 sumComp를 빼면 해시값이 아닌 숫자가 나와 동명이인을 입력 받았을 때는 오류가 발생한다.

 

맞는 풀이

def solution(participant, completion):
    mydict = dict()
    sumPartKey = 0
    for i in participant:
        mydict[hash(i)] = i
        sumPartKey += hash(i)
        
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

딕셔너리를 만들 때, 넣는 값들을 바로바로 더해줘서 위에서 있었던 문제를 해결할 수 있다.

 

풀이 2

collection 모듈의 Counter를 이용한 풀이 방식이다. Counter을 이용하면 배열에 각 원소들의 갯수가 몇개인지 뽑아주는데 참여자 명단과 완주자 명단에 적용을 하고 빼주면 완주하지 못한 참여자를 구할 수 있다. 

딕셔너리 끼리는 뺄 수 없지만 Counter를 통해 객체로 바뀌었기 때문에 빼는 것이 가능하다.

import collections

def solution(participant, completion):
	answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys()[0])

전화번호 목록 문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

  • 구조대 : 119
  • 박준영 : 97 674 223
  • 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
  • phone_book의 길이는 1 이상 1,000,000 이하입니다.
    • 각 전화번호의 길이는 1 이상 20 이하입니다.
    • 같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제phone_bookreturn
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false
입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

이 문제를 풀기 위해선 문자열 비교하는 것을 알아야한다.

  • 완전 일치 : == !=
  • 부분 일치 : in not in
  • 전방 일치 : startswith
  • 후방 일치 : endswith

위와 같이 비교를 할 수 있고 전방과 후방 일치는 문자열2. startswith / endswith (문자열1) 방식으로 사용하고 문자열1일 문자열2에 있는지 찾는 것이다.

 

그리고 정렬하는 기준에 대해 알아야한다. 배열의 원소가 정수형이나 실수형이라면 정렬의 기준의 숫자의 크기이지만 문자열인 경우는 제일 앞에 있는 문자를 기준으로 정렬한다. 제일 먼저 오는 문자 순으로 정렬한 후의 그 뒤에 오는 문자를 기준으로 다시 정렬한다. 예를 들어 133이 1222보다 작지만 1 다음으로 오는 2가 3보다 작기 때문에 ['133', '1222']를 sort하면 ['1222', '133']으로 정렬된다.

 

예를 하나 더 들어서 설명하자면,

[12, 134, 34, 456]에 sort()를 해주면 [12, 34, 134, 456]으로 정렬되고,

['12', '134', '34', '456']에 sort()를 해주면 다음과 같이 정렬한다. ['12', '134', '34', '456']

 

이러한 특성을 이용해 문제를 풀 수 있다.

 

파라미터로 오는 배열을 정렬하면 문자열 a가 그 다음에 오는 문자열 b에 포함되는지만 확인하면 되니까 먼저 배열을 정렬해준 뒤, 바로 옆에 있는 문자열끼리만 비교해주면 된다.

def solution(phone_book):
	answer = True
    phone_book.sort()
    
    for i in range (len(phone_book)-1):
    	if phone_book[i+1].startswith(phone_book[i]):
        	answer = False
            break
	retrun answer

 

이렇게 작성할 수 있다

 

|| 코딩 테스트를 위한 준비 ||

 

코딩 테스트를 볼 수 있는 사이트 >> 온라인 저지(프로그래모스, 백준 등등)

온라인 개발 환경 "리플릿" << 매우 유용하다

 

Replit: The software creation platform. IDE, AI, and Deployments

Run code live in your browser. Write and run code in 50+ languages online with Replit, a powerful IDE, compiler, & interpreter.

replit.com

 

 

알고리즘 성능 평가 - 알고리즘 문제를 알기 위해 알아야하는 개념

시간 복잡도 - 수행 시간 기준

공간 복잡도 - 메모리 사용향 기준

 

이들을 보통 빅오 표기법을 사용한다.

- 가장 빠르게 증가하는 항만을 고려한다.

- 즉 함수의 상한만을 나타낸다.

ex) 3N^3 + 3N^2 이면 복잡도는 O(N^3)이다.

    자세한건 아니지만 중첩을 기준으로 생각하면 편하다

        - 모든 이중for문이 O(N^2)인 것은 아니지만 대부분 O(N^2)이다. 

 

 

알고리즘 설계 Tip 

일반적으로 CPU 기반의 개인 컴퓨터에서 연산 횟수가 5억회 넘어가는 경우 

=> C언어 1-3초

=> Phthon 5-15초 (PyPy를 이용하면 더 빠르게 동작하기도 한다.)

정도의 시간이 소요된다.

 

요구사항에 따라 적절한 알고리즘 설계하기

알고리즘 문제는 시간제한이 걸려있기 때문에 고려해야한다.

시간제한이 1초인 문제를 만났을 때, 일반적으로 설계해야하는 기준으 다음과 같다.

- N의 범위가 500 => O(N^3) 인 알고리즘 설계

- N의 범위가 2,000 => O(N^2) 인 알고리즘 설계

- N의 범위가 100,000 => O(NlogN) 인 알고리즘 설계

- N의 범위가 10,000,000 => O(N) 인 알고리즘 설계

 

일반적인 알고리즘 문제 해결 과정

1. 지문 읽고 분석

2. 요구사항 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩


|| 파이썬의 자료형 ||

 

정수형

양의 정수, 음의 정수, 0

정수 변환 int(변수)

 

 

실수형

소수점 아래의 데이터를 포함하는 수 자료형

X.X라고 작성하면 실수로 인식함

ex)

a = 5. => 5.0

a = -.7 => -0.7

 

    지수 표현 방식

 

    유효숫자e지수 = 유효숫자 X 10^지수

    ex)  1e9 = 1 X 10^9

    - 보통 임의의 큰 수를 표현하기 위해 자주 사용

        - 최단 경로 알고리즘에서 도달할 수 없는 노드에 대하여 최단 거리를 무한으로 설정

            - 이때 가능한 최댓값이 10억 미만이라면 무한값으로 1e9(10억 < 1e9)를 사용할 수 있다

 

    실수형 더 알아보기

    실수형을 저장하기 위해 4바이트 혹은 8바이트의 고정된 크기의 메모리를 할당

    => 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 지님

    ex) a = 0.3+0.6 == 0.899999999

    이러한 한계를 극복하기 위해서 round()함수를 사용한다.

 

    round()함수

    round(특정숫자, 소수점 아래 어디서 반올림할건지)

 

 

수 자료형의 연산

나누기 / >> 나눠진 결과 실수

나머지 연산자 %

몫 연산자 //

거듭제곱 연산자 **

 

 

리스트 자료형

- 연결 리스트와 유사한 기능 

- C++ STL vector와도 기능적으로 유사

- 구조 : [  ,  , ...]

- 빈 배열 선언 : list() or []

- 원소 접근할 때는 인덱스 값 괄호에 넣어서 접근

    - 이를 인덱싱이라고 한다.

슬라이싱 : 대괄호 안에 콜론을 넣어 시작 인덱스와 끝 인덱스를 설정할 수 있다.

 

 

 

리스트 컴프리헨션

대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화할 수 있다.

a = [i for i in range(10)]
# => [0,1,2,3,4,5,6,7,8,9]

for문으로 하나씩 증가시키고 있는 i를 맨 앞의 i에 적어 배열의 원소로 넣는다.

 

조건문도 포함 가능하다

a = [i for i in range(20) if i%2==1]
# 20이하의 수 중에 홀수만 원소로 넣기

a = [i*i for i in range(1, 10)]
# 1에서 9까지 각각의 제곱근 원소롤 넣기

 

    nxm 크기의 2차원 배열 초기화 하기

a = [[0] * m for _ in range(n)]

 

※ 여기서 _ 는 for문에서 i를 사용할 필요없고 횟수 반복만 필요할 때 사용한다. ※

 

    리스트 관련 메소드

arr.append (원소) : 리스트에 원소 하나 삽입 || O(1)

arr.insert (삽입 위치, 삽입값) : 특정 위치에 특정 원소 삽입 || O(N)

arr.sort () : 원소 정렬 기본적으로 오름차순임 >> 내림차순은 .sort(reverse = True) || O(NlogN)

arr.reverse () :  리스트 원소 순서 뒤집기 || O(N)

arr.count(특정 값) : 배열 내의 특정값 갯수 반환 || O(N)

arr.remove(특정 값) : 배열 내 특정 값 제거 || O(N)

 

    리스트에서 특정 값을 가지는 원소 모두 제거

a = [0, 1, 2, 3, 4, 5]
remove = {2, 4}

result = [i for i in a if not in remove]
# [0, 1, 3, 5]

 

문자열 자료형

" "나 ' '로 표현

\로 " " 안에서 " "를 사용가능

ex) a = "my \"Love\"" => my "Love"

 

    문자열 연산

덧셈과 곱셉 가능

ex)

a + B => aB

A *  3 => AAA

인덱싱과 슬라이싱도 할 수 있다

단, 특정 인덱스의 값은 변경 불가하다.

 

튜플 자료형 

리스트와 비슷하지만 살짝 차이가 있다. 

인덱싱과 슬라이싱 가능

- 한번 선언된 값은 변경 불가하다

- ()로 표현한다

위의 특징 덕분에 리스트에 비해 상대적으로 공간 효율적이다.

 

    튜플을 사용하는 경우

- 서로 다른 성질의 데이터를 묶어서 관리해야할 때,

    - 최단 경로 알고리즘에서 (비용, 노드 번호)의 형태로 튜플 사용

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

    - 튜플은 변경이 불가능하기 때문에 키 값으로 사용 가능하다

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

 

 

사전 자료형

- 키와 값의 쌍을 데이터로 가지는 자료형 >> JS의 JSON 형식과 똑같다

     - 값을 순차적으로 저장했던 리스트와 튜플과는 차이가 있음 >> 키를 지정해 값을 넣을 수 있다.

-로 사용하는 것은 변경 불가능한 자료형이다.

- 해시 테이블을 사용하기 때문에 데이터 조회 및 수정에 있어서 O(1)의 시간에 처리하므로 효율적이다.

 

data = dict()
data["키값0"] = "aaa"
data["키값1"] = "aaaa"
data["키값2"] = "aaaa"

# {"키값0":"aaa", "키값1":"aaaa", "키값2":"aaaaa"}

 

키 혹은 값만 뽑고 싶을 때:

    data.keys() => 키들을 반환

    data.values() => 데이터들 반환

배열로 변환 해줘야한다.

 

집합 자료형

- 중복을 허용하지 않는다

- 순서가 없다

- 리스트나 문자열을 이용해 초기화할 수 있다

    - set() 함수 사용

    - {} 안에 , 로 구분하여 삽입하며 초기화 가능

- 데이터 조회와 수정 O(1) 시간에 처리

 

합집합 A | B

교집합 A & B

차집합 A - B

을 제공한다.

 

.add(원소) : 원소 삽입

.updata([원소1, 원소2, ...]) : 여러 원소 삽입

.remove(특정 원소) : 특정 원소 제거

 

사전 자료형과 집합 자료형의 특징

순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다.

    - 사전은 키를 이용해 원하는 값을 조회할 수 있고, 집합은 튜플이난 리스트로 변환하여 조회한다.


|| 파이썬 기초 문법 ||

 

자주 사용되는 표준 입력 방법

- input() : 한 줄의 문자열을 입력받을 때, 사용 

- map() : 리스트의 모든 원소 각각에 특정 함수를 적용할 때 사용

 

ex) list(map(int, input.split()))

받은 것(input 사용)을 공백 기준으로 나누어 배열로 만들고( split 사용 )

정수형으로 변경(map 함수 사용)

 

 

빠르게 입력받기

사용자로부터 입력을 최대한 빠르게 받아야 하는 경우

sys를 import하여 

- sys.stdin.readline() 메서드를 사용한다.

    -단, 입력을 받은 후에 줄바꿈 기호가 자동으로 입력됨으로 rstrip() 메서드를 함께 사용해준다.

import sys

inputdata = sys.stdin.readline().rstrip()

 

입력을 받는 것만으로도 많은 시간이 소요되는 경우에 사용하여 효율을 높인다

이진 탐색, 정렬, 그래프 문제에서 많이 사용

 

 

자주 사용되는 표준 출력

print()

    줄바꿈을 원하지 않을때, end 속성 이용 => print(7, end = ' ')

 

    f-string 문법

대답 = 7

print(f"문자열 사이에 {대답}을 넣어서 사용")

 

 

조건문

if 키워드를 이용해 만들 수 있음

elif == else if

else

a = 5

if a == 5:
    print("a는 5여")
elif a == 0:
    print("a는 0이여")
else :
    print("아무것도 아니여")

 

 

    파이썬의 조건문에서는 대수학에서의 부등식을 그대로 사용할 수 있다

0 < x < 10 와 같은 방식으로 조건을 설정할 수 있다 

다른 언어의 경우 위와같이 쓴다면 0 < x를 먼저 확인해서 true 혹은 false를 내보내는데 true는 1 false는 0 이므로 

무조건 10보다 작기 때문에 x가 조건에 맞지 않더라고 조건문을 실행한다.

 

    pass 키워드

아무것도 처리하고 싶을 때, pass를 사용

continue는 현재 반복문을 넘어가는 것이고 pass는 정말 아무것도 하지 않는 것이다.

 

    논리 연산자

X and Y 둘다 참이여야 참

X or Y 둘 중 하나만 참이여도 참

not X X의 반대 : true라면 false 반환 false라면 true 반환

 

 

    파이썬의 기타 연산자

x in 리스트 : 리스트 안에 x가 있으면 참

x not in 문자열 : 문자열 안에 x가 들어있지 않으면 참

 

 

    조건문의 간소화

조건문이 간소하게 한줄로 적을 수 있다면 줄바꿈을 하지 않고 작성 가능하다.

 

        조건부 표현식

if ~ else문을 한줄에 작성 가능

ex) result = "Success" if score >= 80 else "fail"

 

 

반복문

while문과 for문이 있지만  코테에서는 더 간결하고 편한 for문을 사용한다

    while 문

while 조건:

    코드

코테에서 무한루프가 나오지 않도록 만든다.

 

    for 문

for 변수 in 리스트:

    실행 코드

for 변수 in range(시작, 끝 값(실제로 순회하고 싶은 끝 값) + 1):

    실행 코드

 

- range를 사용하는 for문에서 숫자 하나면 적는다면 시작값이 디폴트로 0이되고 적은 숫자는 끝값이 된다.

- 특정 조건을 만족했을 때, for문을 탈출하고 싶다면 break를 사용하면 된다.

- 중첩해서 사용할 수 있다

 

 

함수와 람다 표현식

함수의 종류

- 내장 함수

- 사용자 정의 함수

 

함수 정의하기

반복적으로 사용되는 코드를 함수로 만들어 소스코드의 길이를 줄일 수 있다.

def 함수이름(매개변수):
    실행 코드
    return 반환 값

리턴 값이 존재하지 않아도 된다.

 

    global 키워드

함수 바깥에서 선언된 변수를 함수 안에서 사용하고 싶을때 함수 내에서 global을 붙여서 가지고 온다.

a = 10

def func():
    global a
    print(a)

func()

 

전역 변수로 설정된 리스트 객체는 global 키워드가 없어도 참조할 수 있다.

 

- 여러개의 반환 값을 가질 수 있다.

여러개를 반환 하는 것을 테킹 순서에 맞게 결과값을 담는 것을 언테킹이라고 한다

 

람다 표현식

람다 표현식을 이용해 함수를 간단하게 작성

    - 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다.

print((lambda a, b : a + b)(3, 7))

# 위의 방식은

def add(a, b):
    return a+b

# 와 같다

 

 

보통 정렬함수에서 많이 사용하기도 한다.

 

여러개의 리스트에 동일한 규칙을 적용시킬 때도 사용한다

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = map(lambda x y : x + y, list1, list2)

실행 결과 [7, 9, 11, 13, 15]

 

 

자주 사용되는 표준 라이브러리

  • itertools : 순열(permutations)과 조합(combinations) 라이브러리가 포함되어있다.
  • heepq : 힙의 자료구조를 제공 >> 우선순위 큐 기능을 구현하기 위해 사용
  • bisect : 이진 탐색 기능 제공
  • collections : 덱, 카운터 등의 자료구조 포함
  • math : 필수적인 수학적 기능 제공 >> 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련함수 혹은 파이와 같은 상수 포함

    자주 사용되는 내장 함수

  • sum 함수 : 리스트나 튜플이 들어왔을 때, 합 반환
  • min, max 함수 : 가장 작은 값 혹은 작은 값 반환
  • eval 함수 : 문자열 내 수식을 계산하여 반환
  • sorted() :
    • 오름차순
    • 내림차순 >> sorted(배열, reverse = True)
    • 키 속성으로 정렬 기준 설정이 가능하다
array = [('홍길동', 89), ('이순신', 77), ('아무개', 40)]
sorted(array, key = lambda x : x[1] )

 

    순열과 조합

- 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열 >> 순서가 있다

from itertools import permutations

data = ['A', 'B', 'C']

result = permutations(data, 몇개 선택한건지 설정 if 3)
print(result)

 

- 조합 : 서로 다른 n개에서 순서 상관없이 서로 다른 r 선택 >> 순서가 없다

from itertools import combinations

result = combinations(data, 뽑는 개수 if 2)
print(result)

 

중복 순열 : product

중복 조합 : combinations_with_replacement

 

Counter  

등장 횟수를 세는 기능

 

 

최대 공약수와 최대 공배수

import math

a = 21
b = 14

print(math.gcd(21, 14)) # 최대 공약수
print(lcm(21, 14)) # 최대 공배수 

det lcm(a, b):
    return a * b / math.gcd(a, b)

+ Recent posts