척척학사의 코딩 여행💻

14501 퇴사 문제로 이동 문제 요약 오늘부터 N+1일 째 되는 날, 퇴사를 하려고 한다. 남은 N일 간 상담을 받아, 최대한 많은 금액을 받으려고 한다. 이때, 받을 수 있는 최대 금액을 구해라. (배열 Tn에는 상담에 걸리는 시간이 저장 돼 있고, Pn에는 상담 시 받을 수 있는 금액이 저장 돼 있다.) 접근 방법 i 번째 날짜에 상담을 받는다고 할 때, 다음과 같은 연산을 할 수 있다. i + T(i) 이후 모든 result에 접근한다. result[next], result[i] + price[next] 중 더 큰 값을 계속 구해나간다. 코드 let n = Int(readLine()!)! var times = [Int]() var prices = [Int]() for i in 0 ..< n { l..

11053 가장 긴 증가하는 부분 수열 문제로 이동 문제 요약 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성해라. 알고리즘 수열을 입력받는다. 나보다 작은 수 중 부분 수열이 가장 긴 값을 찾아 저장한다. result의 최댓값을 출력한다. 접근 방법 우선 가장 긴 증가하는 부분수열이라는 말 부터 이해를 해 보자. 부분 수열 = "주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열" 증가하는 수열 = "오름차순으로 증가하는 수열" 가장 긴 증가하는 부분 수열 = 오름차순으로 정렬되는 부분수열 중 length가 가장 긴 수열 -> [10, 20, 10, 30, 20, 50]에서 가장 긴 증가하는 부분 수열 = [10, 20, 30, 50]이 되는 것이다. 문제..

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..

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를 탐색하며 이분 그래프인지 판별한다. 결과를 출력한다. 접근방법 우선 나는 문제를 보고 이분 그래프의 정확한 정의를 알지 못했다. (그래프에 사이클이 있는가를 확인하는 문제가 아니라는 것이다) 위키에 이분 그래프의 정의를 보면 다음과 같이 나와있다. "모든 꼭짓점을 빨강, 파랑으로 색칠하되, 모든 변이 빨강과 파랑..

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