본문 바로가기

반응형

분류 전체보기

(400)
[BOJ] 백준 10757 큰 수 A + B (Swift) 문제 https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 Swift에서는 파이썬과 달리 BigInteger를 제공하지 않고 있습니다. 그래서 직접 문자열을 통해서 구현을 해주어야 합니다. 실제로 덧셈을 하는것과 비슷하게 구현하기 위해서 맨 뒷자리 수 부터 계산을 해주어야 겠다는 생각을 했습니다. 또한 덧셈을 할 두 수의 길이가 다르다면, 작은 수에 0을 붙여줘야 할 것입니다. 그리고 한자리 수의 덧셈을 진행했을 때, 올림이 되는 경우 (9 + 8 = 17) 올림처리를 해주어야 합니다. 마지막으로 모든 자리수에 맞춰 계산을 한 후, 올림처리가 되어있다면..
[BOJ] 백준 2839 설탕 배달 (Swift) 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이 문제는 어떤 알고리즘을 사용하여 풀 수 있을까요? 봉지가 3, 5의 단위로만 존재하고 5가 3의 배수가 아니기 때문에, 그리디 알고리즘으로는 풀 수 없습니다. 그래서 다이나믹 프로그래밍 기법을 떠올릴 수 있습니다. 다이나믹 프로그래밍은 점화식만 세우면 쉽게 풀 수 있습니다. DP 테이블을 어떤식으로 채울 수 있을까요? 봉지가 3, 5의 단위로만 존재하기 때문에, 1, 2, 4 의 설탕은 들고갈..
[Swift] 컬렉션 자료형에 대해 알아보자 - 2 (Dictionary) 지난 포스팅에서는 컬렉션 자료형 중 Array에 대해 알아보았습니다. 이번 포스팅에서는 Dictionary에 대해 알아보겠습니다. Dictionary란? Dictionary는 요소가 키-값 쌍인 컬렉션이고, 구조체로 되어있네요! 또한 Dictionary는 일종의 해시 테이블이고, 순서가 보장 되어 있지 않습니다. 특이하게 요소중 key가 Hashable을 채택하고 있어야하는데, Swift에서 제공하는 기본 자료형들은 대부분 Hashable 프로토콜을 준수하고 있습니다. 여기서 Hashable이 머냐.. 하면 Hashable은 Equatable 프로토콜을 준수하고 있고.. 이 Equatable 프로토콜은 == 과 같은 연산자를 사용할 때, 사용되는 프로토콜 인데, 어떤 프로퍼티를 가지고 값이 같은지 아닌지..
[BOJ] 백준 2775 부녀회장이 될테야 (Swift) 문제 풀이 이 문제는 다이나믹 프로그래밍 기법을 사용해서 쉽게 풀이할 수 있습니다. 먼저, 0층의 i호에는 i명이 산다. 라는 문제의 지문을 이용해서 0층, 1층, 2층... 바텀업 방식으로 답을 도출할 수 있다는 아이디어를 얻을 수 있습니다. 4호까지 있다고 가정하고 DP 테이블을 어떤식으로 채워나갈지 확인해보시죠..! 2층 3호는 어떤식으로 채워줘야 할까요?? 2층 3호 = 1층 1호 + 1층 2호 + 1층 3호 일 것입니다. n층 1호는 0층 1호가 1이기 때문에, 무조건 1이 될 수 밖에 없습니다. 1층 2호 = 0층 1호 + 0층 2호 겠죠?? 하지만 이것은 1층 1호 + 0층 2호 라고 해도 되겠죠?? 1층 3호는 어떨까요?? 1층 3호 = 0층 1호 + 0층 2호 + 0층 3호 겠네요. 0층..
[BOJ] 백준 10250 ACM 호텔 (Swift) 문제 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 먼저, 도착한 손님의 순서대로 방 배정을 하는 방법에 대해 이해를 해야합니다. 층(H) 수가 6, 방(W) 수가 3이라고 가정을 해보겠습니다. 101 -> 201 -> 301 -> 102 -> 202 -> 302 -> 103 -> ... -> 603 의 순서로 될 것입니다. 그렇다면 먼저 N번째 손님이 갈 층 수를 어떻게 구해야할까요? 층 수 구하기 층 수는 단순히 N % ..
[BOJ] 백준 2869 달팽이는 올라가고 싶다 (Swift) 문제 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 풀이 낮에는 A미터 올라가고, 밤에는 B미터 미끄러진다. 주의해야 할 점이 A미터를 올라갔을 때, 정상에 올라갔다면 미끄러지지 않는다. while문을 통해서 구할 수 있겠지만, 이 문제는 시간제한이 0.15초 입니다. 또한 A, B, V의 범위가 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 이므로, A = 2, B = 1, V = 1,000,000,000 이라면... 약 10억번의 연산을 수행하는 while문으로는 시간안에 해결할 수 없..
[BOJ] 백준 1193 분수찾기 (Swift) 문제 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 먼저 지그재그 순서가 어떻게 되는지 확인을 해봐야 합니다. 보라색으로 색칠한 부분은 아래에서 위 순서로, 주황색으로 색칠한 부분은 위에서 아래의 순서로 진행이 됩니다. 보라색으로 색칠한 부분은 홀수번째 대각선이 되겠네요! 대각선의 크기는 1, 2, 3, 4 ... 순으로 늘어나고 있습니다. X번째가 주어졌다면 X보다 크거나 같아질 때 까지 대각선의 크기를 더해줘서 몇번째 대각선에 위치했는지 찾을 수 있습니다. 예를들어 X가 7이라면..? 7
[BOJ] 백준 2292 벌집 (Swift) 문제 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 풀이 문제에 그림이 있어서 그림을 보고 어떻게 풀어야할지 이해해봅시다. 먼저 그림에 선을 그어서 방을 어떻게 나누는지 확인해봅시다. 발로 그린 그림이지만.. 잘 살펴보면 1 (1) = 1개 2 ~ 7 (6) = 2개 8 ~ 19 (12) = 3개 20 ~ 37 (18) = 4개 ... 인 것을 확인할 수 있습니다. 따라서 1부터 시작해서 n보다 작을 때 까지 6 * i를 더해줍니다. (i는 계속해서 ..

반응형