앱등개발자IOS

백준 1005: ACM Crafe (위상정렬 / with Python)

Python알고리즘 2023. 10. 18. 23:45

백준 14567: 선수과목 (Topology sort / with Python)

Python알고리즘 2023. 10. 18. 21:56

백준 2531: 회전 초밥 (투포인터 / with Python)

Python알고리즘 2023. 10. 17. 22:30

백준 9251: LCS (Dynamic Programming / with C)

C알고리즘 2023. 10. 17. 21:39

백준 2211: 네트워크 복구 (Dijkstra / with Python)

다익스트라를 사용하면서, 약간의 MST(최소 신장 트리) 개념을 섞어야하는 문제였다.

Python알고리즘 2023. 10. 14. 18:45

백준 1719: 택배 (Floyd-Warshall / with Python)

Point 1. result 배열 초기화를 어떻게 해야하는지, 2. 거리를 갱신할 때, 어떤 값으로 result배열을 바꿔줄 것인지 ( 1-2-3-4의 경로의 경우, 1->4 즉 result[1][4] = 2가 되어야한다. 그런데 1-2-3 경로는 이미 압축되어있고, 1-3-4거리가 압축되면서 1과 4 사이 거리 최단 경로를 확정짓게 된다. 이 때, result[1][4]를 어떻게 2라고 값을 채워넣을 것인가!?) 2. Floyd-Warshall을 사용하며 1-1-3 과 1-3-3 처리를 어떻게 해줄 것인지.

Python알고리즘 2023. 10. 14. 16:58

백준 1967: 트리의 지름 ( BFS / with Python)

문제를 읽고나면, 모든 노드 간 거리를 구해, 그 중 가장 긴 거리를 답으로 내면 될 것이라 생각하여 "Floyd-Warshall"알고리즘을 사용해야하는 문제로 생각할 수 있다. 가능하겠지만, 메모리 제한에 무조건 걸리게 된다. (4Byte * 10000 * 10000)하면 이미 400MB를 넘어가기 때문.. ) 가장 중요한 포인트는 "BFS로 진행을 하되, BFS의 input으로 leaf노드들만 넣어주면 된다는 것"이다. 그마저도 python3로는 시간초과 판정이 나오니, pypy3으로 제출하였다.

Python알고리즘 2023. 10. 14. 16:20