Ikjo's Technology blog

문제 설명 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 접근 방법 해당 문제는 당초에는 우선순위 큐를 이용하려고 했지만 poll() 또는 remove() 메서드 사용 시 기존에 내부 요소들의 순서가 변동되어 List 자료구조를 이용하여 문제를 해결했습니다. 우선 문제에 따르면 "특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다"고 하는데, 이는 기존에 있던 학생의 사진을 빼고 새로운 학생의 사진을 넣어야하는 것을 의미합니다. 이때 기존에 어떤 학생의 사진을 빼냐가 중요..

문제 설명 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 접근 방법 해당 문제에서 요구하는 것은 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값입니다. 이때 유의해야할 것은 한 구명보트에 탈 수 있는 사람은 최대 2명뿐이고, 무게 제한이 있다는 점입니다. 즉, 키 포인트(key point)는 최대한 구명보트에는 두 사람씩 태우도록 해야한다는 점입니다. 이를 위해 우선 주어진 정수형 배열(people) 오름차순으로 정렬 해줍니다. (내림차순으로 해도 무방합니다.) 이때 무게..

문제 설명 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 접근 방법 해당 문제는 브루트포스, BFS, DFS를 활용하여 문제를 해결할 수 있었습니다. 우선 땅의 높이 정보가 주어지면 강수량 0(비가 안 온 경우) ~ 100(대지의 최대 높이는 100이닌까) 모든 경우에 대해 안전 영역을 구하도록 했습니다. 이때 대지가 물에 잠긴 것을 표시하기 위해 BFS를 활용하여 땅의 높이 정보인 int형 2차원 배열을 탐색하도록 했습니다. 이때 boolean 2차원 배열을 통해 특정 노드에서의 값이 강수량 미만이라면 해당 물이..

문제 설명 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 접근 방법 해당 문제는 큐(Queue) 자료구조를 이용하여 해결할 수 있었습니다. 문제에 따르면 트럭의 상태는 "대기 트럭"과 "다리를 건너는 트럭" 그리고 "다리를 지난 트럭"으로 나뉩니다. 이때 각각의 트럭의 상태들을 관리할 큐 자료구조를 만들어 줍니다.("다리를 지난 트럭"에 대한 큐 자료구조는 별도로 만들 필요없습니다.) 이후 다리를 건널 수 있는 조건(무게와 트럭 대수)을 충족 하는 경우 "대기 트럭을 담은 큐"에서..

문제 설명 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 회고 해당 문제는 DFS(깊이 우선 탐색)을 이용하여 풀 수 있었습니다. 깊이 우선 탐색을 통해 (0, 0) 지점에서 출발했을 때 탐색할 수 있는 모든 경로에 대해 탐색 종료 시의 이동한 칸 수를 검사하여 이들 중 가장 이동을 많이 한 횟수를 구하도록 했습니다. 다만, 이 문제의 경우 기존 깊이 우선 탐색이랑 다르게 접근했었던 방식이 있는데, 우선 별도의 방문 처리를 하지 않았다는 점이었습니다. 왜냐하면 모든 경로에 대해 검사해야하기 때문..