희연's 개발 일기장

• [선수지식] 재귀함수와 스택

# ch6 - [선수지식] 재귀함수와 스택
def DFS(x):
    if x > 0:
        DFS(x-1)
        print(x)  # 1 2 3

        #print(x) # 3 2 1 -> stack에 매개변수, 지역변수, 복귀주소 저장
        #DFS(x-1)

if __name__ == "__main__":
    n = int(input())
    DFS(n)

• 1. 재귀함수를 이용한 이진수 출력

# ch6 - 1. 재귀함수를 이용한 이진수 출력
n = 720

def recursive(num):
    if num >= 1:
        recursive(num//2)
        print(num%2, end='')
recursive(n)

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

# ch6 - 2. 이진트리 순회(깊이우선탐색)
# 깊이우선탐색은 root부터 탐색 -> 전위순회

def DFS(n):
    if n>7:
        return
    
    else:
        left = n*2
        right = (n*2)+1
        print(n, end=' ')
        DFS(left)
        DFS(right)
DFS(1)

• 3. 부분집합 구하기

# ch6 - 3. 부분집합 구하기
n = 3
ch=[0]*(n+1)

def DFS(v):
    if v>n:
        for i in range(1, n+1):
            if ch[i]==1:
                print(i, end=' ')
        print()
    else:
        # D(1) -> D(2) -> D(3)
        ch[v]=1 # 방문 체크
        DFS(v+1)
        ch[v]=0
        DFS(v+1)
DFS(1)

• 4. 합이 같은 부분집합

# ch6 - 4. 합이 같은 부분집합

n = 6
list = [1,3,5,6,7,10]
total = sum(list)

def DFS(v,sum):
    if v==n:
        if sum==(total-sum): 
            print('YES')
    else:
        DFS(v+1, sum+list[v])
        DFS(v+1, sum)
DFS(0,0)

• 5. 바둑이 승차

# ch6 - 5. 바둑이 승차
c, n  = 259, 5 # 제한 무게, 바둑이 수
list = [81,58,42,33,61]
maxVal =float('-inf')

def DFS(v,sum):
    global maxVal
    if n==v:
        if sum>maxVal and c>=sum:
            maxVal=sum
    else:
        DFS(v+1, sum+list[v])
        DFS(v+1, sum)
DFS(0,0)
print(maxVal)

• 6. 중복 순열 구하기

# ch6 - 6. 중복 순열 구하기
n, m = 3,2
res = [0]*m
cnt = 0

def DFS(v):
    global cnt 
    if v==m: 
        for j in res:
            print(j, end=' ') # 배열안에 있는 수열 출력
        print()
        cnt = cnt + 1
    else:
        # 중복 상관없이 d1, d2, d3
        for i in range(1, n+1):
            res[v] = i # 배열에 수열 넣기
            DFS(v+1)

DFS(0)
print(cnt)

• 7. 동전 교환 - 복습

# ch6 - 7. 동전 교환
n=3 # 동전 종류 개수
list=[1,2,5] # 동전 종류
m = 15 # 거스름돈
minCnt = float('inf')
cnt = 0

def DFS(v,sum):
    global minCnt
    if v>minCnt or sum>m: # 최소개수를 넘거나 거스름돈 초과하면 종료
        return
    if sum == m and v < minCnt: # 거스름돈 가격일 때, 최소 개수
        minCnt = v
    else:
        for i in range(n): # d0->d1->d2..., 각 가격
            DFS(v+1, sum+list[i])

DFS(0,0)
print(minCnt)

• 8. 순열 구하기

# ch6 - 8. 순열 구하기
n, m = 3,2
cnt = 0
res = [0]*n
ch = [0]*(n+1)

def DFS(v):
    global cnt
    if v==m: # 순열 길이만큼 
        for i in range(n): # 결과 출력
            print(res[i], end=' ')
        print()
        cnt = cnt + 1
    else:
        for j in range(1, n+1):
            if ch[j]==0: # 방문 안한경우
                ch[j] = 1 # 방문체크
                res[v]= j 
                DFS(v+1)
                ch[j] = 0
                
DFS(0)
print(cnt)

• 9-1. 순열 추측하기 - 복습

# ch6 - 9. 수열 추측하기
import sys
n, f = 4, 16

p = [0]*n
b = [1]*n # 1 1 1 1 -> 1 3 3 1
ch = [0]*(n+1)

def DFS(v, sum):
    if v==n and sum==f:
        for j in p:
            print(j, end=' ')
        sys.exit(0)
    else:
        for i in range(1, n+1):
            if ch[i]==0:
                ch[i]=1
                p[v]=i
                DFS(v+1, sum+(p[v]*b[v]))
                ch[i]=0

for i in range(1, n): # 맨끝은 x
    b[i] = b[i-1]*(n-i)//i # 이항계수 구하기

DFS(0,0)

• 9-2. 순열 추측하기(라이브러리)

#ch6 - 10. 수열 추측하기(라이브러리)
import sys
import itertools as it
n, f = 4, 16
b=[1]*n
cnt = 0

for i in range(1,n):
    b[i] = b[i-1]*(n-i)//i # 이항계수

a = list(range(1,n+1))

# 모든 수열의 경우의 수 구해주는 permutations
for tmp in it.permutations(a):
    sum = 0
    for L, x in enumerate(tmp):
        sum = sum + (x*b[L])
    if sum==f:
        for x in tmp:
            print(x, end=' ')
        break

#4개의 수 중에서 3개의 수로 수열만드는 경우
#for tmp in it.permutations(a, 3):
#    print(tmp)

• 10. 조합구하기 - 복습

# ch6 - 10. 조합 구하기
n, m = 4, 2
cnt = 0
res = [0]*m

def DFS(v, start):
    global cnt
    if v==m:
        for j in res:
            print(j, end=' ')
        print()
        cnt = cnt + 1
    else:
        for i in range(start,n+1): # 시작지점부터
            res[v]=i
            DFS(v+1, i+1)

DFS(0, 1)
print(cnt)

• 11-1. 수들의 조합

# ch6 - 11. 수들의 조합(dfs)
n, k = 5, 3
list = [2, 4, 5, 8, 12]
m = 6
cnt = 0

def DFS(v, sum, start):
    global cnt
    if v == k and sum % m == 0:
        cnt = cnt + 1
    else:
        for i in range(start, n):
            DFS(v+1, sum+list[i], i+1)

DFS(0, 0, 0)
print(cnt)

• 11-2. 수들의 조합(라이브러리)

# ch6 - 11. 수들의 조합(라이브러리) 
import sys
import itertools as it
n, k = 5, 3
a = [2, 4, 5, 8, 12]
m=6
cnt = 0

for x in it.combinations(a, k): # a 리스트에서 k개의 조합
    if sum(x)%m==0:
        print(x)
        cnt = cnt + 1
print(cnt)

• 12. 인접행렬(가중치 방향 그래프)

# ch6 - 12. 인접행렬(가중치 방향그래프)
n,m=6,9 # 정점의 수, 간선의 수
# 연결정보 거리비용
list=[[1,2,7],[1,3,4],[2,1,2],[2,3,5]
,[2,5,5],[3,4,5],[4,2,2],[4,5,5],[6,4,5]]
res = [[0]*(n+1) for _ in range(n+1)] # 2차원 배열 생성 0으로 초기화

for i in range(len(list)):
    # a, b, c = map(int, input().spilt())
    start = list[i][0]
    end = list[i][1]
    cost = list[i][2]
    res[start][end]=cost

for i in range(1, n+1):
    for j in range(1, n+1):
        print(res[i][j], end= ' ')
    print()

• 13. 경로 탐색 - 복습

# ch6 - 13. 경로 탐색
n, m = 5, 9  # 정점의 수, 간선의 수
list = [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]
info = [[0]*(n+1) for _ in range(n+1)]  # 2차원 배열 생성
cnt = 0
ch = [0]*(n+1)

for i in range(len(list)):
    start = list[i][0]
    end = list[i][1]
    info[start][end] = 1

def DFS(L):
    global cnt
    if L == n:
        cnt += 1
        for x in path:
            print(x, end=' ')
        print()
    else:
        for i in range(1, n+1):
            if info[L][i] == 1 and ch[i] == 0:
                ch[i] = 1
                path.append(i)
                DFS(i)
                path.pop()
                ch[i] = 0

path = []
path.append(1)
ch[1] = 1
DFS(1)
print(cnt)

• 1. 가장 큰 수(스택)
• m 개의 숫자를 제거해서 얻을 수 있는 가장 최대 값

# ch5. 1. 가장 큰 수(스택)
#n = 84836543798739827589237689348957893758937689437896743489673489673986
#d = 30

n=5276823 
d=3
stack = []

num = list(map(int, str(n)))

for x in num:
    while stack and d>0 and stack[-1]< x:
        stack.pop()
        d = d - 1
    stack.append(x)

# 다 삭제되지 않은 경우 만들어진 숫자에서 제거해주기
if d!=0: 
    stack = stack[:-d]
print(stack)

• 2. 쇠막대기 - 복습

# ch5 - 2. 쇠막대기
str = '(((()(()()))(())()))(()())'
stack = []
res = 0

for i in range(len(str)):
    if str[i] == '(':
        stack.append(str[i])
    else:
        stack.pop()
        if str[i-1] == '(':
            res = res + len(stack)
        else:
            res = res + 1
print(res)

• 3. 후위표기식 만들기

# ch5 - 3. 후위표기식 만들기
n = '3+5*2/(7-2)'
stack = []
res = ''
for x in n:
    if x.isdigit():
        res = res + x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res = res + stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and (stack[-1] != '('):
                res = res + stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and (stack[-1] != '('):
                res = res + stack.pop()
            stack.pop()

while stack:
    res = res+stack.pop()
print(res)

• 4. 후위식 연산

# ch5 - 4. 후위식 연산
from curses.ascii import isdigit

n = '58+65*+32+-73*-5-323*++53+2+52*-+3+'
stack = []

for x in n:
    if x.isdigit():
        stack.append(int(x))
    else:
        if x=='+' or x=='-':
            op1 = stack.pop()
            op2 = stack.pop()
            res = 0
            if x=='+':
                res = op1+op2
            else:
                res = int(abs(op1-op2))
            stack.append(res)
        elif x=='*' or x=='/':
            op1 = stack.pop()
            op2 = stack.pop()
            if x=='*':
                res = op1*op2
            elif x=='/' and op1>op2:
                res = op1//op2
            else:
                res = op2//op1
            stack.append(res)
print(stack.pop())

• 5. 공주 구하기
• 1번부터 돌아가면서 K번째 사람 제거하기

# ch5 - 5. 공주 구하기
from collections import deque
n, k = 700, 9
arr = list(range(1,n+1))
q = deque(arr)

while q:
    # k번 만큼 idx 이동하면서 값을 빼면서 idx를 찾기전 까지 바로 값을 뒤에 붙여준다.
    for _ in range(k-1):
        current=q.popleft()
        q.append(current)
    q.popleft() # k 번째 값 삭제

    # 길이가 1이 되면 마지막 원소를 출력해주고 종료한다. 
    if len(q)==1:
        print(q[0])
        q.popleft()

• 6. 응급실
• 우선순위 별로 치료할 때, M번째 환자의 진료 순서를 구하기

# ch5 - 6. 응급실
from collections import deque
n, m = 5, 2
risk = [60,50,70,80,90]
q = []
cnt = 0

# 우선순위 큐 생성 - index, value
for pos, val in enumerate(risk):
    q.append((pos, val))
q = deque(q) 

while True:
    # 큐에서 pop
    current = q.popleft()
    # 제일 앞의 값보다 더 큰 수가 있으면 뒤로 보낸다
    if any(current[1]<x[1] for x in q):
        q.append(current)
    # 제일 앞의 값이 가장 큰 경우
    # 진료 횟수 cnt 증가
    else:
        cnt = cnt + 1
        # 찾는 환자일 경우에 break
        if current[0] == m: 
            print(cnt)
            break

• 7. 교육과정 설계
• 사전 필수 과목을 이수하지 않으면 NO 출력
• 필수 과목을 모두 이수하지 않으면 NO

# ch5 - 7. 교육과정 설계
str = 'CBA'
n = 3
list = ['CBDAGE','FGCDAB','CTSBDEA']

stackList = []
resList = []
for i in range(len(str)):
    stackList.append(str[-i-1])
    #print(str[-i-1])

for x in list:
    preIdx = 0
    res = 'YES'
    stack = stackList.copy()
    while stack:
        search = stack.pop()
        flag = x.find(search) # 없으면 -1
        if flag != -1: # 있는 경우
            idx = x.index(search)
            if preIdx > idx:
                res = 'NO'
                break
            else:
                preIdx = idx
        else:
            res = 'NO'
            break
    resList.append(res)
print(resList)

• 8. 단어 찾기
• 1개를 제외한 모든 값들이 2번 

# ch5 - 8. 단어 찾기
n = 5
listA = ('big','good','sky','blue','mouse')
listB = ('sky','good','mouse','big')
dict = {}

for x in range(len(listA)):
    dict[listA[x]] = 1

for x in range(len(listB)):
    del(dict[listB[x]])

for key, val in dict.items():
    # print(key, val)
    print(key)

• 9. Anagram(아나그램)
• 순서는 다르지만, 알파벳 개수가 같은 경우 찾기

# ch5 - 9. Anagram(아나그램)
from collections import defaultdict
# ch1 = 'AbaAeCe'
# ch2 = 'baeeACA'

ch1 = 'aacccc'
ch2 = 'ccccaa'
dict1 = defaultdict(int)
dict2 = defaultdict(int)
res = 'YES'

for x in range(len(ch1)):
    dict1[x] = dict1.get(ch1[x],0)+1
    dict2[x] = dict2.get(ch2[x],0)+1
    #dict1[ch1[x]] = dict1[ch1[x]] + 1
    #dict2[ch2[x]] = dict2[ch2[x]]+ 1

for key, value in dict1.items():
    if dict2[key]!=value:
        res = 'NO'
        break
print(res)

• 10. 최소 힙 - 복습

# ch5 - 10. 최소 힙
# 최소힙 : 완전이진트리, 부모가 자식보다 작다.
import heapq as hq
n = [5, 3, 6, 0, 0, 2, 4, 0, -1]
stack = []
minVal = float('inf')

for x in n:
    if x==-1:
        break
    if x==0:
        if len(stack)==0:
            print(-1)
        else:
            print(hq.heappop(stack))
    else:
        hq.heappush(stack, x)

• 11. 최대 힙 - 복습

import heapq as hq
n = [5,3,6,0,5,0,2,4,0,-1]
stack = []

for x in n:
    if x==-1:
        break

    if x==0:
        if len(stack) ==0:
            print('-1')
        else:
            print(-hq.heappop(stack))        
            
    else:
        hq.heappush(stack, -x)

• 1. 이분 검색
• 이분 검색은 정렬된 상태에서 사용 가능하다.

# ch4 - 1. 이분 검색
# 이분 검색은 정렬된 상태에서 사용 가능
n = 8
m = 32
arr = [23, 87, 65, 12, 57, 32, 99, 81]
lt = 0
rt = n-1

arr.sort()

while lt <= rt:
    mid = (lt+rt)//2
    if arr[mid] == m:
        print(mid+1)
        break
    elif arr[mid] > m:  # m 이 더 작은 경우 왼쪽으로
        rt = mid-1
    else:  # m 이 더 큰 경우 오른쪽으로
        lt = mid+1

• 2. 랜선 자르기(결정 알고리즘)

# ch4 - 2. 랜선 자르기(결정 알고리즘)
k = 4  # 이미 있는 랜선 개수
n = 11  # 필요한 랜선 개수
lenList = [802, 743, 457, 539]
lt = 1
rt = max(lenList)
maxLen = 0

while lt <= rt:
    mid = (lt+rt)//2
    num = 0
    for x in lenList:
        num = num + x//mid
    if num < n:
        rt = mid-1
    else: 
        maxLen = max(maxLen, mid)
        lt = mid+1
print(maxLen)

• 3. 뮤직 비디오(결정 알고리즘)

# ch4 - 3. 뮤직비디오(결정 알고리즘)
n, m = 9, 3
info = [1, 2, 3, 4, 5, 6, 7, 8, 9]
maxx = max(info)
lt = 1
rt = sum(list(info))
res = rt

while lt <= rt:
    mid = (lt+rt)//2
    sum = 0
    cnt = 1
    for x in info:
        if (sum + x) > mid:
            cnt = cnt + 1
            sum = x
        else:
            sum = sum + x
    if mid >= maxx and cnt <= m:
        # 반례 : 가장 긴 노래보다 용량이 커야한다
        res = mid
        rt = mid-1
    else:
        lt = mid+1
print(res)

• 4. 마구간 정하기(결정 알고리즘) - 복습

# ch4 - 4. 마구간 정하기(결정 알고리즘) 
n, c = 5, 3  # 마구간 개수, 말 마리수
listX = [1, 2, 8, 4, 9]  # 1 2 4 8 9
listX.sort()
lt = listX[0]
rt = listX[n-1]
res = 0

while lt <= rt:
    mid = (lt+rt)//2
    cnt = 1
    ep = listX[0]
    for x in listX:
        if (x-ep) >= mid:
            # print(lt, rt, x)
            cnt = cnt+1
            ep = x
    if cnt >= c:
        res = mid
        lt = mid + 1
    else:
        rt = mid-1

print(res)

• 5. 회의실 배정(그리디)
• list.sort(key=lambda x: (x[1]. x[0]))

# ch4 - 5. 회의실 배정(그리디)
# 그리디는 그 순간에 가장 좋은 방법을 선택 -> 대부분 정렬과 사용된다.
n = 5 # 회의 수
list = [[1,4],[2,3],[3,5],[4,6],[5,7]]
# 2차원 배열 정렬 
# lambda x : 리스트의 원소를 x로 받고
# x[1], x[0]: 1번이 1순위, 0번이 2순위로 정렬 
list.sort(key=lambda x: (x[1], x[0]))
endTime = 0
cnt = 0
for start, end in list:
    if start >= endTime:
        endTime=end
        cnt = cnt+1
print(cnt)

• 6. 씨름 선수(그리디) - 복습

# ch4 - 6. 씨름 선수(그리디)
# 키와 몸무게 중 적어도 하나는 크거나 무거운 지원자만 뽑기
# 키랑 몸무게가 둘다크면 탈락
n = 5
info = [[172,67],[183,65],[180,70],[170,72],[181,60]]

info.sort(reverse=True) # 첫번째원소 내림차순 정렬
largest = 0
cnt = 0

for h,w in info:
    #print(h, w)
    if w>largest: # 몸무게가 더 크면
        print(h, w)
        largest=w # 최대 몸무게
        cnt = cnt + 1

• 7. 창고 정리(그리디)

# ch4 - 7. 창고 정리(그리디)
l = 10 # 창고 가로 길이
list = [69,42,68,76,40,87,14,65,76,81] # 상자 높이
m = 50 # 높이 조정 횟수

for idx in range(50):
    list.sort()
    list[0] = list[0] +1
    list[-1] = list[-1] -1

list.sort()
print(list[-1]-list[0])

• 8. 침몰하는 타이타닉(그리디) - 복습

# ch4 - 8. 침몰하는 타이믹(그리디)
# 무게 제한이 m 일 경우에, 최소로 필요한 구명 보트 수 구하기
# n, m = 20, 120
#list = [68, 72, 30, 105, 55, 115, 36, 67, 119,
#        111, 95, 24, 25, 80, 55, 85, 75, 83, 21, 81]
n, m = 5, 140
list = [90,50,70,100,60]
list.sort()
print(list)
cnt = 0

while list:
    if len(list) == 1:
        cnt = cnt + 1
    if list[0]+list[-1] > m:
        list.pop()
        cnt = cnt + 1
    else:
        list.pop(0)
        list.pop()
        cnt = cnt + 1
print(cnt)

• 9. 증가수열 만들기(그리디) - 복습

# ch4 - 9. 증가수열 만들기(그리디) 
list = [3, 2, 10, 1, 5, 4, 7, 8, 9, 6]
new = []
listRear = 0

while list:
    # 둘다 큰 경우 - 작은 것 부터 먼저 넣기
    if list[0] > listRear and list[-1] > listRear:
        if list[0] < list[-1]:  # rt가 큰 경우
            new.append('L')
            listRear = list[0]
            list.pop(0)
        elif list[0] > list[-1]:  # lt 가 큰 경우
            new.append('R')
            listRear = list[-1]
            list.pop()
        else:  # lt == rt 종료
            break

    # 왼쪽만 큰 경우
    elif list[0] > listRear:
        new.append('L')
        listRear = list[0]
        list.pop(0)
    # 오른쪽만 큰 경우
    elif list[-1] > listRear:
        new.append('R')
        listRear = list[-1]
        list.pop()
    else:  # lt == rt 종료
        break
print(new)

• 10. 역수열(그리디) - 복습
• 역수열이 주어지면, 원래 수열 구하기

# ch4 - 10. 역수열(그리디)
n = 8
list = [5,3,4,0,2,1,1,0]
list.insert(0,0)
new = [0]*len(list)

for i in range(1,n+1):
    for j in range(n):
        if list[i]==0 and new[j]==0:
            new[j]=i
            break
        elif new[j]==0:
            list[i] = list[i] -1
print(new)

• 1. 회문 문자열 검사

# 1. 회문 문자열 검사
N = 5
strArr = ['level', 'moon', 'abcba', 'soon', 'gooG']

for idx in range(len(strArr)):
    str = strArr[idx].upper()  # 대문자 변환
    size = len(str)
    flag = True
    # print(str[-1]) 문자의 맨 뒤에 출력
    for j in range(size//2):
        if str[j] != str[-1-j]:  # size-j-1
            flag = False
            break
    if flag:
        print("#%d YES" % (idx+1))
    else:
        print("#%d NO" % (idx+1))

• 2. 숫자만 추출

# 2. 숫자만 추출
strArr = 'g0en2Ts8eSoft'
res = 0

for str in strArr:
    if str.isdecimal():  # 숫자만 isdecimal
        res = res*10 + int(str)
print(res)

• 3. 카드 역배치

# 3. 카드 역배치
order = [[5, 10], [9, 13], [1, 2], [3, 4], [5, 6],
        [1, 2], [3, 4], [5, 6], [1, 20], [1, 20]]

# 0 ~ 20 배열(21 size) 생성
arr = list(range(21)) 
for i in range(len(order)):
    s = order[i][0]
    e = order[i][1]
    for j in range((e-s+1)//2):  # 교환하는 수 만큼 돌기
        arr[s+j], arr[e-j] = arr[e-j], arr[s+j]  # 서로 교환하기
arr.pop(0)  # 0 없애주기
print(arr)

• 4. 두 리스트 합치기

# 4. 두 리스트 합치기 : 두 졍렬 리스트를 오름차순으로 합치기
n = 3
arrA = [1, 3, 5]
m = 5
arrB = [2, 3, 6, 7, 9]
p1 = p2 = 0
res = []

while p1 < n and p2 < m:
    if arrA[p1] <= arrB[p2]:
        res.append(arrA[p1])
        p1 = p1 + 1
    else:
        res.append(arrB[p2])
        p2 = p2 + 1

# 남은 배열 추가해주기
if p1 < n:
    res = res + arrA[p1:]
if p2 < m:
    res = res + arrB[p2:]

# 출력
for i in res:
    print(i, end=' ')

• 5. 수의 합
• 수열에서 m이 되는 경우의 수 구하기

# 5. 수의 합  
N, M = 8, 3
list = [1,2,1,3,1,1,1,2]
lt = rt = 0
sum = cnt = 0

while True:
    if sum < M:
        if rt < N:
            sum = sum + list[rt]
            rt = rt + 1
        else:
            break
    elif sum == M:
        cnt = cnt + 1
        sum = sum - list[lt]
        lt = lt + 1
    else:
        sum = sum - list[lt]
        lt = lt + 1
print(cnt)

• 6. 격자판 최대합

# 6. 격자판 최대합
arr = [
    [10, 13, 10, 12, 15],
    [12, 39, 30, 23, 11],
    [11, 25, 50, 53, 15],
    [19, 27, 29, 37, 27],
    [19, 13, 30, 13, 19]]
sum1 = sum2 = sum3 = sum4 = 0
max = 0

# 행과 열의 최대합
for i in range(len(arr)):
    sum1 = sum2 = 0
    for j in range(len(arr)):
        sum1 = sum1 + arr[i][j]
        sum2 = sum2 + arr[j][i]
    if max < sum1:
        max = sum1
    if max < sum2:
        max = sum2

# 대각선 최대합
for i in range(len(arr)):
    sum3 = sum3 + arr[i][i]
    sum4 = sum4 + arr[i][len(arr)-i-1]
    
if max < sum3:
    max = sum3
if max < sum4:
    max = sum4

print(max)

• 7. 사과나무

# 7. 사과나무 - 격자판의 값들 총합
N = 5
arr = [
    [10, 13, 10, 12, 15],
    [12, 39, 30, 23, 11],
    [11, 25, 50, 53, 15],
    [19, 27, 29, 37, 27],
    [19, 13, 30, 13, 19]]

size = N//2
start = end = size
res = 0

for i in range(len(arr)):
    for j in range(start, end+1):
        # print(arr[i][j], end=' ')
        res = res + arr[i][j]
    if i < size:
        start = start-1
        end = end+1
    else:
        start = start+1
        end = end-1
print(res)

• 8. 곶감(모래시계)

# 8. 곶감(모래시계)
N = 5
arr = [
    [10, 13, 10, 12, 15],
    [12, 39, 30, 23, 11],
    [11, 25, 50, 53, 15],
    [19, 27, 29, 37, 27],
    [19, 13, 30, 13, 19]]
M = 3
order = [[2, 0, 3], [5, 1, 2], [3, 1, 4]]
# 행, 0(왼쪽) or 1(오른쪽), 회전하는 수

# 각자의 행 이동시키기
for o in range(len(order)):
    row = order[o][0]
    direction = order[o][1]
    move = order[o][2]
    if direction == 0:  # 왼쪽으로 이동
        for _ in range(move):
            # 맨 앞의 원소 맨 뒤에 넣기
            arr[row-1].append(arr[row-1].pop(0))
    elif direction == 1:  # 오른쪽으로 이동
        for _ in range(move):
            # 맨 뒤의 원소 맨 앞에 넣기
            arr[row-1].insert(0, arr[row-1].pop())

# 모래시계 모양 원소들을 더해서 출력
size = N//2
start = 0
end = N-1
sum = 0

for i in range(N):
    for j in range(start, end+1):
        sum = sum + arr[i][j]
        #print(arr[i][j], end=' ')
    if i < size:
        start = start + 1
        end = end - 1
    else:
        start = start - 1
        end = end + 1
print(sum)

• 9. 봉우리

# 9. 봉우리
# 각 격자 판의 숫자 중 자신의 상하좌우보다 큰 숫자가 봉우리
# 봉우리 지역이 몇 개 있는지 알아내기
# 격자는 0으로 초기화
N = 5
arr = [
    [5,3,7,2,3],
    [3,7,1,6,1],
    [7,2,5,3,4],
    [4,3,6,4,1],
    [8,7,3,5,2]]
arr.insert(0, [0]*N) # 맨 위에 0으로 초기화
arr.append([0]*N) # 맨 밑에 0으로 초기화
for x in arr:
    x.insert(0,0) # 맨 왼쪽 행에 0
    x.append(0) # 맨 오른쪽 행에 0

# 동서남북
dx = [-1,0,1,0]
dy = [0,1,0,-1]
count = 0

for i in range(1, N+1):
    for j in range(1, N+1):
        flag = True
        for d in range(4):
            if arr[i][j] < arr[i+dx[d]][j+dy[d]]:
                flag = False
                break
        if flag:
            #print(arr[i][j], end=' ')
            count = count + 1
print(count)

• 10. 스도쿠 검사

# 10. 스도쿠 검사
# 3X3에 숫자 중복 없이, 각 행과 열에 1~9 숫자 중복 없이
a = [
    [1, 4, 3, 6, 2, 8, 5, 7, 9],
    [5, 7, 2, 1, 3, 9, 4, 6, 8],
    [9, 8, 6, 7, 5, 4, 2, 3, 1],
    [3, 9, 1, 5, 4, 2, 7, 8, 6],
    [4, 6, 8, 9, 1, 7, 3, 5, 2],
    [7, 2, 5, 8, 6, 3, 9, 1, 4],
    [2, 3, 7, 4, 8, 1, 6, 9, 5],
    [6, 1, 9, 2, 7, 5, 8, 4, 3],
    [8, 5, 4, 3, 9, 6, 1, 2, 7]]

def check(arr):
    for i in range(len(arr)):
        ch1 = [0]*10  # check list
        ch2 = [0]*10
        for j in range(len(arr)):
            ch1[arr[i][j]] = 1
            ch2[arr[j][i]] = 1
        if sum(ch1) != 9 or sum(ch2) != 9:
            return False
    for i in range(3):
        for j in range(3):
            ch3 = [0]*10
            for k in range(3):
                for s in range(3):
                    ch3[arr[i*3+k][j*3+s]] = 1
            if sum(ch3) != 9:
                return False
    return True

if check(a):
    print('YES')
else:
    print('NO')

• 11. 격자판 회문수

# 11. 격자판 회문수
# 가로나 세로로 연속된 수들 중에서 5자리 회문으로 된 숫자 개수 구하기
arr = [
    [2, 4, 1, 5, 3, 2, 6],
    [3, 5, 1, 8, 7, 1, 7],
    [8, 3, 2, 7, 1, 3, 8],
    [6, 1, 2, 3, 2, 1, 1],
    [1, 3, 1, 3, 5, 3, 2],
    [1, 1, 2, 5, 6, 5, 2],
    [1, 2, 2, 2, 2, 1, 5],
]

cnt = 0
for i in range(3):
    for j in range(7):
        #print(arr[j][i:i+5]) # slice 0~4개
        tmp = arr[j][i:i+5]
        print(tmp[::-1])
        if tmp == tmp[::-1]:
            cnt = cnt + 1
        for k in range(2):
            if arr[i+k][j] != arr[i+5-k-1][j]:
                break
        else:
            cnt = cnt + 1
print(cnt)

https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

• N개의 정수로 이루어진 배열 A가 주어질 때
• 배열을 오른쪽으로 K번 이동한 결과 출력
• 맨 마지막 요소는 맨 첫 번째 위치로 이동한다.
• ex. A = [3,8,9,7,6] -> [6,3,8,9,7] -> [7,6,3,8,9]

def solution(A, K):
    if A:
        for _ in range(K):
            tmp = A.pop()
            A.insert(0, tmp)
    return A

# 다른 풀이
def solution(A, K):
    if not (A and K):
        return A

    K = K % len(A)
    return A[-K:] + A[:-K]

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

• 양의 정수 N이 주어질 때
• 2진수로 표현한 후, 가장 큰 binary gap을 구해준다.
• binary gap : 1과 1사이에 있는 0들의 개수
• ex. 10000010001 -> binary gap = 5
• ex. 100000 -> no binary gap 

def solution(N):
    # 2진수 변환 앞의 2자리 버리기
    binaryNum = bin(N)[2:]
    gap = 0
    maxGap = 0
    flag = False
    for i in range(len(binaryNum)):
        if binaryNum[i] == '1':  # 첫번째 값
            if flag:  # 두번째 값
                if maxGap < gap:
                    maxGap = gap
                gap = 0
            else:
                flag = True

        elif flag:
            gap = gap + 1

    return maxGap

• 1. K번째 약수 구하기

# 1. 환경설정 및 K번째 약수 풀이
# 자연수 N, K번째로 작은 수
N, K = map(int, input().split()) 
a = [] # 리스트 생성

# 약수 구하기 : 1부터 N까지 나누었을 때 
for i in range(1, N+1):
    a.append(int(N//i))
    
    
# 약수 중복 제거 
newList = list(set(a))
if len(newList) < K: # 약수 개수가 K보다 작은 경우 -1
    print(-1)
else:
    newList.sort() # 약수 오름차순 정렬
    print(newList[K-1]) # K번쨰 값 출력

• 2. K번째 수

# 2. K번째 수
N,s,e,k = 6,2,5,3
array1 = [5, 2, 7, 3, 8, 9]
newArray1 = array1[s-1:e] # 2 7 3 8 
newArray1.sort() # 오름차순
print(newArray1[k-1]) # K번째 수 출력

• 3. K번째 큰 수

# 3. K 번째 큰 수
N, K = 10, 3 # 자연수 N, K 번째 수
arr = [13,15,34,23,45,65,33,11,26,42]
# arr = list(map(int, input().split()))
res = set() # 중복 제거 set 사용

# 3개씩 뽑아서 더하기
for a in range(N):
    for b in range(a+1, N):
        for c in range(b+1, N):
            res.add(arr[a]+arr[b]+arr[c])
res = list(res)
# 내림차순 정렬
res.sort(reverse=True)
# K 번째 수 구하기
print(res[K-1])

• 4. 대표값
• 반올림 구하기 round 대신 int(a+0.5) 

# 4. 대표값 - 평균에 가까운 수 구하기
N = 10
arr = [65, 73, 66, 87, 92, 67, 55, 79, 75, 80]
avg = sum(arr)//10
min = float('inf')
resIdx = 0

# enumerate을 사용하면 배열의 idx, val - 인덱스, 값 반환
for idx, val in enumerate(arr):
    dff = round(abs(avg-val))
    if min > dff:
        min = dff
        resIdx = idx
    elif min == dff and arr[resIdx] < val:
        resIdx = idx
print(round(avg), resIdx+1)

# round 반올림 오류
# round_half_even 방식 사용 -> 0.5 인 경우, 0 반환
# round 대신 0.5를 더해주고 int()를 사용
a = 66.5
print(a)
a = a+0.5
print(int(a))

• 5. 정다면체

# 5. 정다면체 - 두개의 정다면체의 값을 더할 때 가장 확률 높은 값 구하기
N, M = 4,6
arr = [0]*(N+M) # 최대값은 N+M

for i in range(1, N+1):
    for j in range(1, M+1):
        # 각 수에 cnt++ 
        arr[i+j-1] = arr[i+j-1] + 1

max = max(arr)

for idx, val in enumerate(arr):
    if max == val:
        print(idx+1, end=' ')

• 6. 자릿수의 합

# 6. 자릿수의 합 - 각 자릿수의 합을 구하고 가장 높은 자연수 출력
N = 3
arr = [125, 15232, 97]
max, maxVal = 0, 0

def digit_sum(x): # 자릿수 구하기 함수
    sum = 0
    while x > 0:
        sum = sum + int(x % 10)
        x = x/10
    return sum

for i in arr: # 자릿수의 최대값 구하기
    tmp = digit_sum(i)
    if max < tmp:
        max = tmp
        maxVal = i
print(maxVal)

• 7. 소수 - 에라토스테네스의 체
• 소수 개수 구하기

# 7. 소수 - 에라토스테네스의 체
# 소수 개수 구하기
N = 20
arr = [0]*(N+1)
cnt = 0

# 1은 소수가 아니다.
for i in range(2, N+1):
    if arr[i] == 0: # 배열의 값이 0 인 경우 = 소수
        cnt = cnt + 1
        # 소수의 배수는 1로 체크
    for j in range(i, N+1, i):
        arr[j] = 1
print(cnt)

• 8. 뒤집은 소수

# 8. 뒤집은 소수 - 자연수를 뒤집은 값이 소수일 경우 출력
N = 5
arr = [32, 55, 62, 3700, 250]

def reverse_num(num):
    res = 0
    while num > 0:
        tmp = int(num % 10)
        res = res*10+tmp
        num = num//10
    return res

def isPrime(num):
    if num == 1:
        return False
    for x in range(2, num):
        if num % x == 0:
            return False
    return True

for x in arr:
    reverse = reverse_num(x)
    if isPrime(reverse):
        print(reverse, end=' ')

• 소수 구하기 알고리즘 - 제곱근 사용

def isPrime(num):
    if num == 1:
        return False
    for x in range(2, int(math.sqrt(num) + 1)):
        if num % x == 0:
            return False
    return True

• 9. 주사위 게임 

# 9. 주사위 게임 
# 3개의 주사위를 각 규칙에 맞게 계산하고, 가장 최대값 출력
N = 3
arr = [[3, 3, 6], [2, 2, 2], [6, 2, 5]]
maxRes = 0

for i in range(len(arr)):
    count = 0
    value = 0
    maxCnt = 0
    for j in range(len(arr)):
        if value == arr[i][j]:
            count = count+1
        else:
            maxCnt = max(count, maxCnt)
            count = 1
            value = arr[i][j]
        if j+1 == len(arr):
            maxCnt = max(count, maxCnt)
    if maxCnt == 3: # 규칙 1(같은 눈3개)
        reward = 10000+(value*1000)
    elif maxCnt == 2: # 규칙 2(같은 눈2개)
        reward = 1000+(value*100)
    else: # 규칙 3(같은 눈X)
        reward = max(list(arr[i]))*100
    maxRes = max(maxRes, reward)
print(maxRes)

• 10. 점수 계산

# 10. 점수 계산 - OX 퀴즈 연속답 가산점 계산
N = 10
arr = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0]
subSum = 0
score = 0

for i in arr:
    if i == 0:
        subSum = 0
    else:
        subSum = subSum+1
        score = score + subSum
print(score)

• 입력 하나 받고 출력

n = input() # 입력 하나 받기
print(n) # 출력

• 값 교환

a, b = 10, 20
print(a, b) # 10 20
a, b = b, a
print(a, b) # 20 10

• 변수 타입 출력

a = 10
print(type(a)) # int
int, float, str

• 출력 방식

print("number")
print(a, b, c, sep=', ') # a, b, c 분리하는 방법 sep

• 줄바꿈 안하는 방법(end)

print(a, end=' ')

• 변수 입력과 연산자

a = input() # 입력 방법
print(a)

a = input("숫자를 입력하세요 : ") # 숫자를 입력하세요
a, b = input("숫자를 입력하세요 : ").split()

# 2개를 입력 받는 방식이 아니라, input으로 입력을 받은 후
# split을 통해 2개로 값을 분리 -> split
# split으로 분해되면 문자열로 들어간다.

print(a,b) # 3 5
print(a+b) # 35

# 다른 방법 - map
a, b = map(int, input("숫자를 입력하세요 : ").split())

• 사칙연산

input 3 2
a+b # 5
a-b # 1
a*b # 6
a/b 나누기 # 1.5
a//b 몫 # 1
a%b 나머지 # 2
a**b 거듭제곱 # 3^2

• 조건문

x=7
if x==7:
    print("Lucky")

if x>0 and x<10:
    print("10보다 작은 자연수")

if 0<x<10:
    print("10보다 작은 자연수")

if x>0:
    print("양수")
else:
    print("음수")

if x>=90:
    print('A')
elif x>=80:
    print('B')
else:
    print('F')

• 반복문

a = range(10) # 0~9까지 10개의 수
a = range(1, 11) # 1부터 10(1~10) 
print(list(a))

for i in range(10): # 0~9
    print(i)

for i in range(1,11): # 0~9
    print(i)

for i in range(10, 0, -2) # 10 8 6 4 2
    print(i)

i=1
while i<=10:
    print(i) # 1 ~ 10
    i=i+1 

i = 10
while i>=1:
    print(i)
    i = i-1

i=1
while True: # 1 ~ 10
    print(i)
    if i == 10:
        break
    i=i+1

for i in range(1, 11):
    if i%2==0:
        continue
    print(i) # 1 3 5 7 9

for i in range(1, 11):
    print(i)
    if i>15:
        break
else:
    print(11) # for문 정상 실행시 for else 구문 출력

# N = input() for문에서 N+1이 문자로 인식된다.
N = int(input()) # int 명시해주기
evenSum = 0
totalSum = 0
for i in range(1, N+1): 
    totalSum = totalSum + i
    if(i%2==1): # 짝수 출력
        print(i, end=' ')
    if(N%i==0): # 약수 출력
        print(i, end=' ')
print(totalSum) # 총합 출력

• 중첩 반복문(2중 for문)

for i in range(5): # 5번 반복
    print('i:', i, sep='', end=' ')
    for j in range(5):
        print('j:', j, sep='', end=' ')
    print()

for i in range(5):
    for j in range(i+1):
        print('*', end=' ')
    print()

for i in range(5):
    for j in range(5-i):
        print('*', end='')
    print()

• 문자열 접근 방법

# 문자열 접근 방법 1
for i in range(len(msg)): # 1~10
    print(msg[i], end='')

# 문자열 접근 방법 2
for x in msg: 
    print(x, end='')

• 대소문자, 문자열 쪼개기

msg = "It is Time"
print(msg.upper()) # 대문자 변환
print(msg.lower()) # 소문자 변환
print(msg)

tmp = msg.upper()
print(tmp)
print(tmp.find('T')) # 1 인덱스 번호를 찾아준다.
print(tmp[1]) # T
print(tmp.count('T')) # 2 특정 문자의 개수 출력
print(msg[:2]) # It : 제일 처음부터 1, 2번까지 
print(msg[3:5])
print(len(msg)) # 10


# 대소문자 출력
for x in msg:
    if x.isupper(): # 대문자만 출력
        print(x)

msg = "It is Time"
for x in msg:
    if x.isalpha(): # 알파벳만 출력
        print(x, end='')

• ASCII 표현

tmp = 'AZ'
for x in tmp:
    print(ord(x)) # ord는 아스키 넘버 출력 -> 65 90

tmp = 65
print(chr(tmp)) # 아스키 코드 출력 -> A

• 리스트와 내장함수

import random as r
a=[]
b=list()
print(a) # 같은 표현 1
print(b) # 같은 표현 2

a = [1,2,3,4,5]
b=list(range(1, 11)) # 1부터 10까지의 리스트
print(a+b) # 두개의 리스트를 합친다.
a.append(6) # 배열의 뒤에 원소를 추가하는 함수
a.insert(3, 7) # 3번 인덱스에 7 입력
a.insert(3, 7) # 3번 인덱스에 7 입력
a.pop() # 리스트 맨 뒤의 원소를 없애준다
a.insert(3, 7) # 3번 인덱스에 7 입력
a.pop(3) # 3번 인덱스 값을 제거해준다.
a.remove(4) # 4라는 값 찾아서 제거
print(a.index(5)) # 5라는 값의 인덱스 출력

a = list(range(1,11)) # 1부터 10까지의 리스트 생성
print(a) 
print(sum(a)) # 리스트 원소들의 총합
print(max(a)) # 최대값 출력
print(min(a)) # 최소값 출력
print(min(7,5)) # 인자 값들 중에서 최소값을 찾아주는 min

import random as r 
r.shuffle(a) # 랜덤으로 값을 섞어주는 라이브러리 
a.sort() # 오름차순 정렬
a.sort(reverse=True) # 내림차순 정렬
a.clear() # 리스트의 모든 값들이 삭제된다.

a = [23, 12, 36, 53, 19]
print(a[:3]) # 0~2번 index value output
print(a[1:4]) # 1~3번 index
print(len(a)) # 5

• 반복문으로 리스트 원소 접근

for i in range(len(a)): # 같은 결과 1
    print(a[i], end=' ')
print()

for x in a: # 같은 결과 2
    print(x, end=' ')
    
    
a = [23, 12, 36, 53, 19]
# 방식1
for x in enumerate(a): # 튜플 자료구조
    print(x)

# 방식2
for x in enumerate(a):
    print(x[0], x[1])
    
# 방식3 을 제일 많이 사용한다.
for index, value in enumerate(a):
    print(index, value)
    
# 출력 결과
# (0, 23)
# (1, 12)
# (2, 36)
# (3, 53)
# (4, 19)

리스트, 튜플, 셋, 딕셔너리

• list : [], 값 변경 가능
• tuple : (), 값 변경 불가능
• set : {}
• dictionary : {key:value, key:value}

b = (1,2,3,4,5)
print(b[0]) # 접근 방법 -> 1 출력
b[0] = 7 # 튜플의 값은 변경이 불가능하다

# if all, if any 사용방법
if all(50>x for x in a):
    print("YES")
else:
    print("NO")
# for문으로 a 리스트를 변수 x로 접근
# 60보다 큰 값들이 없어요 
# if all은 모든 값들이 해당되어야 한다. 1개라도 거짓이면 X

if any(15>x for x in a):
    print("YES")
else: 
    print("NO")
# any는 하나라도 참이면 참을 반환한다.