알고리즘

백준(수업)

• 11724번 연결 요소의 개수 구하기

  
  

#백준 11724 - 연결요소 개수 확인
#파이썬 재귀호출 1000번까지 가능
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,m=map(int,input().split()) # 6 5 일 때
A=[[] for _ in range(n+1)] # x, 7열 2차원 리스트
visited=[False]*(n+1) #[0,1,2,3,4,5,6,]

#DFS(재귀함수)
def DFS(v):
    visited[v]=True
    for i in A[v]:
        if not visited[i]:#방문을 안했다면
            DFS(i)

for _ in range(m): #엣지(edgt) 개수 만큼
    s,e=map(int,input().split())
    A[s].append(e) #무방향이기에 양쪽 edge 추가
    A[e].append(s)

count=0

for i in range(1,n+1):
    if not visited[i]:
        count+=1
        DFS(i)

print(count)

• 1541번 잃어버린 괄호

  
  

answer=0
A=list(map(str,input().split('-'))) #55-50+40+30+20-30+30+30

def mysum(i): # i가 55 / 50+40+30+20 / 30+30+30
    sum=0
    temp=str(i).split('+') # 55 / 50,40,30,20 / 30,30,30
    for i in temp:
        sum+=int(i) # sum = 55 / 50+40+30+20 / 30+30+30 
    return sum

for i in range(len(A)): #A가 ['55', '50+40+30+20', '30+30+30'] 형태면 for문 3번 돔
    temp=mysum(A[i])  #mysum(A[i]) 호출 시 순서대로 55 / 50+40+30+20 / 30+30+30 들어옴
    if i==0: #첫번째 즉 -를 만나기 전 첫번째 값이라 더하고
        answer+=temp
    else: #나머지 값들은 -를 만난 뒤의 값들이기에 뺀다
        answer-=temp
     
print(answer)

1) 입력 예시 : 55-50+40+30+20-30+30+30
2) - 를 기준으로 잘라서 list 형태로 저장 -> ['55', '50+40+30+20', '30+30+30']
3) mysum함수로 + 기준으로 잘라서 sum 값에 누적해서 더함
4) sum을 반환하기에 - 기준으로 list 형태로 잘라놓은걸 다시 + 기준으로 자른 후 정수형태로 더해놓은 값이 반환됨 -> 55 / 50+40+30+20 / 30+30+30
5) - 기준으로 잘라놓은 list인 A 를 기준으로 for 문이 도는데 i=0 일때의 temp는 식 자체의 첫번째 값이기에 더해주고 나머지 temp들은 빼주게 되면 - 를 기준으로 묶어서 계산하게 되는 꼴
--> 55-(50+40+30+20)-(30+30+30)

백준(자습)

• 10809번 알파벳 찾기

  
  

s=input()
for i in 'abcdefghijklmnopqrstuvwxyz':
    print(f'{s.find(i)}',end=' ')

cf) ord와 chr 함수 사용하여 아스키 코드로 변환해서 2중 for문으로 풀다가 문제 티어가 브론즈5임을 직시하고 뭔가 접근 자체가 잘못됐다고 판단함...
문제를 잘 읽어보니.. 포함되어 있지 않은 경우에 -1 출력을 보니 아 find 쓰란소리구나 하고 정신차리고 다시품..
1) 파이썬의 특권인 for i in 문자열로 알파벳 소문자만큼 반복문 돌리면서
2) 입력한 문자열.find(알파벳 문자열) 로 찾으면 내가 입력한 문자열에서 같은 문자를 찾으면
내가 입력한 문자열에서 찾는 문자가 몇번째에 있는지 찍어줌 / 아래 소스 참조

#print('baekjoon'.find('a')) # 1
#print('baekjoon'.find('b')) # 0

• 10810번 공 넣기

  
  

m,tc = map(int,input().split()) # 5 4 
emp=[0 for i in range(m)] #emp:[0,0,0,0,0]
for _ in range(tc): 
    i,j,k=map(int,input().split())
    for num in range(i-1,j): # 1 4 1 
        emp[num]=k #emp[0] = 1 / emp[1] = 1 ... emp[3] = 1 

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

cf) 앞으로 메모장 / 수기로 문제를 이해하는 시간을 좀 가져야할듯
1) m,tc 입력받아 m칸짜리 list emp생성
2) tc만큼 반복하며 i,j,k 입력
3) i,j,k가 1 4 1 이라면 1번바구니~4번바구니 모두 1 집어넣음
4) emp는 list형태이기에 0번바구니~3번바구니에 1을 집어넣어야 한다고 생각해야함
5) i-1,j 까지 반복하며 k 를 넣어주게되면 ex) 1 4 1 --> emp[0]...emp[3] = 1 로 저장

• 1920번 수 찾기

  
  

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

m=int(input())
arr2=list(map(int,input().split()))

for num2 in range(len(arr2)):
    for num1 in range(len(arr1)):
        if arr2[num2]==arr1[num1]:
            print('1')
            break
        if num1==len(arr1)-1:
            print('0')

--> 제출했는데 시간초과 뜸.. 이진탐색 말고 그냥 이중포문으로 하면 안되는걸까!!! 다시 풀어야함

• 10813 공 바꾸기

  
  

m,tc=map(int,input().split()) # 5 4 
emp = [i+1 for i in range(m)] # emp : [1,2,3,4,5] 
for _ in range(tc):
    i,j=map(int,input().split())
    temp=emp[i-1]
    emp[i-1]=emp[j-1]
    emp[j-1]=temp

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