도지와 나

[백준] 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 의 삽입은 트리의 가장 바깥쪽 노드에서 시작됩니다. 먼저 삽입할 노드를 트리의 가장 바..

[알고리즘] 동적 계획법 (Dynamic Programming) 다이나믹 프로그래밍은 하나의 큰 문제를 여러개의 작은 문제들로 나눠서 해결하는 방식입니다. 그렇기 때문에 다이나믹 프로그래밍을 이용하여 문제를 해결하려면 2 가지 조건을 만족해야 합니다. - 부분 반복 문제 (Overlapping Subproblem) 다이나믹 프로그래밍은 전체 문제를 여러개의 작은 문제들로 나눈 다음 그 결과값들을 이용해 전체의 답을 도출해냅니다. 그렇기 때문에 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능합니다. - 최적 부분 구조 (Optimal Substructure) 최적 부분 구조는 전체 문제의 최적해가 부분 문제들의 최적해로 이루어진 경우를 말합니다. 그렇기 때문에 특정 문제의 정답은 문제의 크기에 상..

[알고리즘] 탐욕법 (Greedy) 탐욕법이란 현재 상황에서의 최적해를 쫓는 알고리즘입니다. 하지만 현재 상황에서의 최적해만을 추구하는 것이 전체적으로 어떤 영향을 끼칠지는 고려하지 않기 때문에 항상 옳은 결과를 장담하지는 않습니다. Local minimum & Global minimum 그래프 위 시작점 X 에서 최소값을 찾는 프로그램을 작성한다고 할 때, 탐욕법을 이용한다고 가정해보겠습니다. 탐욕법은 앞서 말했듯이 현재 상황에서의 최적해를 찾는 알고리즘이기 때문에 시작점 X 에서 최소값을 찾으려면 무조건 지금의 값보다 낮은 왼쪽으로 향하게 될 것입니다. 왼쪽으로 진행하던 점 X 는 어느 순간 값이 커지는 변곡점을 맞게 될 것이고, 프로그램은 해당 변곡점을 그래프의 최소값이라고 생각할 것입니다. 하지만..

[프로그래머스] 가장 먼 노드 (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. 다리 현재 다리 위에 어떤 트럭들이 올라가 있는지에 대한 정보를 저장할 수 있는 자료구조가 필요했습니다. 먼저 다리를 건너기 시작한 트럭이 먼저 다리를 다 건너기 때문에 큐를 활용할까 생각했지만, 각 트럭이 다리에 머물러 있는 시간을 세는 방식이 애매하다고 생각하였습니다. 다..