문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 읽어보면 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 한다라고 적혀있다. 이를 통해 해당 문제는 선택지마다 최선의 선택을 해야 하는 그리디 문제이다. 항상 그리지 문제를 풀기전에 어떻게 최선의 선택을 도출할까 가 가장 고민되고, 어려운 부분이다. 배낭문제와 같이 보통의 그리디문제는 주어진 배열을 정렬해서, 최선의 선택을 하기 위한 사전작업을 한다. 입력받은 구간에..
문제 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 풀이 오랜만에 풀어본 그리디 문제였다. 그리디문제는 문제에서 요구하는 최적의 결과를 도출하기 위한 접근방법을 잘 생각해야 하는 것 같다. 버스 정류장을 지날 때마다 2가지 선택지가 있다. 멈춰서 연료를 채우거나, 그냥 지나가거나 따라서 나는 모든 정류장을 지나갈 때마다 2가지 선택지를 우선순위큐에 넣어줬다. 이렇게 해도 괜찮을거라 생각했던 이유는 우..
문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 골드 1이라는 난이도답게 BFS와 여러 가지를 섞었던 문제였다. 우선 문제의 핵심은 주어진 섬을 모두 연결할 수 있는 다리를 건설하는데 발생하는 최소비용을 구하는 것이다. 해당 문구를 통해서 섬이라는 정점을 모두 연결해야 하는 MST라고 유추할 수 있다. 원래 MST는 모든 정점을 연결하는 문제이지만, 해당 문제는 정점을 확대한 섬으로 계산을 해야 했기 때문에..
문제 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 문제 풀이 정말 오래 걸렸던 문제다. 특정 테케에서 통과하지 못해서 많이 고생했다. 내가 생각하는 알고리즘 분류는 조합과 BFS를 같이 사용하는 문제인 것 같다. 배양액을 뿌릴 수 있는 땅에 대해서 빨간색,초록색,배양액X에 조합을 통해서 경우의 수를 정해준다. 사용한 자료구조 private lateinit var setting: Se..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 길고 설명이 장황하지만 LV1 문제답게 문제 흐름 그대로 쭉쭉 있어나가면 된다. 우선 해당 문제에서는 선물을 주고 받은 기록이 중요하다. 따라서 선물을 주고 받을 기록을 저장할 자료구조를 나는 2차원 배열로 설정했다. 인접리스트도 상관없지만 친구수가 50명밖에 되지 않기도 했고, 인덱스로 바로 접근할 수 있다는 장점이 컸던 것 같다. 인접리스트를 한다면 해당 인덱스의 친구..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 방문한 정점의 개수와 간선을 바탕으로 그래프의 모양을 구하려고 했지만, 그래프의 크기를 측정할 수가 없었다. 생각해 보니 각 그래프의 특징이 있었고, 해당 그래프의 특징을 파악하면 풀 수 있는 문제였다. 도넛 그래프 도넛 그래프는 사이클을 형성하고 있으며 N-1개의 간선으로 구성되어 있기 때문에 모든 정점이 하나의 간선을 가지고 있다. 막대그래프 막대그래프는 간선마다 하..
문제 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 문제 풀이 문제를 풀기 위해서 생각해야 할 점은 외부 공기와 내부 공기의 분리를 어떻게 할 것인가 이다. 외부 공기와 내부 공기의 분리 외부 공기와 내부 공기의 다른 점은 어떤 것일까? 내가 생각한 점은 내부 공기는 치즈에 둘러싸여 밖으로 나가지 못하고, 외부 공기는 치즈에 둘러 쌓여 있지 않아서 자유롭게 움직일 수 있다는 점이다. 이를 구현하기 위해선 역발상이 필요하다. 내부공..