PS/백준 (318) 썸네일형 리스트형 [BOJ] 백준 1240 노드사이의 거리 (Swift) 문제https://www.acmicpc.net/problem/1240풀이이 문제에서 명확하게 "트리" 라고 알려주었다."트리"는 무뱡항 그래프이다.DFS, BFS로 트리를 구현해서 풀 수 있겠다고 생각했다.DFS, BFS로 풀 때, 간선의 비용을 graph에 저장해두어야 겠다고 생각했다.그래서 그래프의 자료형을 [[(Int, Int)]] 형식으로 튜플의 2차원 배열로 선언해주어야겠다고 생각했다.물론 Struct나 Class, typealias 만들어줬어도 상관없다.첫번째로 풀이했을 때는 DFS로 풀어보았다.문제에서 간선의 개수는 노드의 개수 - 1 이고 같은 노드 번호는 주어지지 않으므로, 모든 노드가 연결되어있음을 알 수 있었다.startNode에서 DFS를 수행했다. startNode에서 DFS를 수.. [BOJ] 백준 2346 풍선 터뜨리기(Swift) 문제https://www.acmicpc.net/problem/2346풀이오른쪽으로 이동하는 것 (양수)인 경우에는array.append(array.removeFirst()) 를 통해 맨 앞으로 이동시킬 수 있다.주의할 점으로는 적힌 숫자보다 -1 만큼 이동을 시켜주어야 한다.예를 들어 다음과 같은 배열이 있을 때를 생각해보자.array = [2, -1, 1]가장 앞에 있는 2가 터지고 2만큼 뒤에있는 1이 터져야 할 상황이다.2가 터졌기 때문에 index가 자연스럽게 1이 줄어들게 된다.[-1, 1]array.append(array.removeFirst()) 수행 시 다음과 같다.[1, -1]한 번만 수행해도, 1이 가장 앞에 위치하는 것을 확인할 수 있다.왼쪽으로 이동하는 방식은 (음수) 다음과 같이 .. [BOJ] 백준 14502 연구소(Swift) 문제https://www.acmicpc.net/problem/14502풀이접근 방법그래프에서 0 -> 1로 변경시켜주어야 하는 작업이 필요할 것0 -> 1로 3개를 변경해주어야 하는 작업이 필요하기 때문에, 0의 위치들 중에서 3개를 뽑는 조합 알고리즘의 필요성을 느낌0의 위치를 배열로 담아주어야겠다고 생각함for문 3개로 0 -> 1로 바꿔주는 방법을 하려고 했지만 이 문제에서는 필요없겠지만 추후 확장성을 위해 조합알고리즘을 짜야겠다고 생각함0 -> 1로 3개를 변경했다면, 바이러스(2)에서 BFS를 수행해야겠다고 생각함2의 위치를 배열로 담아주어야겠다고 생각함BFS를 수행 이후 0의 개수를 세고 max 값을 찾는다. 그리고 0 -> 1로 바꿔준 부분을 되돌려주어야 함 (백트래킹)반복..이 문제는 n과.. [BOJ] 백준 28279 덱 2 (Swift) 문제https://www.acmicpc.net/problem/28279 풀이덱 자료구조는 이전에 포스팅 해두었다.구현해놓은 덱 자료구조를 가지고, 풀면 되는 문제..소스코드후기덱 자료구조만 구현한다면 쉽게 풀 수 있는 문제덱 구현하는게 쫌 귀찮고 까다롭다.. [BOJ] 백준 1389 케빈 베이컨의 6단계 법칙 (Swift) 문제https://www.acmicpc.net/problem/1389풀이이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.BFS의 시간복잡도가 어떻게 될까도 생각해봤다.$O(V + E)$ 라는 점, 최악의 경우 $O(100 + 5000)$ 이 될 것이라고 생각했다.또한 모든 친구($N$)에 대해 검사를 해봐야 하므로, $O(V * (V + E))$ 이지 않을까..?$100 \times 5100$라면 충분히 통과할 것이라고 생각했다.처음엔 다음과 같이 생각했다.1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지.. [BOJ] 백준 2745 진법 변환 (Swift) 문제https://www.acmicpc.net/problem/2745풀이사실 이 문제는 아주 간단하게 풀 수 있는 문제이다.Int 자료형에 다음과 같은 이니셜라이저가 존재한다.이거 하나면 바로 풀 수 있는 문제하지만 이 문제에서는 위와 같이 푸는것으로 의도하고 있지는 않은 것 같다.다른 방법으로 풀이하자면, 먼저 진법에 대한 이해가 필요한 것 같다.음.. 언제 배웠는지 기억은 잘 안나는데, 2진수를 10진수로 변환하는 과정에 대해서는 대부분 알 것이라고 생각한다.2진수 "110"을 10진수로 변환한다면, 2의 2제곱 * 1 (4) + 2의 1제곱 * 1 (2) + 2의 0제곱 * 0 (0) = 6 과 같이 변환할 수 있다.예제에 나온 "ZZZZZ" 를 36진수로 변환한다면..?"ZZZZZ"는 너무 기니깐.. [BOJ] 백준 18110 solved.ac (Swift) 문제 https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 풀이 문제만 잘 따라가면 쉽게 풀 수 있는 문제 먼저 제외할 상위 15%, 하위 15%의 명 수를 구해주어야 한다. Swift는 자료형이 까다로운 언어이므로 15%를 구하고 반올림을 하기위해서 형변환이 필요했다. 15%가 몇명인지 구한 후, removeFisrt(_ k:), removeLast(_ k:) 메서드를 사용하여 삭제시켜주었다. 그 이후, 평균을 구해주어.. [BOJ] 백준 10845 큐 (Swift) 문제 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 큐를 구현하는 문제 Swift에서는 Queue를 지원하지 않으므로 직접 구현해야 한다. 큐 자료구조에 대해 모른다면 다음 포스팅을 확인하고 와도 좋을 것 같습니다. https://dev-mandos.tistory.com/190 [자료구조] Queue에 대해 알아보고 구현해보기 (Swift) Queue란? Queue 자료구조는 선입선출(First In First Out)F.. 이전 1 2 3 4 ··· 40 다음
