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
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))
'Today I Learned' 카테고리의 다른 글
[TIL] 11.20 ~ 11.26 (0) | 2023.11.20 |
---|