앱등개발자IOS

BFS문제중에서는 신박한 문제였던 것 같다. 뿐만 아니라, DFS, BFS 또는 union-find 알고리즘으로 각 노드의 parent를 체크하고, Set()자료형을 이용해 마무리할 수도 있는 문제이다. 출제자 의도대로 BFS로 풀이해보았다. 각 노드를 모두 나타낼 수 있도록 n+1크기만큼의 visited배열을 만들어놓은 후, 30 번째 줄부터, 1번 ~ n번 노드를 모두 돌며, 1. visited여부가 false인 노드가 나타나면, 2. 해당 노드의 visited = true로 설정해주고 3. 해당 node를 출발 node로 하여 bfs함수를 호출하여, 연결된 모든 node의 visited를 true로 바꿔준다 4. 이렇게 반복문에서 visited가 false인 node를 만날 때마다 count를 1 ..

Swift알고리즘 2022. 6. 3. 15:28

전형적인 DP문제이다. 한가지 포인트는, dp배열이 하나의 원소만을 갖고있는 것이 아니라, [0,0]과 같이 두개의 원소로 초기화되어있는 것. 해당 칸이 i번째 칸이라면, 앞쪽 인덱스는, i-2번 칸에서 i번 칸으로 진행해왔을 때의 최댓값. 뒷쪽 인덱스는, i-1번 칸에서 i번 칸으로 진행해왔을 때의 최댓값이다. 이렇게 나누어 저장한 이유는, "3개의 연속된 계단"을 밟으면 안되기 때문에, 이를 점화식에서 방지해주기 위함이다.

Swift알고리즘 2022. 6. 3. 15:04

아직 Swift로 알고리즘 코드를 작성하면 컴파일에러가 뜨는 경우가 적지 않다.... python에 익숙하다보니 여러모로 쉽지 않지만 이제는 Swift로 아예 갈아타야하는게 맞는 것 같다!! 큰 동전부터 작은 동전 순으로 접근하여 남은 금액과 나눗셈을 하여 몫을 취해 count에 더해준 후, 그 나머지를 다시 남은 금액에 할당해준다. 모든 동전에 대해 진행하면, 잔돈 동전의 "최소" 갯수를 구할 수 있다. ==> 이는 동전의 단위가 서로 약수, 배수 관계에 있기 때문이다! 그렇지 않다면 그리디 알고리즘으로 풀이할 수 없다!!

Swift알고리즘 2022. 6. 3. 14:33

지금 i번째 집을 칠할 때 우리는 무엇을 신경써야할까?? 앞, 뒤? 뒷 집을 무슨 색으로 칠할지는 그 때 가서 생각하자! 현재 집을 초록색으로 칠하고싶다면, 그 최솟값은 앞집을 파랑색으로 칠한 경우, 빨간색으로 칠한 경우 이 두가지 경우중 min값을 선택하여 현재 집을 초록색으로 칠할 때 드는 비용에 합쳐 저장한다. 같은 방식으로 두 번 더 진행하면, 현재 집을 앞 집과 색깔이 겹치지 않으면서, 해당 집을 각각 R, G, B로 칠할 때의 최소 비용을 구할 수 있다. 마지막에 result에서 최솟값을 취해줘야 모든 집을 칠하는 최솟값을 구하게 되는데, 배열의 최소, 최대를 .max(), .min()으로 가져올 때는 항상 Optional()타입으로 가져오므로 !로 언래핑을 해줘야한다!

Swift알고리즘 2022. 6. 2. 00:18

Dynamic Programming!! 문제이다. DP는 혼자 있을 때보다 Dijkstra나 DFS, BFS와 같은 친구들과 섞이는 순간 난이도가 확 올라가는 것 같다. 그런 아이들을 풀이하려면 일단 DP만 쓰는 이런 기본 문제들을 잘 풀어야할 것이다! 항상 초기 값들에 대해서는 index out of range오류가 날 것을 생각하여 출력 후 exit(0) 혹은 python에서는 quit() / exit()을 해주어 종료시켜줘야한다. 이후는 점화식을 세워 반복문을 우리가 필요로하는 n까지 돌려주면 된다! python에서는 상관없지만 dp배열에 저장하며 미리미리 10007로 나눠주지 않으면 overflow가 날 수 있으므로 주의하자!

Swift알고리즘 2022. 6. 1. 23:58

이전에 풀이했던 백준 : 거스름 돈 과 동일한 풀이로 해결할 수 있는 Greedy 기본 문제이다. 버튼을 누르면 늘어나는 시간을 배열에 내림차순으로 담아, 몫을 취하고, 나머지 연산을 해주어 n에 갱신해주면 된다.

Swift알고리즘 2022. 6. 1. 23:31

Greedy 알고리즘 문제이다. 핵심은 rope배열에 오름차순으로 정렬을 하고, 맨 왼쪽에서부터 조회를 해나가면, 조회된 로프가 버틸 수 있는 하중이 해당 상황에서의 "최대 하중"이 되므로, "최대 하중" * 남은 로프 수 ( 남은 로프 수는 n -> n-1 -> n-2...... 1) 위와 같이 진행하며 모든 경우에서 최대치를 구해 return해준다.

Swift알고리즘 2022. 6. 1. 23:10

지난 주 Swift로만 응시해야하는 코딩 인터뷰를 준비하며 한참 Swift로 알고리즘 풀이를 하면서.. Dijkstra를 제외하고는 알고있는 모든 알고리즘에 대하여 Swift로 풀이를 해보고 (Heapq를 지원해주지 않는 Swift...) 어느정도 Swift 알고리즘 풀이도 python으로 풀이하는 것만큼 실력이 올라왔다고 느꼈지만, 며칠 놓아버리니 금방 이것저것 다 잊어버린 것 같다... 이 문제는 기본 Greedy문제인데, python으로 요 며칠 풀이하다 돌아오니, 변수명 앞에 var, let 붙여주는 것이 또 어색하게만 느껴졌다. 배열에 잔돈 단위를 큰 순서로 담아두고, 차례대로 몫을 취해 result에 더하고, 나머지만을 n에 남기는 방식으로 진행했다.

Swift알고리즘 2022. 6. 1. 22:59