https://www.acmicpc.net/problem/17208

동적계획법으로 접근한 문제다.


풀이 방법

2차원 배열 dp를 생성. x열은 소유하고 있는 버거를, y행은 소유하고 있는 감자튀김이다.

따라서 dp[x][y]는 버거 x개와 감자튀김 y개를 가지고 있을 경우 받을 수 있는 최대 주문의 수를 의미한다.

 

M행 K열의 2차원배열을 생성해야 하는데, 인덱스로 접근하기 편하게 dp[M+1][K+1] 배열로 선언하였다.

 

입력된 주문이 버거 M개 혹은 감자튀김 K개를 초과한다면 해당 주문은 탐색할 필요가 없다.

 

dp[M][K]부터 dp[0][0]까지 역순으로 탐색하여 (동일 주문은 하나만 받을 수 있다.)

주문을 받지 않고 남아있는 음식을 아낄 것인지 (dp[x][y]) 혹은

해당 주문을 받을 것인지 (dp[x-현재 주문의 버거 개수][k-현재 주문의 감자튀김 개수]+1)

둘 중 더 큰 값을 선택하여 현재 탐색 중인 곳을 갱신하면 된다.

 

따라서 현재 보유 중인 버거가 x개, 감자튀김이 y개이며 현재 요청된 주문의 버거 개수가 dx, 감자튀김의 개수가 dy일 경우, 점화식은 다음과 같다.

dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[7211] Ringsõit  (1) 2024.06.09
[3271] MEADOW  (0) 2024.05.26
[17090] 미로 탈출하기  (0) 2024.04.24
[14923] 미로 탈출  (0) 2024.04.21
[13397] 구간 나누기 2  (0) 2024.02.28

https://www.acmicpc.net/problem/7211

 

유니온 파인드의 기본 문제다.


풀이 방법

입력되는 간선 정보를 저장한다.

이때 국가소유의 간선인지 아닌지 또한 저장해야 한다.

 

간선정보를 비용순서로 정렬. 모든 단선을 탐색하며 유니온 과정을 수행한다.

  • 해당 간선이 국가소유의 간선이며 최소 스패닝 트리에 포함되어야 하는 간선이라면 비용을 0으로 하여 필요한 비용으로 추가한다.
  • 해당 간선이 국가소유의 간선이지만 최소 스패닝 트리에 포함하면 안 되는 간선이라면 해당 간선의 비용을 필요한 비용에서 빼준다.
  • 국가소유의 간선이 아니라면, 최소 스패닝 트리에 포함되는지 여부를 확인한 뒤 필요한 비용에 반영하면 된다.

필요한 비용이 0보다 작다면 0을 출력. 그 이상이라면 해당 비용을 출력하면 된다.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[17208] 카우버거 알바생  (0) 2024.09.11
[3271] MEADOW  (0) 2024.05.26
[17090] 미로 탈출하기  (0) 2024.04.24
[14923] 미로 탈출  (0) 2024.04.21
[13397] 구간 나누기 2  (0) 2024.02.28

https://www.acmicpc.net/problem/3271

번역기능으로 문제를 봐도 이해되지 않아 헤맸다. chatGPT를 통해 번역과 설명을 보고 나서 이해하여 정답을 받았다..

기본적인 최소 스패닝 문제.


풀이 방법

B마리의 벌들이 F개의 꽃을 최소 스패닝 트리로 구성하여 각 구역을 분담하여 탐색하게 된다. 이때 각 벌들이 분담받은 이동 경로 중 한 번에 가장 많이 이동한 거리의 최솟값을 출력하라는 얘기.

 

따라서 크루스칼 알고리즘을 컴포넌트가 B개가 될 때까지 진행하고, 이때까지 가장 많이 이동한 거리를 출력하면 된다.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[17208] 카우버거 알바생  (0) 2024.09.11
[7211] Ringsõit  (1) 2024.06.09
[17090] 미로 탈출하기  (0) 2024.04.24
[14923] 미로 탈출  (0) 2024.04.21
[13397] 구간 나누기 2  (0) 2024.02.28

https://www.acmicpc.net/problem/17090

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

그래프 탐색 문제. 시간초과를 해결하지 못해 결국 풀이를 찾아보았다.


풀이 방법

배열 범위 밖으로 탈출할 수 있는 노드의 수를 반환해야 한다.

단순히 깊이우선으로 모든 노드에 수행하게 되면 시간초과가 일어난다.

 

미로의 각 칸에서 넘어가는 다음 칸은 지정되어 있다. 따라서 이미 탐색을 수행한 노드의 끝이 맵 밖으로 이어지는지,  아니면 맵을 탈출 하지 못하고 사이클을 형성하는지 미리 저장해 둔다면 시간 내에 정답을 반환할 수 있다.

 

미로와 같은 크기의 N*M 2차원 visited 배열 생성. 특정 좌표를 아직 탐색하지 않았다면 -1, 해당 좌표가 탈출하지 못하는 좌표라면 0, 미로를 탈출할 수 있는 좌표라면 1을 저장한다.

 

깊이 우선 탐색을 수행. 다음 좌표가 미로 밖이라면 1 반환. 아닌 경우에는 처음 방문 좌표인지 확인하여 처음 방문 하는 곳이라면 (-1) 다음 좌표로 재귀호출이 이루어지며 해당 좌표에 결괏값이 저장된다. 

 

탐색을 통해 1의 개수를 정답으로 출력하면 된다.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[7211] Ringsõit  (1) 2024.06.09
[3271] MEADOW  (0) 2024.05.26
[14923] 미로 탈출  (0) 2024.04.21
[13397] 구간 나누기 2  (0) 2024.02.28
[8983] 사냥꾼  (0) 2024.02.19

https://www.acmicpc.net/problem/14923

 

14923번: 미로 탈출

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이

www.acmicpc.net

기본형태의 그래프탐색 문제. 단 지팡이의 사용여부라는 조건이 붙어있다.


풀이 방법

너비 우선 탐색으로 목적지까지 그래프 탐색을 시도한다. 중복 방문을 피하기 위한 visited 배열을 3차원으로 생성.

 

visited[0][X][Y] -> 지팡이를 사용하지 않은 상태로 x,y 좌표 탐색여부,

visited[1][X][Y] -> 지팡이를 사용한 상태로 x,y, 좌표 탐색여부를 나타낸다.

 

visited 배열을 통해 좌표 탐색을 수행하여 정답을 출력하면 된다.

 

목적지에 도달하지 못하면 -1을 반환해야한다는 조건을 까먹지 말고 제출하자.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[3271] MEADOW  (0) 2024.05.26
[17090] 미로 탈출하기  (0) 2024.04.24
[13397] 구간 나누기 2  (0) 2024.02.28
[8983] 사냥꾼  (0) 2024.02.19
[17471] 게리멘더링  (0) 2024.02.06

에러라기보단, 기술을 이해 없이 사용하여 마주한 문제 해결 정도로 봐야겠다.


문제 정의

비동기 함수를 통한 동작으로 UI반영이 안된다.

 

위치정보를 담당하는 locationManager 객체가 @Published로 정의되어 있다.

따라서 locationManager의 값이 변경이 되면 swiftUI는 자동으로 화면을 새로 그려낸다.

따라서 나는 ViewModel에서 locationManager의 속성 변경을 통해 UI를 갱신하도록 하였다.

 

locationManager 객체에는 사용자의 위치를 갱신하는 함수 locationManager(_, didUpdateLocations) 함수가 있다.

lastLocation 속성을 변경하는 동작이다. 해당 함수는 delegate 패턴으로 작성되며, 개발자는 해당 함수를 직접 호출할 수 없다.

그러면 어떻게 사용하느냐?

 

locationManager객체의 startUpdatingLocation() 함수를 통한 대리 호출만 가능하다.

해당 함수는 ViewModel에 정의하여, 여기서 호출이 일어나면 locationManager의 속성이 바뀌게 되고,

이를 SwiftUI가 자동으로 UI에 반영해 준다.

 

그리고 locationManager에는 사용자의 위치를 기반으로 주소값을 갱신하는 함수가 있다.

lastLocation을 기준으로 주소를 가져오게 된다.

 

이때 든 생각

어차피 따로 쓸 일 없는데, 호출 한 번으로 사용자 위치 갱신할 때 한 번에 주소도 갱신하면 안 됨?

 

 

내가 의도한 순서:

위치 갱신 -> 갱신한 위도, 경도를 기준으로 주소 갱신 -> 변경된 속성을 SwiftUI가 감지하여 UI 갱신

 

이런 단순한 생각으로 ViewModel에 다음과 같이 작성하였으나,

사용자 위치만 갱신될 뿐 정작 중요한 주소 레이블이 UI에 반영이 되지 않았다.

 

실제 동작

 

열심히 함수에 print()를 찍어 동작이 어떻게 이루어지다 파악해 보니 내가 작성한 것은 다음과 같이 동작했다.

delegate 패턴으로 작성된 locationManager(_, didUpdateLocation) 함수로 넘어가기 전에 비동기로 주소갱신이 이루어진다.

 

당연하게도 갱신이 되지 않은 위치로 주소를 가져오니 이전 주소가 나오고,

위도, 경도 값이 경신된 이후 함수가 종료된다.

locationManager의 대리호출과 비동기 호출의 조합으로 동작의 순서가 엉망이 돼버린 것.

 


문제 해결

짧지 않은 기간 동안의 삽질과 아직 해결되지 않은 의문점이 남아있지만 아무튼 지금은 의도된 동작대로 작동한다.

 

 

일단 위치갱신과 주소갱신을 한 번에 하겠다는 생각을 버렸다.

따라서 주소갱신함수는 locationManager의 속성을 바꾸는 것이 아닌, Sting을 반환하는 비동기 함수로 변경하였다.

* 비동기로 굳이 작성하는 이유는 주소를 반환하는 reverseDeocoderLocation() 함수가 비동기로 작성되었기 때문.

 

이어서 locationManager에 있던 주소 레이블 속성을 viewModel로 가져왔다.

이렇게 각 함수를 ViewModel에서 따로 호출할 수 있게 변경하였다.

 

이어서 View에서는 onChange를 통해 위도, 경도의 갱신이 완료되면, 주소를 가져오게 하여 동작의 순서를 정해주었다.


정리

동작을 분리한 이유는 다음 한 줄로 정리할 수 있다.

 

UI의 반영은 메인 스레드에서만 이루어진다.

 

ViewModel을 담당하는 FitcastManager@MainActor로 선언된 이유가 바로 여기서 작동하는 동작들은 모두 메인스레드에서 이루어지게 하기 위함이다.

 

 

따라서 기존의 방식대로 주소 갱신이 비동기로 동작하게 된다면 메인스레드가 아닌 새로 생성된 스레드에서 작동하게 되는 것이고, 여기서 이루어진 갱신은 UI에 반영될 수 없다고 판단하였다.

 

따라서 UI에 반영할 주소값의 갱신은 @MainActor로 선언된 ViewModel의 속성으로 두어 비동기로 작동하더라도 메인스레드에서 동작하게끔 수정해 주었다. 

 

사실 해당 문제를 해결하기까지 아직 의문점이 남은 부분이 많이 있다. 아직 aync/await의 사용법과 MainActor와 관련된 이해도가 떨어져서 그렇다고 생각한다. 해당 개념에 대해 쉽게 설명한 글이 많으므로 나중에 완벽하게 이해된다면 다시 한번 리팩토링을 통해 후기로 돌아와야겠다.

 

 

 

 

https://www.acmicpc.net/problem/13397

 

13397번: 구간 나누기 2

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수

www.acmicpc.net

이분탐색으로 접근했다.


풀이 방법

배열의 크기 N이 최대 5000으로 작은 값에 속한다. 따라서 이분탐색으로 찾게 될 값은 구간의 최대 점수를 찾는 문제로 접근했다.

즉 이분탐색으로 mid값을 고정하고 길이 N의 배열을 순차탐색하면서 탐색 중인 구간의 최댓값 - 최솟값이 mid보다 크다면 구간을 나누어 마지막까지 탐색이 끝났을 때 구간의 개수가 M이하라면 최대 점수를 더 낮은 쪽을 탐색, 개수가 M보다 크다면 최대 점수가 더 큰 쪽으로 이분 탐색을 이어가면 된다.

 

입력 예제 1

 

입력 예제를 기준으로 동작을 그림으로 나타내면 다음과 같다. 이분탐색 mid 값이 3, 5, 4 일 경우 각각의 구간의 개수 조건을 확인. 구간의 최댓값이 5일 경우에 조건을 만족하므로 5가 정답이 된다.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[17090] 미로 탈출하기  (0) 2024.04.24
[14923] 미로 탈출  (0) 2024.04.21
[8983] 사냥꾼  (0) 2024.02.19
[17471] 게리멘더링  (0) 2024.02.06
[1700] 멀티탭 스케줄링  (0) 2024.01.30

https://www.acmicpc.net/problem/8983

 

8983번: 사냥꾼

입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌

www.acmicpc.net

이분탐색으로 접근했다.


풀이 방법

주어지는 사대의 위치를 오름차순으로 정렬한다.

이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.

 

이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.

 

해당 방법으로 접근한다면 O(100,000 * log100,000)O(500,000)에 탐색이 가능하다.


정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[14923] 미로 탈출  (0) 2024.04.21
[13397] 구간 나누기 2  (0) 2024.02.28
[17471] 게리멘더링  (0) 2024.02.06
[1700] 멀티탭 스케줄링  (0) 2024.01.30
[23286] 허들 넘기  (0) 2024.01.18

+ Recent posts