![]()
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제 풀이 문제를 읽으면서 조건을 파악하고 차근차근 단계에 맞는 함수를 작성하면 되는 문제였다. 그 외에도 자료구조의 선택이 중요하다. 봄, 여름, 가을, 겨울에 맞는 동작을 구현해야 한다. 봄 private fun spring(): ArrayList { val aliveTrees = PriorityQueue(compareBy { it.age }) val deadTrees =..
![]()
문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 풀이 한마디로 요약하면 조건이 많은 그래프 탐색 문제이다. 내가 작성했던 메서드들은 크게 3가지로 분리된다. 가장 가까운 승객 찾기 private fun findGuest(): Triple? { val visit = Array(n) { BooleanArray(n) { false } } var result: Triple val pq = Priorit..
![]()
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 문제를 풀기 위해서 생각해야 할 점은 외부 공기와 내부 공기의 분리를 어떻게 할 것인가 이다. 외부 공기와 내부 공기의 분리 외부 공기와 내부 공기의 다른 점은 어떤 것일까? 내가 생각한 점은 내부 공기는 치즈에 둘러싸여 밖으로 나가지 못하고, 외부 공기는 치즈에 둘러 쌓여 있지 않아서 자유롭게 움직일 수 있다는 점이다. 이를 구현하기 위해선 역발상이 필요하다. 내부공..
![]()
문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 풀이 시물레이션을 연습하고 있는데, 정말 복잡한 것 같다. 문제가 정말 길고, 생각해야 될 케이스가 너무 많아서 굉장히 오래 걸렸다. 우선 문제의 중요 포인트는 다음과 같다. 원판 회전 원판 회전은 방향에 따라 달라진다. 행렬을 시계방향으로 옮겨주거나, 반시계방향으로 옮겨주는 것과 동일하다. private fun rotate(step: Int) { var temp = 0..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 주어진 배열에서 최소한의 크기의 종류로 배열을 구성하는 문제이다. 그러기 위해서 크기별 개수를 기록할 필요가 있다. 크기별 개수 기록 fun makeSubTotal(tangerine : IntArray){ tangerine.forEachIndexed{ index, _ -> fruits[tangerine[index]]++ } } 나는 귤의 크기를 index로 가지는 배열을 만들어서..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 초기 풀이 초기 풀이에는 각 인덱스별로 누적합을 구해서 n^2으로 특정 인덱스를 기준 삼아 처음부터 인덱스까지의 누적합의 차이를 이용해서 구간의 합을 계산하려고 했다. class Solution { fun solution(sequence: IntArray, k: Int): IntArray { var answer = IntArray(2) println(sequence.size) v..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 접근까지는 쉽게 했는데 IDE 적응과 자료형에 대한 계산이 정말 귀찮았던 문제이다. 실제로 로직은 똑같은데 자료형 처리 순서에 따라서 계산 결과가 달라져서 틀렸던 경험이 있다. 우선 두 원 사이의 영역에 대해서 접점을 구하는 공식은 수학 시간에 배워서 알 수 있었다. 두 원의 반지름이 각각 4와 5일 경우 각 원의 방정식은 다음과 같다. 두 원 사이의 공통영역은 당연히 작은 원 ..
![]()
문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 문제 풀이 문제가 길지만, 문제의 핵심은 M개의 보석을 연속적으로 주워야 한다는 사실이다. 핵심을 지키면서 주울 수 있는 보석의 최대값을 구하는 전형적인 누적합 문제이다. 나는 i번째의 보석을 이동할 때의 누적합을 accumulateSum 이라는 1차 배열로 잡았다. 따라서 accumulateSum[4]라면 4번째의 보석까지 이동했을 때의 누적합이다. 즉 여기는 1~4번째 보석의 ..
![]()
문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 처음 문제를 보고 이렇다 할 접근 방법이 떠오르지 않았다. 초기에는 하나의 원소를 기준으로 left를 고정시키고, right를 옮겨가면서 투포인터 알고리즘으로 합이 s가 되는 조합을 찾으려고 했었다. -7 -3 -2 5 8이 있을 경우 -7을 기준으로 오른쪽을 8로 고정시키고, 투포인터를 시작한다. 현재 포인터는 8이고, sum은 1이다. 합..
