[TIL] 11.13 ~ 11.19

2023.11.13 ~ 2023.11.19

 

---

11.13 월

 

😀  파이썬 출력 포맷팅

정수 %d

문자열 %s

소수점 3자리까지 %0.3f 

print("문자열 %s 문자열" %출력값)
print("문자열 %s %d %s " %(1번째, 2번째, 3번째))

print("{0} 문자열".format(출력값))
print("{0} {1} 문자열".format(출력값1,출력값2))

 

 

 

😀  프로그래머스 - lv.3 단어변환 (BFS/DFS)

내가 처음 생각한 방법: DFS 스택 활용

그리고 문제를 제대로 안읽었었다!!! begin은 아니지만 target은 words 안에 존재해야함

 

더 좋은 방법: BFS 큐 활용 -> 최단거리 구하는 것의 일종임!

[단어, 깊이] 형식으로 큐에 넣기

 

어려운점...-.- 순서가 상관이 없나...??????

dfs: https://mungto.tistory.com/53

https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98BFSDFS-C-v5lnyekn

bfs: https://naa0.tistory.com/153

 

 

 

😀  SWEA - D3 view

진짜 이유를 모르겠는데 리스트 입력받는 곳에서 컴파일 에러가 자꾸 나서 한참 속썩었다 대체 왤까?

 

😀  SWEA - D3 Flatten

정직하고 단순한 방법으로 풀었다

 

😀  SWEA - D3 최대상금----> 실패했다!!!! 생각보다 까다로운 문제인듯

댓글에 이 문제를 그리디, DP, DFS 등 다들 다른 알고리즘으로 풀었다는 사람들이 많아서 신기하다 대체 이 문제를 보고 어떻게 그런 알고리즘으로 연결시키지 

 

 

 

---

11.14 화

 

---

11.15 수

sdc다녀옴

---

11.16 목

반성

 

---

11.17 금

 

DP도 그렇고 백트래킹도 그렇고 당시에 모른척 넘긴 문제들은 꼭 업보로 돌아오는듯 하다ㅠㅠ

SWEA - nqueen

백트래킹문제

 if (board[n] == board[i]) or (n-i == abs(board[n] - board[i])):
 # 좌우 또는 대각선에 있는지 확인

 

---

11.18(토)

SWEA - 회문1, 농작물 수확하기 

둘 다 무난한게 풀었음

근데 아무 알고리즘 사용하지 않고 이렇게 무식하게 풀어도 되는건가 싶음

 

 

---

11.19(일)

백준 1238 - 파티

다익스트라 알고리즘

 

1.출발노드설정

2.최단거리테이블 inf 초기화

3.미방문 노드 중 가장 가까운것 선택

4.테이블 갱신

 

입력받기: arr[출발지].append((도착지, 거리))

 

heapq 사용하기!!!!!!!!!!!

 

import heapq

#학생수, 도로수, 파티마을
n, m, x = map(int, input().split())
INF = 1e8

graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가

check = [0] * (n+1)
answer = [0] * (n+1)

#시작점, 끝점, 소요시간
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    

#집 -> 파티장소
for start in range(1, n+1):
    q = []
    heapq.heappush(q,(0,start))
    distance = [INF] * (n + 1)
    distance[start] = 0

    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue

        for nextnode, nextdist in graph[node]:
            cost = nextdist + dist

            if cost < distance[nextnode]:
                distance[nextnode] = cost
                heapq.heappush(q,(cost,nextnode))

    answer[start] = distance[x]

    
    
#파티장소 -> 집
q = []
heapq.heappush(q,(0,x))
distance = [INF] * (n + 1)
distance[x] = 0

while q:
    dist, node = heapq.heappop(q)
    if distance[node] < dist:
        continue

    for nextnode, nextdist in graph[node]:
        cost = nextdist + dist

        if cost < distance[nextnode]:
            distance[nextnode] = cost
            heapq.heappush(q,(cost,nextnode))

for i in range(1, len(answer)):
    answer[i] = answer[i] + distance[i]

print(max(answer))