파이썬 알고리즘

기본 파이썬 문법

변수와 출력함수

변수명 정하기

1) 영문과 숫자, _로 이루어진다.

2) 대소문자를 구분한다.

3) 문자나 _로 시작한다.

4) 특수문자를 사용하면 안된다.(%, &등)

5) 키워드를 사용하면 안된다.(if, for)

#값 교환

a, b = 10, 20

a, b = b, a

#출력방식

print(”number”)

print(a, b, c, sep=’, ‘) → sep 는 출력될 때 a, b, c 사이사이가 어떻게 될 지 결정해줌

print(a, end = ‘ ‘) 기본적으로 print엔 엔터가 입력되있는데, end를 통해 옆으로 작성 가능.

변수입력과 연산자

a = input()

a = input(”숫자를 입력하세요: “)

a, b = input(”숫자를 입력하세요: “).split() →input이 a, b를 모두 받고 split이 공백을 인식하여 a와 b를 분리시킨다.

a, b = map(int, input(”숫자를 입력하세요 : “).split())

반복문(for, while)

a = range(10) → range함수는 순차적으로 정수리스트를 생성

a = range(1, 11) → 1부터 10까지의 정수리스트

for i in range(1, 10) → i가 1부터 9까지 증가하면서 들어감.

for i in range(10, 0, -2) → 10부터 0까지 2씩 작아짐. 3번째가 증감 간격.

for else 문

for i in range(1, 11):

print(i)

if i>15:

break

else:

print(11)

→ 1부터 11까지 출력된다. for-else문은 for문이 정상적으로 종료되면 else구문 출력. break를 통해 나왔다면 미출력.

반복문을 이용한 문제풀이

1) 1부터 N까지 홀수출력하기

n = int(input())
for i in range(1, n+1):
    if i % 2 == 1:
        print(i)
Python
복사

2) 1부터 N까지의 합 구하기

n = int(input())
sum = 0
for i in range(1, n+1):
    sum = sum + i
		print(sum)
Python
복사

3) N의 약수구하기

n = int(input())
for i in range(1, n+1):
    if n % i == 0:
				print(i, end= ' ')
Python
복사

리스트와 내장함수(1)

a = []

a = list()

a = list(range(1, 11)

a.append → 리스트에 추가시키기.

a.insert(3, 7) → a의 3번 인덱스(3뒤로)에 7을 삽입한다.

a.pop() → 리스트의 맨 뒤 제거.

a.pop(3) → a의 3번 인덱스에 있는 것을 제거.

a.remove(4) → a에 있는 ‘4’를 제거.

a.index(5) → a에 있는 ‘5’의 인덱스 출력

sum(a) max(a) min(a)

a.sort() → a를 오름차순으로 배열

a.sort(reverse= True) → a를 내림차순으로 배열

len(a) → a리스트 길이

람다함수

def plus_one(x):
		return x+1
print(plus_one(1))     #2



plus_two=lambda x: x+2 
print(plus_two(1))     #3
위의 함수를 이와같이 간단히 만들수도 있다.
Python
복사

내장함수의 인자로 사용될 때 편함.

a = [1, 2, 3]

def plus_one(x):
		return x+1
print(plus_one(1))

print(list(map(plus_one, a))        # [2, 3, 4]

print(list(map(함수명, a)))


이걸 함수 쓸 필요도 없이

print(list(map(lambda x: x+1, a))) #[2, 3, 4]
Python
복사

문제 구현능력 기르기

K번째 약수 구하기

내 답.

N, K = map(int, input().split())

lst=[]
for i in range(1, N+1):
    if N % i == 0:
        lst.append(i)

if len(lst)<K:
    print -1

else:
    print(lst[K-1])
Python
복사

선생님 답.

N, K = map(int, input().split())

cnt = 0
for i in range(1, N+1):
    if N % i ==0:
        cnt+=1
    if cnt == K:
        print(i)
        break
else:
    print(-1)
Python
복사

K번째 수

N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수를 오름 차순 정렬했을 때 k번째로 나타나는 숫자를 출력하는 프로그램을 작성하세요.

T = int(input())
lst = []
for i in range(T):
    N, s, e, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = a[s-1: e]
    a.sort()
    print(a[k-1])
Python
복사

내가 생각 못한것.

슬라이싱, 바로 list함수를 이용하여 list에 추가시키기.

자릿수의 합

N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 각 자연수의 자릿수의 합을 구하는 함수를 def digit_sum(x)를 꼭 작성해서 프로그래밍 하세요.

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

def digit_sum(x):
    sum = 0
    while x>0:
         sum += x % 10
         x= x//10
    return sum




max = -2147000000
for x in a:
    tot = digit_sum(x)
    if tot> max:
        max = tot
        res = x
print(res)
   
Python
복사

python의 장점을 활용하여

def digit_sum(x):
    sum = 0
    for i in str(x):
        sum += int(i)
    return sum
Python
복사

숫자를 → 문자열로 분리 ex)216→ ‘2’ ‘1’ ‘6’ 이걸 int화시켜서 더하기.

에라토스테네스의 체(소수판별법)

n = int(input())
cnt = 0
ch = [0]*(n+1)
cnt = 0
for i in range(2, n+1):
    if ch[i] == 0:
        cnt += 1
        for j in range(i, n+1, i):
            ch[j] = 1

print(cnt)
Python
복사

ch에 모두 0으로 초기화시켜놓고 인덱스 번호를 따라 체크하는건데

만약 0이면 cnt+1 되고 , 그 수의 배수인건 다 1로 체크된다. (for j in range(시작지점, 끝나는지점, 건너뛰는만큼) 이니까 i가 2라면 2의 배수는 싹다 걸러지는거.

*for - else 구문

for i in range(2, x//2+1):

if x%i == 0:

return False

else:

return True

for-else구문은 위의 for문에 break, return 등 함수를 종료시키는 것이 있을 때 for문이 도중에 종료되지 않고 정상적으로 끝났다 → else문 실행.

탐색&시뮬레이션

회문 문자열 검사

N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열) 이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다. 단 회문을 검사할 때 대소문자를 구분하지 않습니다.

N = int(input())

for i in range(N):
    s = input()
    s = s.upper()
    size = len(s)

    for j in range(size//2):
        if s[j] != s[-1-j]:
            print("#%d NO" %(i+1))
            break
    else:
        print("#%d YES" %(i+1))
Python
복사

대소문자를 구별하지 않는다 → 다 대문자로 만들어버리고 비교해보면 될 일.

s[j] s[-1-j] 이와 같이 리스트 안 -도 잘 활용해주면 좋다.

이걸 더 짧게,

N = int(input())

for i in range(N):
    s = input()
    s = s.upper()

    if s == s[::-1]:
        print("#%d YES" %(i+1))
    else:
        print("#%d NO" %(i+1))
Python
복사

s[::-1] 슬라이스 기능을 통하여 문자열을 뒤집어서 비교할 수도 있다.

근데 이는 파이썬스럽고 간단하긴 하지만 추천하진 않는다.

숫자만 추출

문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2h0er”에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120이 됩니다. 즉 첫 자리 0은 자연수화 할 때 무시합니다. 출력은 120를 출력하고, 다음 줄에 120 의 약수의 개수를 출력하면 됩니다

s = input()
res = 0
for x in s:
    if x.isdecimal():
        res = res * 10 + int(x)  

print(res)
cnt = 0
for i in range(1,  res+1):
    if res%i == 0:
        cnt += 1

print(cnt)
Python
복사

x.isdigit() → x가 숫자면 TRUE(2^2 이런것도 TRUE)

x.isdecimal() → x가 0~9 중 하나면 TRUE

res = 0

res = res * 10 + N 숫자 만들기

t = N % 10

res = 0

res = res * 10 +t 숫자 뒤집어서 만들기

sum = 0
while x>0:
	sum += x %10
	x = x//10
Python
복사

숫자 자릿수 합 구하기.

sum = 0

while x> 0:

    sum += x % 10

    x = x//10                 **자릿수더하기**

이걸 더 짧게

for i in str(x):
    sum += int(i)
return sum
Python
복사

정수를 문자열화 시켜서 한 자 한자 따지게 만들고, 합에 각 자리를 정수화시켜서 더해주기.

격자판 합구하기

n=int(input())
a=[list(map(int, input().split())) for _ in range(n)]
largest=-2147000000
for i in range(n):
    sum1=sum2=0
    for j in range(n):
        sum1+=a[i][j]
        sum2+=a[j][i]
    if sum1>largest:
        largest=sum1
    if sum2>largest:
        largest=sum2
sum1=sum2=0
for i in range(n):
    sum1+=a[i][i]
    sum2+=a[i][n-i-1]
if sum1>largest:
    largest=sum1
if sum2>largest:
    largest=sum2
print(largest)
Python
복사

최댓값은 처음에 꼭 초기화 시켜주기. 가로, 세로, 대각선 더해서 비교한것.

문자열 회전시키기

for i in range(m):
    h, t, k = map(int, input().split())
    if t == 0 :
        for _ in range(k):
            a[h-1].append(a[h-1].pop(0))
    else:
        for _ in range(k):
            a[h-1].insert(0, a[h-1].pop())

0이 오른쪽으로 , 1이 왼쪽으로 문자열 회전시킬 때를 의미한다.
"a[h-1].append(a[h-1].pop(0))" 0번째 인덱스에서 pop되었으므로 문자열은 땡겨지며 그 0번째
에 있던 인자를 append 마지막에 붙여줌.

"a[h-1].insert(0, a[h-1].pop())" 마지막 인자를 pop시키고, insert를 이용하여 0번째 인덱스에 
새로운 인자 넣어주기.
Python
복사

격자판에서 상하좌우 탐색하기

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]

cnt=0
for i in range(1, n+1):
    for j in range(1, n+1):
        if all(a[i][j]>a[i+dx[k]][j+dy[k]] for k in range(4)):
            cnt+=1

dx, dy를 이용하여 상하좌우를 탐색할수 있다.
all함수는 ( ) 안이 모두 TRUE 일때 작동한다. 
Python
복사

회의실 배정(그리디)

그리디 알고리즘은 주로 정렬을 먼저 시킨다. 그 정렬을 시키고 어떻게 효율적으로 할지를 생각하자.

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

n = int(input())
meeting = []
for i in range(n):
    s, e = map(int, input().split())
    meeting.append((s, e))

meeting.sort(key = lambda x : (x[1], x[0]))
et = 0
cnt = 0
for s, e in meeting:
    if s >= et:
        et = e
        cnt += 1
Python
복사

→ 회의가 빨리 시작한다고 회의를 많이 할 수 있는게 아니다. 회의가 빨리 끝나야 많이 하게 되므로

회의가 끝나는 시간 순으로 일단 정렬한다.

meeting.sort(key = lambda x : (x[1], x[0]))

→튜플 형식으로 리스트에 넣어주었을 때 sort함수를 쓰면 tuple자료형의 앞을 기준(a, b)가 있으면 a기준으로 정렬을 하는데 위의 식을 통해 뒤에꺼 기준으로 정렬을 하란 의미이다.

씨름선수 뽑기

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자 만 뽑기로 했습니다.” 만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니 다

N = int(input())
body = []
for _ in range(N):
    h, w = map(int, input().split())
    body.append((h, w))

body.sort(reverse= True)
largest = 0
cnt = 0
for h, w in body:
    if w > largest:
        largest = w
        cnt += 1
print(cnt)
Python
복사

→ 일단 키 순으로 내림차순으로 정렬을 하자. 그럼 사실 몸무게만 보면 된다. 왜? 키가 큰 애들은 이미 키가 모두 크니까 . 밑으로 내려가면서 키가 위보다 작긴한데 몸무게만 크면 된다. 몸무게가 위애들보다 크면 됨. → 몸무게의 최댓값을 갱신해가면서 세면 된다.

재귀함수와 스택

def DFS(x):
    if x>0:
    
        print(x, end= " ")
        DFS(x-1)
Python
복사

실행하면 3 2 1

def DFS(x):
    if x>0:
		    DFS(x-1)
        print(x, end= " ")
        
Python
복사

실행하면 1 2 3

왜 다르게 나올까?

밑의 경우 print실행되기전 먼저 DFS가 호출되므로 스택으로 먼저 쌓인다.

결과적으로 말하면 위부터 실행되므로 1 2 3 출력되는것.

이진트리순회(깊이우선탐색)

기본적으로 부모, 왼쪽자식, 오른쪽 자식으로 구성된다.

전위순회 = 부→왼→오 부모에서 왼쪽으로 계속 가고 없으면 백에서 오른쪽

1 2 4 5 3 6 7 전위순회출력

*대부분의 문제.

def DFS(v):
    if v > 7:
        return
    else:
        print(v, end = " ")
        DFS(v*2)                   #왼쪽 자식
        DFS(v*2+1)                 #오른쪽 자식


if __name__ == "__main__":
    DFS(1)
Python
복사

여기선 print함수가 함수본연의 일. 그니까 본연의 일 하고→ 왼쪽 → 오른쪽 가면 전위순회다.

저기 print 함수가 집어넣어있는 쪽에 다른 함수가 들어가면 된다.

중위순회 = 왼→부→오

4 2 5 1 6 3 7 중위순회출력

def DFS(v):
    if v > 7:
        return
    else:
       
        DFS(v*2)                    #왼쪽 자식
        print(v, end = " ")             
        DFS(v*2+1)                 #오른쪽 자식


if __name__ == "__main__":
    DFS(1)
Python
복사

후위순회 = 왼 → 오→ 부

4 5 2 6 7 3 1

*병합정렬

def DFS(v):
    if v > 7:
        return
    else:
       
        DFS(v*2)                    #왼쪽 자식
        DFS(v*2+1)                  #오른쪽 자식
        print(v, end = " ")              


if __name__ == "__main__":
    DFS(1)
Python
복사