척척학사의 코딩 여행💻

1916 최소비용 구하기 문제로 이동 문제 요약 N개의 도시가 있다. 한 도시에서 출발하여, 다른 도시에 도착하는 M개의 버스가 있을 때, A 도시에서 B 도시로 가는 최소 비용을 출력해라. 알고리즘 최소 힙을 구현한다. (스위프트도 힘 줘서 힙 내놔라) 주어진 정보를 입력받는다. 도시의 개수를 입력 받는다. (딕셔너리의 키의 개수가 된다.) 버스의 개수를 입력 받는다. (간선의 개수가 된다.) city[시작노드] = [ (도착도시, 비용)] 으로 딕셔너리를 입력받는다. (이때 객체는 비용을 기준으로 정렬되어야 한다) 다익스트라 알고리즘을 수행한다. 도착 도시에 대한 비용을 출력한다. 접근방법 전형적인 다익스트라 문제로 풀 수 있다. 특정 노드에서 다른 노드로 가는데에 최소 비용을 구하기 때문이다. 코드..

7576 토마토 문제로 이동 문제 요약 창고에 토마토가 보관되어있다. 보관 후 하루가 지나면, 익지 않은 토마토는 인접해있는 익은토마토의 영향을 받아 하루가 지나면 익게 된다. (토마토가 혼자 저절로 익는 경우는 없다) 토마토가 며칠이 지나 다 익게 되는지, 최소 일 수를 구해라. (1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 없는 칸이다) 알고리즘 주어진 토마토 정보를 입력받는다. 이때, 토마토가 입력 된 경우, tomato라는 배열에 넣는다. 입력받은 토마토 큐를 이용하여 bfs를 수행한다. 토마토 상자에 0이 있는 경우만 익는다고 생각하면 된다.(이동한다) 결과를 출력한다. 토마토 상자를 조회하며 0이 하나라도 있다면 -1을 출력한다. 토마토 상자의 최댓값을 출력한다. 접근방법 처음..

1753 최단 경로 문제로 이동 문제 요약 방향 그래프가 주어졌을 때, 시작 점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야한다. 알고리즘 주어진 그래프를 딕셔너리 형태로 입력받는다. Min Heap 자료구조를 만든다. (Swift는 heap 자료구조를 제공하지 않는다.) 다익스트라 알고리즘을 수행한다. 접근 방법 한 정점에서 다른 모든 정점의 최단 경로를 구하는 방법은 다익스트라 알고리즘을 사용해야한다. 이에 최소 힙을 제작하여 다익스트라 알고리즘을 구현해야한다. 코드 // 최소 힙 구현 struct Heap { var heap = [T]() private func getParent(_ index: Int) -> T { heap[index / 2] } private func getL..

Heap 자료구조 다익스트라 알고리즘을 공부하다가, 최소 힙에 대한 개념이 필요해서 구현하게 되었다. Swift는 왜 최소 힙 안 주냐 \ 그래도 직접 구현하면서 많은 공부를 할 수 있었다. 우선순위 큐 개념 컴퓨터에서도 우선순위 개념이 필요할 때가 있다. 네트워키 패킷 중에서 네트워크 관리와 관련된 것들은 일반 패킷보다 운선순위를 가져야한다. 운영 시스템에서 시스템 프로세스가 용 프로세스보다 우선순위를 가진다. 이러한 이유 때문에 자료구조에서도 우선순위를 지원하는 것이 필요하다. 우선순위 큐(Priority Queue)는 우선순위에 대한 개념을 큐에 도입한 자료구조이다. 조금 더 생각해보면, 일반적인 스택이나 큐도 우선순위 큐로 표현할 수 있다. 큐: 데이터 삽입 시간이 빠른 것을 높은 우선순위로 생각..

9095 1, 2, 3 더하기 문제로 이동 문제 요약 정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 계산해라. n = 3이라면 (1+1+1, 1+2, 2+1, 3) 4가지로 표현할 수 있다. 접근방법 사실 규칙을 생각하기 전에 점화식이 떠올랐다. (얻어 걸렸다는 말) 점화식 $$F(n) = F(n-1) + F(n-2) + F(n-3)$$ 이게 왜 맞지? 라는 생각을 했는데 F(1)의 1이 의미하는 바가 최댓값이 1이라고 생각하면 쉽게 이해할 수 있다. F(4) = F(3) + F(2) + F(1) 이다. F(1)에서 3을 더하면 4, F(2)에서 2를 더하면 4, F(3)에서 1을 더하면 4가 된다. 마찬가지로 F(7) = F(6) + F(5) + F(4) F(6)에서 1을..

1463 1로 만들기 문제로 이동 문제 요약 정수 x에 대해 세 가지 연산을 할 수 있다. 연산을 반복하며 x를 1로 만들고자 할 때, 최소한의 연산 횟수를 구해라. 3으로 나누어 떨어진다면, 3으로 나눈다. 2로 나누어 떨어진다면, 2로 나눈다 1을 뺀다. 알고리즘 점화식은 다음과 같다.$$F(n) = min(F(n/3), F(n/2), F(1)) + 1$$ 해당 점화식을 사용하여 Bottom up 방식으로 코드를 구현한다. 접근 방법 그리디는 왜 안 될까? 무조건 나눗셈이 숫자가 더 빨리 줄어들기 때문에 그리디를 생각할 수 있지만, 최적회가 아니다. 그리디 알고리즘은 3으로 나눔 -> 2로 나눔 -> 1로 뺌의 순서로 이루어 질 것이다. 2n + 1을 생각해보자. Greedy: 11 -> 10 -> ..

2839 설탕배달 문제로 이동 문제 요약 상근이는 정확히 Nkg의 설탕을 배달해야한다. 설탕은 3kg, 5kg의 봉지에 담겨있다. 이때 상근이가 Nkg의 설탕을 최소한의 봉지로 배달하려고 한다. 이때 최소 봉지 수를 계산해라. (정확히 Nkg으로 배달할 수 없을 때에는 -1를 출력한다.) 알고리즘 설탕 DP 배열을 선언한다. 점화식 $$F(n) = min(F(n-3), F(n-5)) +1$$을 만족하는 F(n)을 계산하여 출력한다. 접근방법 그리디로 안 되는 이유? 처음에는 그리디로 충분히 접근 가능하다고 생각했다. 거스름돈 문제처럼, 5키로 그램 봉지로 나누고, 나머지를 3키로 봉지에 담으면 되지 않나? 라고 생각했지만 아니다! 그리디 접근 방식에 따르면, 가능한 만큼 5kg로 가져가고, 나머지를 3k..

🥇 Gold 1707 이분 그래프 문제로 이동 문제 요약 그래프의 정점 집합을 두개로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 이분 그래프라고 부른다. 그래프가 주어졌으 ㄹ때, 이분그래프인지 판별하는 프로그램을 작성해야한다. 알고리즘 정보를 입력받고, 테스트케이스만큼 반복한다. 그래프를 무방향 그래프로 입력받는다. (양방향 간선) 전체 노드에 대해 bfs를 탐색하며 이분 그래프인지 판별한다. 결과를 출력한다. 접근방법 우선 나는 문제를 보고 이분 그래프의 정확한 정의를 알지 못했다. (그래프에 사이클이 있는가를 확인하는 문제가 아니라는 것이다) 위키에 이분 그래프의 정의를 보면 다음과 같이 나와있다. "모든 꼭짓점을 빨강, 파랑으로 색칠하되, 모든 변이 빨강과 파랑..

Record 작업하면서 Carousel을 만들었는데, 많은 부분에서 쓰일 수 있을 것 같아서 커스텀 가능한 형태로 라이브러리를 만들게 됐다! 코코아팟 배포하는 방법 Pod Libary를 생성하기 터미널에서 작업할 디렉토리로 이동한다. pod lib create JWCarousel을 입력한다. 라이브러리 정보를 입력한다. 해당 정보를 입력하면, Xcode 프로젝트가 열린다. (안 열린다면 해당 디렉토리 이동해서 직접 열자) 코드 작성하기 아까 만든 Pod 프로젝트에서 코드를 작성한다. Pod/DevelopmentPods/JWCarousel/ReplaceMe.swift 파일을 수정해주면 된다. (접근제어 주의!) 나는 SwiftUI 프로젝트이기 때문에 UIKit으로 되어있는 데모를 수정해줘야했다. App D..

2206 벽 부수고 이동하기 문제로 이동 문제 요약 N * M 행렬로 표현되는 맵이 있다. 0은 이동할 수 있는 길이고 1은 이동할 수 없는 벽이며 상하좌우로 이동할 수 있다. (1, 1)에서 (N, M)까지 최단거리로 이동해야한다. 이동 거리는 시작하는 칸과 끝나는 칸도 포함되어야하며, 이동 중 벽을 한 개 까지 부수고 이동할 수 있다. 알고리즘 맵을 입력받는다. (시간초과 주의) 3차원의 visited 배열을 선언한다. bfs를 수행한다. 접근방법 시간초과 때문에 삽질 어어어어어어어엄청 한 문제이다. 첫 번째 접근 - (안 될 거 뻔하지만, 무식하게 풀어보자) 지도를 입력받을 때, walls라는 벽의 위치를 모두 입력받은 후, 모든 경우의 수를 탐색하는 방법이다. N, M의 범위가 최대 1,000이므..