뭐든지 다 알아보자

https://www.acmicpc.net/problem/11724

VERSION 3.0 ==>연습연습!

import sys
sys.setrecursionlimit(10000) #최대 재귀한도
N , M = map(int,sys.stdin.readline().split())

edge = [ [] for i in range(N+1)]
visited = [False] * (N+1)
for i in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edge[u].append(v)
    edge[v].append(u)

def dfs(e):

    if not visited[e]:
        visited[e] = True
        for p in edge[e]:
            dfs(p)


count = 0
for j in range(1,N+1):

    if not visited[j]:
        dfs(j)

        count+=1
print(count)

#%%

VERSION 2.0

import sys

sys.setrecursionlimit(10000)

N , M  = map(int, sys.stdin.readline().split())

edge = [[] for i in range(N+1)]

visited = [False] * (N+1)
count = 0

for i in range(M):
    u,v = map(int, sys.stdin.readline().split())
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

def dfs(v):

    for e in edge[v]:
        if not visited[e]:
            visited[e] = True
            dfs(e)

for v in range(1, N+1):
    if not visited[v]:

        dfs(v)


        count+=1

print(count)



#%%

VERSION 1.0

import sys
sys.setrecursionlimit(10000)



N, M = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N + 1)]
#N = 6 , M = 5
#adj(EDGE) = [ [] [] [] [] [] [] [] ]
visited = [False] * (N + 1)
#visted = [ False , False , False , False , False , False , False]
count = 0

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    adj[u].append(v)

    adj[v].append(u)
    #u , v = 1 , 2
    #adj[1].append(2) ==> adj = [ [] [2] [] [] [] [] [] ]
    #adj[2].append(1) ==> adj = [ [] [2] [1] [] [] [] [] ]

    #u , v = 2 , 5
    #adj[2].append(5) ==> adj = [ [] [2] [1,5] [] [] [] [] ]
    #adj[5].append(2) ==> adj = [ [] [2] [1,5] [] [] [2] [] ]

    #u , v = 5 , 1
    #adj[5].append(1) ==> adj = [ [] [2] [1,5] [] [] [2,1] [] ]
    #adj[1].append(5) ==> adj = [ [] [2,5] [1,5] [] [] [2,1] [] ]

    #u , v = 3 , 4
    #adj[3].append(4) ==> adj = [ [] [2,5] [1,5] [4] [] [2,1] [] ]
    #adj[4].append(3) ==> adj = [ [] [2,5] [1,5] [4] [3] [2,1] [] ]

    #u , v = 4 , 6
    #adj[4].append(6) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [] ]
    #adj[6].append(4) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ]

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        #adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ]

        if not visited[e]:
            dfs(e)
# #visited = [ False , False , False , False , False , False , False]
#
for j in range(1, N + 1):
    if not visited[j]: #visited 가 False일때 , visited = [False , True , True , False,
        dfs(j)

        #j = 1
        #dfs(1)
        #visited[1] = True
        # for e in adj[1]=[2,5] , e= 2 , 5

        #visited[2] = False ==> dfs(2) , visited[5] = False ==> dfs(5)
        #dfs(2)
        #visited[2] = True
        #for e in adj[2] = [1,5] , e = 1 , 5

        #if not visited[1]= True'''' visited[5] = False
        #dfs(5)
        #visited[5] =True
        #for e in adj[5] = [2 , 1] , e = 2 , 1:

        #if not visited[2] = True , visited[1] = True


        #visited = [False , True , True , False, False , True , False]

        #count+= 1


        #j = 2
        #visited[2] = True

        #j = 3

        #visited[3] = False

        #dfs(3)
        #visited[3] = True
        #for e in adj[3] = [4]
        
        #if not visited[4] = False
        
        #dfs(4)
        #visited[4] = True
        #for e in adj[4] = [3,6] , e= 3 ,6
        
        #if not visited[3] = True , visited[6] = False
        #dfs(6)
        #visited[6] =True
        #for e in adj[6] = 4
        
        #if not visited[4] = True
        
        #visited = [False , True , True, True , True, True, True]
        #count+=1 = 2

        #j = 4
        
        #visited[4] = True
        
        #j=5

        #visited[5] = True

        #j=6

        #visited[6] = True
        
        count += 1

print(count) # count = 2

1. 인접한 요소에 따른 리스트 생성

==> 1번 요소는 2,5

==> 2번 요소는 1,5

==> 3번 요소는 4

==> 4번 요소는 3,6

==> 5번 요소는 2,1

==> 6번 요소는 4

3. DFS 선언 

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        #adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ] ==> adj[v]의 리스트 안에 있는 값이 2개일경우, e는 2개의 값을 받아 2번 실행하게 된다.

        if not visited[e]:
            dfs(e)

3. DFS 실행 ==> 재귀함수 실행

for j in range(1, N + 1):
    if not visited[j]: #visited 가 False일때
        dfs(j)

        #j = 1
        #dfs(1)
        #visited[1] = True
        # for e in adj[1]=[2,5] , e= 2 , 5

        #visited[2] = False ==> dfs(2) , ★visited[5] = False ==> dfs(5)
        #dfs(2)
        #visited[2] = True
        #for e in adj[2] = [1,5] , e = 1 , 5

        #if not visited[1]= True, visited[5] = False
        #dfs(5)
        #visited[5] =True
        #for e in adj[5] = [2 , 1] , e = 2 , 1:

        #if not visited[2] = True , visited[1] = True

★ visited[5] = False--> True


        #visited = [False , True , True , False, False , True , False]

        #count+= 1


        #j = 2
        #visited[2] = True

        #j = 3

        #visited[3] = False

        #dfs(3)
        #visited[3] = True
        #for e in adj[3] = [4]
        
        #if not visited[4] = False
        
        #dfs(4)
        #visited[4] = True
        #for e in adj[4] = [3,6] , e= 3 ,6
        
        #if not visited[3] = True , visited[6] = False
        #dfs(6)
        #visited[6] =True
        #for e in adj[6] = 4
        
        #if not visited[4] = True
        
        #visited = [False , True , True, True , True, True, True]
        #count+=1 = 2

        #j = 4
        
        #visited[4] = True
        
        #j=5

        #visited[5] = True

        #j=6

        #visited[6] = True

https://www.acmicpc.net/problem/11004

VERSION 2.0

==> 퀵정렬 해보자

VERSION 1.0

import sys

N, K = map(int,sys.stdin.readline().split(' '))

A = sorted(list(map(int , sys.stdin.readline().split(' '))))

print(A[K-1])

VERSION 2.0

import sys
from collections import deque
#p1 = 3 , p2 = 1 , p3 = 4 , p4 = 3, p5 =2  ==> 인출하는데 걸리는 시간

#[1,2,3,4,5] ==> 1번은 3분, 2번은 4분 , 3번은 3+1+4 = 8분 , 4번은 3+1+4+3= 11분 , 5번 13분
#3+4+8+11+13 = 15+24 = 39분

#[2,5,1,4,3] 순서 ==> 2번 1분 , 5번 1+2 =3분 , 1번 1+2+3 = 6분 , 4번 1+2+3+3 = 9
# 3번 1+2+3+3+4 = 13분 ==> 32분

#==시간이 작은거 순서대로 배열

N = int(sys.stdin.readline())

A = list(map(int,sys.stdin.readline().split(' '))) #인출하는데 걸리는 시간
A = deque(sorted(A))
B =deque()
res = 0
while len(A)>=1:
    a = A.popleft()
    # print(a)
    res+= a
    B.append(res)

print(sum(B))

==> DEQUE 활용하여 풀어보았다

VERSION 1.0

import sys

A= int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split(' ')))

B = sorted(B , reverse = False)
#print(B)

for i in range(len(B)-1):
    B[i+1] += B[i]

print(sum(B))

인출수가 적은 순서대로 하기위해 SORTED()함수 활용==> 누적합 알고리즘 활용 ==> SUM()함수 통해 구했다.

정렬알고리즘 참고 

https://www.acmicpc.net/problem/1377

VERSION 2.0

VERSION 1.0

import sys

N = int(sys.stdin.readline())
A = []
for i in range(N):
    A.append(int(sys.stdin.readline()))

for i in range(N-1):
    changed =False
    for j in range(N-1):
        if A[j]>=A[j+1]:
            changed = True
            idx = A[j]
            A[j] = A[j+1]
            A[j+1] = idx
            # print(A)
    if changed == False:
        print(A[i])
        break

==> 버블소트 BUT . 시간초과

https://www.acmicpc.net/problem/11286

import sys
import heapq

N = int(sys.stdin.readline())
res = []

for i in range(N):
    x = int(sys.stdin.readline())
    if x != 0:
        heapq.heappush(res , (abs(x) , x))
        print(res)
        #heapq.heappush(결과를 저장할 리스트 , (비교할 값_1) , (비교할 값_2 )
        #==> 우선순위에 따른 정렬을 해준다.
    else:
        if res:
            print(heapq.heappop(res)[1])
        else:
            print(0)

==> 리스트 res에 (우선순위 , 값) 으로 표현해준다.

==> x값이 0일경우에  heapq.heappop(res) 해주는데 ==> 우선순위가 높은거 부터 빼준다!!!!

VERSION 2.0

import sys

from collections import deque

#N장의 카드 , 1번이 가장 위 n번이 가장 아래

# 1 2 3 4 ==> 1버리기 ==> 2 3 4 ==> 2를 아래로 ==> 3 4 2
# 3 4 2 ==> 3 버리기 ==> 4 2 ==> 4를 아래로 ==> 2 4
# 2 4 ==> 2 버리기 ==> 4
N = int(sys.stdin.readline())
A = deque([i for i in range(1, N+1)])

while len(A) > 1:
    A.popleft()

    A.append(A.popleft())

print(* A)

==> DEQUE 으로 풀면 쉽다.

VERSION 1.0

import sys
from collections import deque

N = int(sys.stdin.readline())
queue = deque()
for i in range(N):
    queue.append(i+1)

while True:
    if len(queue) == 1:
        print(queue[0])
        break
    else:
        queue.popleft()
        # print(queue)
        queue.append(queue.popleft())
        # print(queue)

1. queue.popleft() 맨처음 위에꺼 삭제 

2. queue.append(queue.popleft()) ==> popleft() 먼저 실행 ==> 나중에 queue 에 적재 ==> 한번에 실행가능

https://www.acmicpc.net/problem/17298

VERSION 2.0

import sys

from collections import deque

N = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split(' ')))

res = [-1] * N
deque = deque()
deque.append(0)
for i in range(1, N):
    while deque and A[deque[-1]] < A[i]:
        res[deque.pop()] = A[i] #i값은 가만히 있고, deque값은 pop 되므로 작은 것들만 값을 바꿔준다.

    deque.append(i)

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

==> deque값을 인덱스화 하여 처리한다.

==> 결과값을 미리 -1로 추가한다.

VERSION 1.0

import sys
from collections import deque

N = int(sys.stdin.readline())

A = list(map(int , sys.stdin.readline().split(' ')))
B = deque()
for i in enumerate(A):
    B.append(i)
res = [-1] * N
for k ,v in B:
    p = k+1
    # print(k)
    # print(f' B[p][1] : {B[p][1]}')
    while p<=N-1:
        if B[k][1] <= B[p][1]:
            res[k] = B[p][1]
            break
        else:
            p+=1
for i in res:
    print(i , end = ' ')
#%%

==> while 문에 p<=N-1 해놓기 ==> 시간초과 난다.

https://www.acmicpc.net/problem/1874

import sys
from collections import deque

n = int(sys.stdin.readline())
a = deque()
for i in range(n):
    a.append(int(sys.stdin.readline()))
res = []
b = deque()
for i in range(1,n+1):
    b.append(i)
    res.append('+')
    while True:
        if len(b)==0:
            break
        if b[-1] == a[0]:
            b.pop()
            a.popleft()
            res.append('-')
        else:
            if i==n and len(b)>0:
                res =[]
                res.append('NO')
            break
for i in list(res):
    print(i)

==> i==n and len(b)>0

==> 마지막 찾을 값이 마지막이고, 연속된 배열에 숫자가 남아있는경우 while 문 계속돌아간다

==> res 값에 NO 붙여주고 BREAK 시켜준다.