도지와 나

[백준] 5639.이진 검색 트리 (Swift) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 전위순회 입력대로 트리를 구성하여 후위순회로 출력하는 방법은 시간초과가 발생합니다. 따라서 전위순회 결과에서 규칙을 찾는 과정이 필요한 문제입니다. 전위순회는 루트 노드로부터 시작해 왼쪽 자식, 오른쪽 자식 순으로 진행되기 때문에 전위순회의 가장 첫번째 값은 루트 노드가 됩니다. 이진 탐색 트리의 특성 상 왼쪽 자식은 루트노드보다 ..

[백준] 1655.가운데를 말해요 (Swift) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 시간복잡도를 고려해야하기 때문에 힙을 사용하는 문제입니다. 풀이를 위해선 최대힙과 최소힙을 모두 사용하는데, Swift 는 힙 자료구조를 제공하지 않아 직접 구현해야 합니다. 힙에 관한 설명과 Swift 를 이용해 작성된 코드는 아래 링크에서 확인하실 수 있습니다. https://trumanfromkorea.tistory.com..

[백준] 1790.수 이어 쓰기 2 (Swift) https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 풀이 입력값의 최대 크기가 1억이기 때문에 단순히 문자열을 이어붙여서 탐색하는 방법으로는 문제를 해결할 수 없습니다. 그래서 규칙을 찾아야 하는데, 이 문제에서 찾을 수 있는 규칙은 다음과 같습니다. 1자리 숫자 1~9 는 총 9개가 존재합니다. 2자리 숫자 10~99 는 총 90개가 존재합니다. 3자리 숫자 100~999 는 총 900개가 존재합니다. 4자리 숫자 1000~99..

[백준] 2467.용액 (Swift) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투포인터로 해결할 수 있는 문제입니다. 용액들의 값은 정렬된 상태로 주어지기 때문에 특성값이 0에 가까워지려면 더해지는 두 용액의 절대값의 차이가 작아야 합니다. 그렇기 때문에 초기 포인터는 양쪽 끝, 즉 최소값과 최대값을 가리키고 있어야 합니다. 2개의 포인터가 가리키는 값을 더한 다음 절대값을 씌워줍니다. 해당 값이 작을수록 0에 가깝다는 의미이..

[프로그래머스] 광고 삽입 (Swift) https://programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 풀이 시청시간이 가장 많이 겹치는 경우를 찾아야 합니다. 그러기 위해서 입력받는 모든 시간을 초로 환산하였습니다. 전체 구간의 크기만큼 배열을 생성하여 시청시간들의 시작과 끝까지 1 씩 증가시켜주었습니다. 이렇게 되면 아무도 시청하지 않은 구간은 0,..

[백준] 1484.다이어트 (Swift) https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 풀이 문제에서 나오는 G 는 (현재)^2 - (예전)^2 으로 표현할 수 있습니다. G 가 자연수이기도 하고 문제를 읽어보면 현재 몸무게가 예전 몸무게보다 값이 크다는 것을 알 수 있습니다. 문제의 조건을 만족하는 모든 경우의 수를 출력해야하기 때문에 예전 몸무게를 1, 현재 몸무게를 2라고 생각하고 차례차례 탐색해보겠습니다. (현재)^2 - (예전)^2 라는 식을 조건..

[백준] 5014.스타트링크 (Swift) https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 시작층에서 목표층까지 도달하기 위해 버튼을 눌러야하는 최소 횟수를 구해야 합니다. 버튼은 위, 아래 2개가 존재하기 때문에 현재 있는 층에서 위로 가는 버튼을 누른다, 아래로 가는 버튼을 누른다 2가지 경우의 수를 생각해볼 수 있습니다. 이렇게 생각하면 간단하게 구현할 수 있을 것 같지만, 신경써야 하는 점이 크게 2가지가 있습니다. 이미 방문한 층에서는 어떤 ..

[자료구조] Swift 로 Heap 구현하기 Heap 은 이진트리 형태의 자료구조로 최대값 및 최소값을 빠르게 탐색할수 있도록 설계되었습니다. Heap 에는 2가지 종류가 있는데, 부모노드의 키값이 자식노드의 키값보다 항상 큰 경우는 Max Heap, 부모노드의 키값이 자식노드의 키값보다 항상 작은 경우는 Min Heap 이라고 합니다. 그렇기 때문에 Max Heap 의 루트노드에는 항상 최대값이 저장되고 Min Heap 의 루트노드에는 항상 최소값이 저장됩니다. Heap 은 이진트리 형태로 구현되었기 때문에 삽입과 삭제에서 O(logN) 의 시간복잡도를 가집니다. 삽입 MaxHeap 을 예로 들어보겠습니다. Heap 의 삽입은 트리의 가장 바깥쪽 노드에서 시작됩니다. 먼저 삽입할 노드를 트리의 가장 바..

[프로그래머스] 가장 먼 노드 (Swift, Java) https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 1. BFS 일단 문제를 읽고 1번 노드와 모든 노드간의 거리를 구해야했기 때문에 가장 가까운 노드부터 탐색하는 BFS 를 이용해야겠다고 생각했습니다. 노드의 탐색은 BFS 를 이용하면 비교적 간단하게 구현할 수 있지만, 가장 먼 노드의 개수를 알아야 했기 때문에 노드간의 거리를 계산하는 것이 문제의 핵심이라고 생각했습니다. 2. 거리 계산 거리계산을 위해 각 노드마다 1..

[프로그래머스] 다리를 지나는 트럭 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 풀이 1. 다리 현재 다리 위에 어떤 트럭들이 올라가 있는지에 대한 정보를 저장할 수 있는 자료구조가 필요했습니다. 먼저 다리를 건너기 시작한 트럭이 먼저 다리를 다 건너기 때문에 큐를 활용할까 생각했지만, 각 트럭이 다리에 머물러 있는 시간을 세는 방식이 애매하다고 생각하였습니다. 다..