Hyun's_Devlog

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

이분탐색으로 접근했다.

풀이 방법

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

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

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

정답 코드

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

이분탐색으로 접근했다.

풀이 방법

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

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

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

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

정답 코드

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

조합을 통한 완전탐색 + 유니온파인드로 접근하였다.

접근 방법

입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.

유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.

정답 코드

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

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

정답 코드

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

최단거리 탐색 알고리즘으로 접근한 문제다. 

풀이

특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.

정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.

따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.

즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.

정답 코드

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

처음엔 길이가 짧은 문자열에서 부분문자열을 뽑아낸 뒤 길이가 긴 문자열에 포함되는지 여부를 통해서 접근했지만 당연하게도 시간초과.

동적계획법 태그를 보고서 접근법을 생각해 봤지만 결국 풀이를 찾아봤다. 점화식부터 말하면 다음과 같다.

dp[i][k] = dp[i-1][k-1] + 1

여기서 2차원 배열 dp는 해당 위치의 문자로 끝나는 공통 부분 문자열의 길이를 뜻한다.

풀이

문자열 A = "AACD"와 문자열 B = "SSAB"를 기준으로 설명하면 다음과 같이 작동한다.

문자열 A의 길이 N, 문자열 B의 길이 M 일 때, (N+1)*(M+1) 크기의 2차원배열 dp를 생성. 0으로 초기화한다.

1부터 N, 1부터 B까지 2중 반복문을 탐색하면서 점화식을 통해 계산한 값 중 최댓값이 정답이다.

두 문자열의 i번째와 k번째 문자가 일치했다는 것은 두 문자열의 i-1번째와 k-1번째 문자로 끝나는 공통 부분 문자열에 현재 문자를 이어 붙여 한 글자 더 긴 공통부분 문자열을 만들 수 있다는 뜻이 된다.

즉 O(N*M) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

정답코드

간절기만 되면 항상 외출 전에 "기온별 옷차림"을 검색하여 날씨 앱과 번갈아가면서 보게 된다.

이때마다 위젯으로 제공하면 좋겠다는 생각을 해서 어플을 찾아보면 앱스토어에 있는 어플들은 UI가 내 마음에 썩 들지는 않는달까..

그래서 이번에 직접 만들어보았다.

2023년의 겨울은 따듯함과 극한 추위가 함께 있는 겨울이었다.

분명 4계절이 뚜렷한 건 알겠는데, 일주일 단위로 계절이 바뀌는 느낌이랄까..

그래서 더더욱 "기온별 옷차림"을 많이 검색해 보았다.

기본적으로 시간단위 날씨정보와 외출시간을 설정하여 해당 구간의 평균기온이 나오게 하였다.

미리 저장해 둔 기온별 옷차림이 평균기온에 맞게 화면 중앙에 나오는 형태이다.

크게 복잡한 로직이 요구되지 않는 앱이어서 3-4주면 만들겠거니 시작했는데, 두 달이나 걸려버렸다.

심지어 처음 구상했던 다른 지역 날씨 조회 기능은 빠진 상태로 출시하였다...

현재는 사용자의 위치를 조회하여 해당 지역 정보만 조회가 가능하다.

개인 프로젝트를 할 때마다 마주하는 순간이 바로 내가 구상했던 기능들을 다 구현하기 위해 데드라인을 미룰 것인가, 아니면 미구현된 부분은 추후에 업데이트하기로 하고 현재 구현된 부분까지만 마무리하고 배포할 것인가에 대한 혼자만의 줄다리기가 발생하게 된다는 점이다. 

현재 대한민국 날씨가 굉장히 변덕스럽다는 점을 감안해서 이번에는 일단 출시를 하고

내가 직접 사용해 보면서 불편한 점들을 개선해 나가는 쪽으로 결정하여 배포를 우선시하였다.

프로젝트를 진행하면서 처음에 가장 신경 썼던 부분은 iOS 순정 앱과 비슷한 UI 구성과 룩이었다.

아이폰 순정 날씨 위젯과 나란히 놓았을 때 위화감이 없었으면 해서 그렇게 구성하려 했고,

배경화면 색상과 UI구성을 최대한 흉내 내어 보았다.

이번에는 별도의 외부 라이브러리는 사용하지 않았고, 요즘 많이 사용한다는 SwiftUI 프레임워크를 이용하였다.

UIKit을 대체하기 위해 나온 건 아니지만, 확실히 UIKit에 비해 직관적이고 쉬워졌다고 생각한다. 

다음으로 서비스의 핵심인 WeatherKit.

날씨 정보를 가져오는 데 사용한 애플 측에서 제공하는 API다.

async / await 표현을 이번에 처음 마주해서 당황했는데,

다행히도 자주 도움을 받는 naljin님의 글 덕분에 기본적인 지식은 이해하였다.

다음 핵심인 WidgetKit. 마찬가지로 애플 측에서 제공하는 위젯 제작 프레임워크이다.

이번 프로젝트의 주요 목적이라고 할 수 있는 위젯 기능의 구현을 위해 필요했다.

당연하게도 처음 사용하다 보니 사용법을 이해하는데에 시간이 많이 걸렸는데, 그만큼

iOS에서 위젯이 어떻게 작동하는지 평소의 궁금증이 해결되어서 좋았다.

깃허브에도 신경쓰면서 작업을 했다. 아직도 서투르긴 하지만 우연히 좋은 Commit massage 작성법을 발견해서 이전에는 그냥 작업 끝나고 눌러대던 커밋버튼을 나름대로 작업의 구간과 의도를 나타내기 위해 메세지를 작성하고 정리해가면서 작업하였다.

사실 이전까지만해도 "이미 있는 서비스네" 라는 결론으로 시작하지 않고 묻어둔 개인 프로젝트가 몇가지 있다.

Fitcast 또한 마찬가지로 이미 같은 기능을 제공하는 앱이 많이 출시되어있는 상태임에도 생각을 바꾸고 프로젝트를 시작하게된 계기가 유튜브에서 저 썸네일을 발견하고서 부터다.

간간히 즐겨보는 노마드 코더님의 영상인데, 요약하면 창의적인 서비스에 대한 이이디어가 떠오르더라도 이미 누군가 생각했을 가능성이 높으니, 해당 서비스가 존재하는지 구글링 하지 말고 아이디어에 대해서만 집중하여 나만의 창의성을 부여하라는 얘기다.

이미 있는 서비스인 것을 알지만 경쟁 서비스보다 내가 만든 서비스가 조금이라도 더 나은 점이 있다면 그것으로 차별점을 두는 것이 의미있지 않을까 라는 결론에 도달했다.

또하나 재밌게 본 영상이 천재들의 코딩 공부법.

Swift 창시자라는 썸네일이 내 시선을 사로잡았다.

개발실력을 쌓기 위해 책을 보고 암기하지말고 무언가를 만들어보고 그 과정에서 마주한 문제들을 해결하기 위해 지식들을 찾아가면서 성장하라는 얘기이다.

사실 개인 프로젝트를 시작하라는 문구보다 책을 보고 암기하지 말라는 문구가 더 와닿았다. 실제로 나는 정반대로 프로젝트보단 강의영상 시청 위주의 학습을 이어오고 있었고, 이것이 동기와 흥미가 금방 식어버린다는 것을 최근에 느꼈기 때문이다.

개발자는 현실의 문제를 IT기술로 해결하는 사람이라고 생각한다. 따라서 크건 작건 현실 속의 불편함을 해결해 나가는 과정을 통해 성장하는 것이 개발자로서의 흥미와 동기를 잃지 않는 방법이 아닐까 생각하여 프로젝트를 시작한 것이다.

작성하고 보니 나는 주위의 환경에 크게 영향을 받는 타입이라고 생각한다.

그분들에게 도움을 받았듯이 나도 언젠가 글속에서 언급한 개발자 분들 처럼 남들에게 도움을 주는 그런 사람이 되고 싶다.

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

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

정답 코드