앱등개발자IOS

위상정렬 문제이다. 생각보다 헷갈릴 만한 포인트가 많이 들어가있는 문제이다. 1. 같은 숫자가 여러 번 나오는데, 이에 대한 처리를 어떻게 해줘야하는가? 2. 순서를 정하는 것이 불가능한 경우가 어떻게 생기는가?? 먼저 1번의 경우에는, 1 -> 3 2 -> 3 -> 4 2 -> 3 -> 5 과 같이 하나의 점으로 들어오는 경우가 많은 와중에, 2 -> 3 과 같이 동일한 것이 여러 번 나올 때는 나올 때마다 graph[2].append(3)해주면 된다. 이유? 어차피 위상정렬을 수행하면서 2가 queue에서 나오고, 2에서 들어가는 점들에 대한 indegree를 1씩 감소시킬텐데, 그 때 알아서 겹쳐서 제거될 것이기 때문! ( Graph가 set이 아닌 Array 형태이므로 걱정할 것 없음) 2번 같은..

Swift알고리즘 2023. 9. 8. 01:44

Swift알고리즘 2023. 9. 8. 00:50

if let을 사용하여, dict에 해당 key에 대한 value값이 있는지를 체크했다! dict의 keys 혹은 values는 type도 그 이름과 같다. 이를 Array로 사용하기 위해서는 Array()로 감싸서 형 변환을 해줘야한다.

Swift알고리즘 2023. 9. 7. 16:04

Greedy 알고리즘 분류에 들어가있는데, 풀이는 BFS로 할 수 있었던 문제였다. 진행이 될수록 숫자는 커지기만하니까 (2를 곱하거나 뒤에 1을 붙이는 두가지 모두) visited와 같은 배열은 필요가 없다.

Swift알고리즘 2023. 9. 7. 15:23

Swift알고리즘 2023. 9. 6. 23:24

POINT 그래프가 여러 조각으로 나뉘어 있을 경우, 모든 조각들에 대해 bfs를 돌렸을 때, true가 return되어야 전체적인 그래프가 "이분 그래프"라고 할 수 있다!!

Swift알고리즘 2023. 9. 5. 20:19

처음 했던 풀이는 1일에 3일 걸려서 10의 비용을 받을 수 있다면, dp배열의 3번째 인덱스에 저장해두었다. ( dp[3]에 저장) 그 이유는 3일차가 끝나면 그 금액을 가져갈 수 있다는 생각으로 비롯한 것이었는데, 그렇게 된다면, 원래는 그 금액을 받고서 4일차부터 새로운 상담을 할 수 있는 것인데, 3일차부터 겹쳐서 진행하는 논리가 되어 정답보다 더 큰 값이 정답으로 출력되었다. 이러한 저장 인덱스만 조정해주었더니, 문제가 해결되었다. ( 1일차에 3일 걸려서 20을 받을 수 있다면, 4번 인덱스부터 n-1 번 인덱스까지 max( 본인, 20) 과 같은 연산을 수행해준다.

Swift알고리즘 2023. 9. 5. 13:21

Swift알고리즘 2023. 9. 5. 12:46