분류 전체보기 (400) 썸네일형 리스트형 [BOJ] 백준 11725 트리의 부모 찾기 (Swift) 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 문제 그대로 트리에서 각 노드의 부모를 찾는 문제입니다. 루트노드를 1로 정하였으므로, 입력에서 주어진 간선들을 연결시켜 줍시다. 1에서부터 BFS, DFS를 사용해서 노드들에 대해서 탐색한다면, 다음 탐색할 노드가 현재 노드의 자식노드가 됩니다. 트리의 부모를 찾기 위해 parent라는 Int 배열을 사용하였고, 값을 -1로 초기화하였습니다. 인덱스를 현재 노드, 값을 부모 노드의 번호로 사용하려고 합니다. parent[4] = 3 이라면, 4의 .. [BOJ] 백준 11780 플로이드 2 (Swift) 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드워셜 알고리즘으로 풀이할 수 있는 문제입니다. 경로를 확인하기 위해 routes[1][5] = [1, 3, 5]와 같이 3차원 Int 배열을 사용하였습니다. 1에서 5로 가는 루트는 1 -> 3 -> 5 를 나타낸 것입니다. 초기의 버스와 버스 사이의 비용은 임의로 큰 수를 넣어주었고, A 도시와 B 도시의 비용을 입력받을 때, 비용을 갱신해주었습니다. 다만 주의해야할 점으로.. [BOJ] 백준 11779 최소비용 구하기 2 (Swift) 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘으로 풀이할 수 있는 문제입니다. 기본적인 다익스트라 알고리즘으로 최소 비용을 구할 수 있습니다. 배열의 인덱스와 값을 갖고 경로를 추적할 수 있도록 routes라는 Int 배열을 선언해주었습니다. routes[5] = 4 라면 4번노드에서 5번노드로 이동하였다는 방식으로 사용했습니다. A -> B로 이동할 때, 최소 비용으로 갱신 된다.. [BOJ] 백준 9019 DSLR (Swift) 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 이 문제는 BFS로 풀 수 있는 문제입니다. A에서 B로 변환하는 4가지 과정에 대해 모두 수행해서 최소의 연산을 출력해주는 문제입니다. 저는 DSLR 연산을 Int의 extension으로 작성을 하였습니다. BFS를 수행하면서, queue에 명령어를 String으로 넣어줬는데 시간초과 판정을 받았습니다. String 값을 더해주는 것도 $O(1)$이지만, 일반적으로 정수 .. [BOJ] 백준 13913 숨바꼭질 4 (Swift) 문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 X에서 X - 1, X + 1, 2 * X 의 방향으로 이동하는 경우 모두 1초가 걸리기 때문에, BFS로 최단비용를 구할 수 있습니다. 최단거리로 간 루트를 구하기 위해 visited라는 Int 배열을 선언하였습니다. 이 Int 배열의 index를 현재 위치, 값을 이전 위치로 사용하려고 합니다. 예를들어 visited[10] = 9 라면, 9에서 출.. [디자인 패턴] 팩토리 패턴에 대해 알아보기 (Swift) 1. 팩토리 패턴이란? 객체 생성 부분을 따로 두어 추상화하고, 인스턴스를 생성할 클래스를 서브클래스에서 결정하는 패턴입니다. 맨처음 말로만 들었을 때, 잘 이해가 가지 않았습니다. 예를들어, 내가 햄버거 가게를 오픈을 했는데 처음에는 불고기버거만 만들줄 알았다고 가정해봅시다. 그렇다면 불고기 버거 인스턴스를 만들 class를 선언을 해야합니다. 이제 버거 기술이 발전해서 새우버거랑 치킨버거도 만들 수 있게 되었습니다. 그렇다면 새우버거, 치킨버거 class도 선언을 해주어서 인스턴스를 생성해주어야겠네요. 이러한 버거들을 (인스턴스) 불고기버거, 새우버거, 치킨버거를 생성하는 것을 서브클래스에서 결정을 해주는게 팩토리 패턴입니다. 이 인스턴스를 생성하는 것을 팩토리 클래스에서 생성하여 반환하게 됩니다. .. [디자인 패턴] 싱글톤 패턴에 대해 알아보기 (Swift) 1. 싱글톤 패턴이란? 하나의 클래스에 오직 하나의 인스턴스를 갖는 디자인 패턴입니다. Dog라는 클래스를 하나 만들고, 인스턴스를 생성해주었습니다. dog1과 같은 인스턴스를 참조하기 위해 dog2라는 변수를 두었고, 참조가 같은지 확인하였습니다. dog2의 name도 변경해보고 dog1의 name이 변경되었는지 확인을 해보았습니다. 같은 인스턴스에 접근을 하고있다는 것을 확인할 수 있습니다. Dog 클래스를 통해 인스턴스를 하나 더 생성을 하고 dog3라는 변수로 두었습니다. 당연하게도 dog3는 dog1과 dog2와는 다른 인스턴스 일 것입니다. 싱글톤 패턴을 사용하면 하나의 클래스에 오직 하나의 인스턴스를 갖기 때문에 Dog 클래스로 생성한 인스턴스는 다 같은 인스턴스가 될 것입니다. Swift에.. [BOJ] 백준 9252 LCS 2 (Swift) 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 이차원배열을 사용해 LCS의 길이를 구한 후, 오른쪽 구석에서 부터 탐색하여 문자열을 구할 수 있습니다. 소스코드 후기 LCS의 길이를 구하는 문제는 이미 풀어봤지만, 문자열을 어떻게 구할 수 있을지 2차원 배열을 확인하면서 풀이를 유추할 수 있었습니다. 이전 1 ··· 12 13 14 15 16 17 18 ··· 50 다음
