본문 바로가기

Algorithm39

[Algorithm/BOJ] 2504 - 괄호의 값 Swift 문제풀이: 열린 괄호일 때, 문제의 핵심은 1로 초기화된 temp 변수를 이용하여 "("가 입력되면 2를 곱하고 "["가 입력되면 3을 곱하는 것이다. 또한, 스택에 현재 괄호를 추가해준다. 닫힌 괄호일 때, 스택이 비어있거나 스택의 가장 윗 부분이 해당 닫힌 괄호에 짝이 아니라면 bool 값을 토글하고 반복문을 빠져나옵니다. -> 올바르지 않은 경우 확인 현재 괄호 직전의 괄호( "(" )가 해당 닫힌 괄호( ")" )의 짝일 경우에만 현재 temp의 값을 결과 값에 더해준다. 아래의 그림처럼 그려보면 이해가 된다. temp를 해당 괄호에 따라 2를 나누거나 3을 나눠준다. 스택에 짝이 맞는 괄호를 꺼낸다. 이와 같이, 반복문이 다 돌고 bool값이 초기화한 값과 다르거나 스택이 비어있지 않다면 0을 .. 2021. 5. 1.
[Algorithm] LowerBound & UpperBound 다른 사람의 풀이를 확인하다가 몰랐던 새로운 알고리즘 발견했다. Lower Bound는 찾고자 하는 값 이상이 처음 나오는 인덱스를 찾는 것이다. Upper Bound는 찾고자 하는 값보다 큰 (초과) 값이 처음 나오는 인덱스를 찾는 것이다. 두 알고리즘 모두 이분탐색을 활용한다. func lowerBound(arr: [Int], start: Int, end: Int, target: Int) -> Int { var start = start var end = end while start < end { let mid = (start + end) / 2 // target 값보다 작을 때 start를 움직여 target보다 크거나 같은 첫번째 값의 인덱스를 찾는다. if arr[mid] < target { st.. 2021. 4. 29.
[Algorithm/BOJ] 5557 - 1학년 (DP) Swift 문제풀이: 완전탐색으로 접근하면 시간초과가 난다. 그러면 DP로 풀어야 하는데 DP는 항상 접근 방법을 찾기가 어려웠다. 이전의 숫자 정보와 덧셈과 뺄셈을 진행할 index를 필요로 해서 2차원 배열로 사용해야 한다. 위 그림과 같이 처음에 dp[0][8]을 시작으로 다음 수인 3을 뺀 결과와 더한 결과가 0보다 크거나 같고 20보다 작거나 같으면 dp에 값을 저장한다. 이후는 같은 과정으로 진행하고 마지막 수에 해당하는 경우의 수를 출력한다. 코드: let n = Int(readLine()!)! var nums = readLine()!.split(separator: " ").map { Int(String($0))! } var dp = [[Int]](repeating: [Int](repeating: 0,.. 2021. 4. 29.
[Algorithm/BOJ] 1806 - 부분합 (투 포인터) Swift 투 포인터는 배열을 순차적으로 접근할 때 2개의 포인터를 이용해서 처리하는 알고리즘입니다. 양의 정수로만 이루어진 수열의 부분합 또는 정렬되어 있는 두 배열의 합집합(병합 정렬)에서 사용됩니다 문제풀이: 시작점과 끝점이 0에 둔다. 현재 부분합이 S보다 작고 끝점이 수열 길이인 N보다 작다면, 끝점이 가리키는 수를 더하고 끝점을 증가시킨다. 현재 부분합이 목표 합계인 S보다 크거나 같다면, 길이를 배열에 추가하고 시작점을 증가시킨다. 모든 경우를 확인할 때까지 반복한다. 코드: let ns = readLine()!.split(separator: " ").map { Int(String($0))! } let n = ns[0] let s = ns[1] var nums = readLine()!.split(sep.. 2021. 4. 19.
[Algorithm/BOJ] 1074 - Z (분할정복, 재귀) Swift 문제풀이: 2^N X 2^N을 2 X 2 까지 분할해서 타겟 좌표를 찾아야 한다. 하지만 N의 범위는 15까지 이기 때문에 일일히 찾으면 2^15 * 2^15 시간 초과가 발생한다. 그러므로 타겟 좌표에 해당하는 행렬일 때만 탐색하고 아닐 때는 방문한 걸로 치고 넘어가서 시간을 줄여야 한다. 코드: import Foundation func solution(_ powN: Int, _ nr: Int, _ nc: Int) { if nr == r && nc == c { print(result) return } // 원하는 좌표가 포함되는 행렬이 아닐 때 방문한 걸로 치고 넘어가기 (시간 줄이기) if !(nr 1이 라서 www.acmicpc.net 2021. 4. 8.
[Algorithm/BOJ] 2589 - 보물섬 (BFS) Swift 문제 풀이: 문제에서 시작점이 주어지지 않기 때문에 직접 기준점을 잡아주어야 한다. 육지(L)를 기준으로 시작점을 잡는다. 그 좌표에서 지도를 벗어나지 않고 상화좌우로 이동할 좌표가 육지라는 선에서 이동거리를 1씩 늘려서 갈 수 있는 모든 좌표에 대한 거리를 나타내는 배열에 저장한다. 그리고 시작점에서 갈 수 있는 최대 거리(거리를 나타내는 배열의 최대 값)랑 이 문제의 답이 되는 변수와 비교하여 큰 것을 변수에 저장한다. 모든 육지(L)의 좌표에 대해서 반복한다. 코드: typealias Coord = (r: Int, c: Int) let input = readLine()!.split(separator: " ").map { Int(String($0))! } let n = input[0] let m = .. 2021. 3. 14.
[Algorithm/BOJ] 5014 - 스타트링크 (BFS) Swift 문제풀이: 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. -> 총 F층이 있는 고층 건물에서 S층에서 엘리베이터를 타고 G층으로 이동한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) -> 엘리베이터에 U층만큼 올라가는 U버튼과 D층만큼 내려가는 D버튼만 있다. 두 버튼을 몇 번 눌러야 S층에서 G층으로 갈 수 있는지 구하는 것이고 G.. 2021. 2. 23.
[Algorithm/BOJ] 7569 - 토마토 (BFS) Swift 문제풀이: 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. -> 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 6가지 방향으로 탐색하여 토마토를 익힌다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. -> 아래의 그림과 같이 상자에는 익지 않은 토마토, 익은 토마토, 빈 칸이 존재하고 3차원 배열을 이용한다. 정수 1은 익은 토마토, .. 2021. 2. 23.
[Algorithm/BOJ] 18353 - 병사 배치하기 (DP) Swift 문제 풀이: N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. LIS에 대한 개념을 아는 상태라면 쉽게 풀 수 있는 문제이다. 하지만 기본적인 LIS는 오름차순이고 문제에서는 내림차순으로 바꿔 풀어야 한다. 또한, 최대로 남은 병사의 수를 구하는 것이기 때문에 N에서 제일 긴 감소하는 부분 수열의 길이를 빼줘야 한다. 아래 그림은 내림차순인 것을 제외하면 전 포스팅.. 2021. 2. 9.
[Algorithm/BOJ] 11053 - 가장 긴 증가하는 부분 수열 (DP) Swift 문제 풀이: LIS에 대한 개념을 아는 상태라면 쉽게 풀 수 있는 문제이다. 가장 긴 증가하는 부분 수열 (LIS) 하나의 수열이 주어졌을 때, 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 것이다. 아래의 그림을 그리면서 DP를 어떻게 사용해야 하는지 알 수 있었다. 값이 1인 n개의 요소들을 포함하는 배열을 이용해서 전의 값들을 비교하고 증가되었을 경우에 원래 값에 1을 더해주면서 부분 수열의 최장 길이를 갱신하는 것이다. 코드: import Foundation func solution() -> Int { let n = Int(readLine()!)! let nums = readLine()!.split(separator: " ").map { Int(String($0))! } var dp = [In.. 2021. 2. 9.

티스토리툴바