알고리즘

백준(수업)

• 최대공약수 gcd

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

a,b=map(int,input().split())
result=gcd(a,b)
print(result)
-------------출력--------------
-------------출력--------------
35 80
5

• 백준 18352번 특정 거리 도시 찾기

import sys
from collections import deque
input=sys.stdin.readline

n,m,k,x=map(int,input().split()) # 노드수,엣지수,목표거리,시작노드
a=[[] for _ in range(n+1)] #초기화
answer=[] #값을 담을 리스트
visited=[-1]*(n+1) #방문리스트 초기화

def bfs(v):
    q=deque()
    q.append(v)
    visited[v] +=1
    while q:
        now=q.popleft() 
        for i in a[now]:
            if visited[i]==-1: #미방문이면
                visited[i]=visited[now]+1
                q.append(i)

#두번째 줄부터 엣지 입력
for _ in range(m):
    s,e=map(int,input().split())
    a[s].append(e)

bfs(x) #시작점부터 bfs 시작

for i in range(n+1):
    if visited[i]==k:
        answer.append(i)

if not answer:
    print(-1)
else:
    answer.sort()
    for i in answer:
        print(i)

백준(자습)

• 10811번 바구니 뒤집기

  
  

m,tc=map(int,input().split()) # 5 4 -> 빈 바구니 5개,테케 4개
emp=[i+1 for i in range(m)] # emp=[1,2,3,4,5] / 1->emp[0] 5->emp[4]임을 유의
for _ in range(tc):
    i,j=map(int,input().split())
    emp[i-1:j]=reversed(emp[i-1:j])

for i in emp:
    print(i,end=' ')

1) list의 원소를 역순으로 뒤집는 방법을 모르겠어서 ChatGpt를 통해 알아봄

레전드..

print(emp) # [1,2,3,4,5]
emp[1:5] = reversed(emp[1:5]) 
print(emp) # [1,5,4,3,2]

--> emp가 [1,2,3,4,5] 일 때, reversed(emp[1:5]) 로 뒤집으면 [1,2,3,4,5] 에서 [1,5,4,3,2]로 뒤집힌다.
cf) 즉 emp[i:j]로 뒤집으면 두번째부터 다섯번째까지 즉 i+1부터 j까지가 반대로 뒤집힘

2) 문제 입력 예시를 보면 1,4 입력 시 1~4까지가 역순이 되어야 하기 때문에 i,j 입력 하면 i부터 j까지 반대로 뒤집히도록 구현해야 하기때문에 1) 의 cf) 를 참조하여 인덱스를 i-1,j로 잘라서 맞춰줘야 문제가 요구하는대로 출력됨.

3) 아래 예시 참조

• 2675번 문자열 반복

  
  

tc=int(input())
for i in range(tc):
    r,s=map(str,input().split())
    for j in range(len(s)):
        print(f'{int(r)*s[j]}',end='')
    print()

• 1157번 단어 공부

  
  

str1=str(input()).lower() #일단 소문자로 저장
str1_set=list(set(str1)) # Mississipi입력 시 ['p','i','m','s']

arr=[]

for i in str1_set: # Mississipi / i --> p , i , m , s
    count=str1.count(i)
    arr.append(count)

if arr.count(max(arr))>=2: 
    print('?')

else:
    print(str1_set[arr.index(max(arr))].upper())

ex) 입력 예시 : Mississipi

1) str1_set = list(set(str1)) --> mississipi를 중복제거하여 list형태로 저장함->['p','i','m','s']

2) for i in str1_set : i는 p,i,m,s

3) count=str1.count(i) --> str1 즉 mississipi에 들어있는 i의 개수를 세어서 count에 집어넣고 빈 배열 arr에 count를 원소로 넣음

mississipi 의 경우 p i m s 를 찾으면서 arr은 [1,4,1,4] 의 형태로 저장됨

4) arr.count(max(arr)) --> max(arr) : 4 즉 가장 많이나온 알파벳 단어의 개수를 찾는데 그 값이 2이상 즉 가장 많이나온 알파벳 단어가 2개 이상이면 ? 출력

5) 2개 이상이 아니면 arr.index(max(arr)) 으로 가장 많이 나온 알파벳 위치를 받아와서 str1_set으로 해당 알파벳을 .upper을 통해 대문자로 변환하면서 동시에 출력

cf) str1_set=['p','i','m','s'] / arr=[1,4,1,4] 인데 max 라고 하면 인덱스값으로 1을 반환해서 str1_set에서 i 를 찾고 이를 upper 을 통해 대문자로 변환해서 출력

• 백준 2908번 상수

  
  

num1,num2=map(int,input().split())

re_num1=str(num1)[::-1]
re_num2=str(num2)[::-1] # 사용시에 int로 형변환 해야함

if int(re_num1)>int(re_num2):
    print(re_num1)
else:
    print(re_num2)

1) str으로 형변환 하고 뒤집은 다음 다시 int 형으로 형변환해서 크기 비교