[백준] 밀린 문제 풀기

🛒 문제

[ 1 ] 11724 : 연결요소의 개수

😥 시도 1 : 틀렸습니다
깊이우선탐색을 통해서 연결되어 있는 것들 모두를 탐색하는 방법을 진행했다. 딕셔너리를 이용해서 연결됨을 표현했고, 딕셔너리에 키를 하나씩 뽑아서 이미 탐색하지 않은 노드라면 그 노드들을 탐색하고 카운트를 하나 올리는 형식으로 하였는데 예제1에 경우 문제 없이 정답이 나왔으나, 예제2에서 전체적으로 큰 사이클이 하나 만들어짐에도 연결요소가 2개라고 나와서 고민을 많이 하게 되었다.

import sys
sys.setrecursionlimit(10000)

alredy = []
cnt = 0
def dfs(find):
    # 이미 거친건지 보고 안 거친거면 관련 자식들 빼자
    alredy.append(find)

    # 자식 노드로 계속 파고든다.
    try:
        if(inf[find] in alredy):
            print(find, '는 이미 있는데')
        dfs(inf[find])
    except:
        return

vertex, line = map(int, input().split())
inf = {}

for _ in range(line):
    a,b = map(int, input().split())
    inf[a] = b

for i in inf:
    if(i in alredy):
        continue
    dfs(i)
    cnt+=1
print(cnt)

😥 시도 2 : 틀렸습니다
고민을 좀 오래하다가 서칭을 해보니 나는 연결요소들을 서로 연결 시켜준 게 아니라 한 쪽 방향으로만 생각하고 양방향 연결을 해주지 않았다.
그저 1 : 2 -> 2 : 5 -> 5 : 1 이렇게만 생각을 해서 1 : 2,5 | 2 : 1,5 이렇게 서로간의 연결을 해주지 않았기 때문에 올바른 정답을 얻을 수 없었고 다시 수정을 통해 정답을 맞추었다. 그러나..채점을 하던 도 중 틀렸습니다가 나왔고 멘붕이 왔다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def make_dic(p, q):
    if p in graph:
        graph[p].append(q)
    else:
        graph[p] = [q]
        
alredy = []
cnt = 0
def dfs(find):
    # 이미 거친건지 보고 안 거친거면 관련 자식들 빼자
    alredy.append(find)

    # 자식 노드로 계속 파고든다.
    for i in graph[find]:
        if(i in alredy): continue
        else : dfs(i)

vertex, line = map(int, input().split())
graph = {}

for _ in range(line):
    a,b = map(int, input().split())
    make_dic(a, b)
    make_dic(b, a)

for i in graph:
    #이미 방문했다면 넘어가자
    if(i in alredy):
        continue
    dfs(i)
    cnt+=1
print(cnt)

😊 시도 3 : 맞았습니다.
시도 2에 비해서 새로 놓은 부분이 remainders = vertex - len(keys) 이 부분인데, 딕셔너리에 넣은 키 값들의 길이와 처음 시작할 때 넣은 vertex의 갯수의 차를 구해서 마지막에 더해주는 과정이 필요했다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def make_dic(p, q):
    if p in graph:
        graph[p].append(q)
    else:
        graph[p] = [q]
        
alredy = []
cnt = 0
def dfs(find):
    # 이미 거친건지 보고 안 거친거면 관련 자식들 빼자
    alredy.append(find)

    # 자식 노드로 계속 파고든다.
    for i in graph[find]:
        if(i in alredy): continue
        else : dfs(i)

vertex, line = map(int, input().split())
graph = {}

for _ in range(line):
    a,b = map(int, input().split())
    make_dic(a, b)
    make_dic(b, a)

keys = list(graph.keys())

for key in keys:
    #이미 방문했다면 넘어가자
    if(key in alredy):
        continue

    dfs(key)
    cnt+=1
remainders = vertex - len(keys)
print(cnt + remainders)

---

[ 2 ] 10773 : 제로

시도 1 : 맞았습니다

간단한 스택문제로 크게 어렵지 않게 해결할 수 있었다.

k = int(input())
money = []

for i in range(k):
    talk = int(input())

    if(talk == 0):
        money.pop()
    else:
        money.append(talk)

print(sum(money))

---

[ 3 ] 17298 : 오큰수

시도 1 : 시간초과
배열을 만들고 내가 원하는 인덱스에 접근해 pop을 1번한 값을 기억하고 같은 인덱스에 계속 팝을 진행시키며 기억한 값과 비교해서 만약 더 큰 값이 있으면 출력하고 종료 그렇지 않다면, 마지막 인덱스까지 도달했을 때 종료한다.

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

for i in range(n):
    temp_s = ary[:]

    # 해당 번째 인덱스를 팝
    value = temp_s.pop(i)
    # while문으로 해당 번째 인덱스 팝하고
    while(temp_s):
        if(i == n-1):
            print('-1')
            break

        compare_v = temp_s.pop(i)

        #print(value,':',compare_v)
        if(value < compare_v):
            print(compare_v, end=' ')
            break

        # 못 찾고 종료
        if(len(temp_s) == i):
            print('-1', end=' ')
            break
    
    

시도 2 : 틀렸다
단순 반복문을 통한 논리로는 절대 원하는 횟수 안에 끝나지 않을 것이란 것을 알았다. 그래서 큐 방식을 이용해 앞에서 한 개를 팝하고 그것을 cur에 저장한다. 그 후 자기 값보다 큰 값이 있으면 멈추고 지금까지 지나간 곳에 찾은 큰 값을 기록해두는 방식으로 진행해보았다.

그러나 이 방식은 9 4 5 1 같이 처음 나오는 9가 가장 큰 경우는 돌아갈 수가 없다..

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

n = int(input())
dq = deque(map(int,input().split()))

# 스택을 이용
# 오른쪽에서부터 숫자를 꺼내는 아이디어
# 타 배열에 꺼낸 걸 저장
# 진행 : 반복 (끝보다 1칸 앞 ~ 0까지) 팝하고 appendleft()
# 현재 꺼낸 것과 배열에 첫 부분부터 검사

save=[]
while(dq):
    cnt=1
    cur = dq.popleft()

    print(cur)
    if(len(dq)== 0):
        save.append(-1)
        break

    while(True):
        comp = dq.popleft()
        if (cur < comp):
            dq.appendleft(comp)
            break
        cnt+=1
    for i in range(cnt):
        save.append(comp)
print(save)

시도 3 : 틀렸습니다.
이유를 잘 모르겠다..테스트 케이스들도 만들어서 넣어봤는데 원하던 값이 안나왔다 잘 모르겠다. 다음 시간에 스터디원들이랑 같이 이야기해봐야겠다.

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

n = int(input())
dq = deque(map(int,input().split()))

save=[]


while(dq):
    cnt=1
    list_max = max(dq)
    cur = dq.popleft()

    # 현재가 가장 큰 경우 or 더 이상 팝할게 없으면
    if(cur == list_max or len(dq) == 0):
        save.append(-1)
        continue
    
    # 반복 : 큐가 남아있는 동안
    while(dq):
        # 비교 값 pop
        comp = dq.popleft()

        # 현재 값보다 더 큰 값 존재
        if (cur < comp):
            dq.appendleft(comp) # 빼낸 거 다시 넣고
            break
            
        # 넘어간 비교숫자 갯수 기록
        cnt+=1
    
    # cnt만큼 배열에 기록한다.
    for i in range(cnt):
        save.append(comp)

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

---

[ 4 ][G5][12865] 평범한 배낭

[3월 17일 해결]

못푼 문제 중 이 문제를 선택한 이유는 아무래도 내가 DP문제에 많이 약하다는 것을 내가 알기 때문이다. 해당 문제도 이전에 무게를 우선으로 그리디하게 접근을 하다가 같은 무게에 다른 가치일 경우에 틀릴 수도 있는 경우가 생겨서 이 방법으론 안되겠다 싶었고, 30분 정도 고민하다가 유튜브나 구글 서칭을 통해서 아이디어를 얻었다.

그 아이디어 조차도 이해하는데 조금 시간이 걸렸다. DP라는 문제 자체를 이해하는데 익숙해져야할 것 같아. 지금까지 접근한 DP들은 표를 그려서 보면 이해가 쉬워지는 느낌이다. 경우마다 값을 구하는데 애초에 맞지 않는 값이면 넣지 않는? 그런 느낌이다. 어림잡아 2시간정도 넘게 이해하고 스스로 코드를 짜보는데 시간이 걸렸다. 아직도 사실 감이 확실히 잡히지 않는다 DP 문제를 더 연습해야지..

import sys
input = sys.stdin.readline

# 모든 경우 : N 100일때 물건을 넣고 빼고 하는..총 2의 100승
# 불가능하니까 DP를 이용

n, k = map(int, input().split())
things = [[0,0]]
graph = [[0 for i in range(k+1)] for j in range(n+1)]

for _ in range(n):
    w,v = map(int, input().split())
    things.append([w,v])

for i in range(1, n+1):
    for j in range(1, k+1):
        w = things[i][0]
        v = things[i][1]

        # 그래프 채우자
        if(w > j): # 현재 한계 무게j보다 크면 못 들어가!
            graph[i][j] = graph[i-1][j]#이전 값
        else: # 들어갈 수 있다!
            graph[i][j] = max(graph[i-1][j], v + graph[i-1][j-w])

print(graph[n][k])

---

[ 5 ]