도지와 나

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

[백준] 1976.여행 가자 (Swift, Java) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 1. BFS 입력은 인접행렬로 표현된 그래프가 주어지고, 마지막 줄에는 방문할 노드들이 순서대로 주어집니다. 처음에는 단순히 방문한 노드들을 차례대로 2개씩 뽑아서 BFS 를 진행할 생각이었습니다. 최단 경로가 존재한다면 true 를 리턴하고, 존재하지 않는다면 false 를 리턴하는 방식으로 접근하면 된다고 생각했습니다. 하지만 m 번만..

[프로그래머스] 네트워크 (Swift) https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 이차원 배열로 주어진 그래프 정보에서 총 그래프의 개수를 구하는 문제입니다. 해당 문제를 풀기 위해서는 한 그래프를 모두 탐색한 다음 그 횟수를 구하면 된다고 생각했습니다. DFS 나 BFS 모두 한번 실행할 시 그래프 전체를 탐색하지만 이번에는 DFS 를 활용해봤습니다. 그래프 탐색 여부를 저장하기 위해 먼저 ..