꽁치대디의 개발일기

[백준] 14888.연산자 끼워넣기 (Swift) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 백트래킹으로 해결할 수 있는 문제입니다. 각 연산자의 개수가 들어있는 배열을 입력받고 나서 백트래킹을 이용해 모든 경우의 수를 탐색합니다. 연산자를 이용해 계산한 값과 현재 몇 번째 연산을 진행하는지에 대한 정수를 메소드 인자로 하여 재귀함수를 작성합니다. 연산자 배열을 탐색하며 값이 존..

[백준] 9012.괄호 (Swift) https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 스택을 이용해 해결할 수 있는 간단한 문제입니다. 괄호는 무조건 한 쌍으로 이루어져야 하며 괄호가 열리면 무조건 괄호는 닫혀야 합니다. 스택을 이용해 괄호의 유효성을 판단하는것은 굉장히 간단합니다. ( 가 나오면 스택에 push 하고 ) 가 나오면 pop 하는 것이 전부입니다. 하지만 pop 할 시 스택이 비어있다면 해당 괄..

[백준] 7453.합이 0인 네 정수 (Swift) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 1. 나눠서 풀기 크기가 최대 4000인 배열을 4개 이용해야 하기 때문에 완전탐색을 이용한다면 시간복잡도는 O(n^4) 이 되어 절대 테스트를 통과하지 못할 것입니다. 그래서 저는 4개의 배열을 두 개씩 묶기로 했습니다. 배열 A, B 에서 나올 수 있는 모든 수의 합, 배열 C, D 에서 나올 수 있는 모든 수의 합을 ..

[백준] 18808.스티커 붙이기 (Swift) https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 1. 배열 비교 먼저 스티커 자체를 배열에 붙일 수 있는지 없는지를 확인해야 했기 때문에 스티커의 크기만큼 배열에서 인덱스를 이동하며 탐색하였습니다. 맨 처음에는 확인하려는 범위의 첫번째 인덱스, 즉 맨 좌측 상단이 1로 채워져 있으면 스티커를 붙일 수 없다고 생각했습니다. 하지만 스티커의 첫번째 인덱스는 항상 1이 아니고 0일 수도 있기 때문에..

[백준] 2461.대표 선수 (Swift) https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 풀이 각 배열마다 수를 하나씩 뽑아 그 중 최대값과 최소값의 차이가 제일 작은 경우를 구하는 문제입니다. 처음에는 Heap 을 이용해 최소값을 모두 뽑은 다음, 최대값과 최소값의 차이를 계산한 뒤 그 중 최소값들을 삭제하고 다시 값을 뽑는 식으로.. 진행할 계획이었습니다. 입출력 예시는 모두 맞았지만, O(n^2) 정도로 코드를 작성하다보..

[백준] 2564.경비원 (Swift) https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 풀이 탐색할 좌표들은 주어진 사각형의 가장자리에만 위치하고 있습니다. 저는 일단 이 좌표들을 2차원 배열 위에 옮겼습니다. 좌표들은 칸이 아닌 점에 위치하고 있기 때문에 행과 열의 개수는 하나씩 더 크게 선언해주었습니다. 문제의 입출력 예시를 2차원 배열에 저장한 것은 아래와 같습니다. 하지만 이렇게 되면 좌표간의 거리를 계산하는것이 매우 복잡해지기 때문에 저는 ..

[백준] 19238.스타트 택시 (Swift) https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 BFS 를 이용한 최단거리 계산 문제입니다. 같은 거리에 있는 승객이 여러명이라면 행의 크기가 가장 작은 승객을, 그마저도 여러명이라면 열의 크기가 가장 작은 승객을 태우는 것이 문제의 조건입니다. 이를 해결하기 위해서 먼저 BFS 로 모든 승객과의 거리를 계산한 후에 최소거리에 있는 승객을 추려냈습니다. ..

[백준] 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..