![]()
문제 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이다. 합..
![]()
문제 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 풀이 문제가 길고, 부연 설명도 많은 편이지만, 한마디로 요약하자면 다빈치 코드라는 게임에서 이기는 최적의 경우를 계산한다고 생각하면 편할 것이다. 당연하게도 상대방이 낼 카드를 알고 있다면, 플레이어는 가장 근소하게 이기거나, 지는 걸 원할 것이다. 즉 문제의 목표는 상대방의 카드에 따라서 가장 적합한 카드를 찾는 것이다. 이렇게 ..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 평소와 같이 DFS/BFS로 생각을 하고 풀었지만, 평범한 DFS/BFS 문제는 아니었다. 테스트케이스에서 주는 혼란을 주는 것도 있었다. 테스크케이스를 예로 들어서 설명해보겠다. [ ICN, SFO] , [ICN, ATL] , [SFO, ATL] , [ATL, ICN], [ATL, SFO]라는 티켓이 있다. 0번 index -> 1번 index로의 값은 항공권으로 갈 수 있다는 ..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 굉장히 길었지만, 실제로는 문제의 유형을 알고 있다면 쉽게 풀 수 있는 문제였다. 내가 느끼기에 문제의 유형을 파악할 수 있는 부분은 다음과 같았다. 모든 섬을 최소한의 비용으로 연결해라! 다리를 여러번 건더더라도, 도달할 수 있으면 통행이 가능하다 다음 정보를 통해서 해당 문제는 MST(Minimum Spanning Tree)라고 생각했다. MST 문제도 주어진 N개의 ..
