Ikjo's Technology blog

문제 설명 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 회고 해당 문제는 DFS를 통해 해결할 수 있었습니다. 우선 해당 문제에서 요구하는 것은 '그림의 영역 개수'와 '가장 큰 영역의 칸수'입니다. 이를 구하기 위해 문제에 접근한 방식으로는 다음과 같습니다. 1. 주어진 2차원 배열을 차례대로 순회한다. 2. 방문되지 않은 색칠된 영역이라면(배열 요소 값이 0이 아닌 경우) 해당 색의 영역을 DFS 탐색한다.(영역 칸수 카운팅) 3. '2번'에서 모든 탐색을 마친 후 다음 요소 값을 기준으로 다시 D..

문제 설명 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 회고 제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다. 주어진 2차원 배열 상의 요소별 값(집터 좌표별 블록의 높이) 중 최솟값(최소 블록 높이)와 최댓값(최대 블록 높이)를 구한다. 최소 블록 높이부터 최대 블록 높이까지 각각의 값으로 블록의 높이를 모두 일정하게 바꾸고(땅 고르기) 이 경우의 소요 시간과 블록 높이를 구한다. 각각의 값으로 순차적으로 땅 고르기 작업을 할 때마다 낮은 시간을 우선적으로 산출하고 시간이 동일할 경우 더..

문제 설명 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 회고 제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다. 주어진 2차원 배열에 대해 임의의 3개의 벽 세우기 바이러스 확산시키기 안전 영역 크기 구하기(기존 값과 대소 비교 후 더 큰 값 할당) 변경된 2차원 배열 초기화하기 1번으로 돌아가 다시 임의의 3개의 벽 세우기(기존 3개의 벽과 완전히 중복되지 않는 3개의 벽) 위 단계에서 제가 가장 구현하기 까다로웠던 부분은 "임의의 3개의 벽을 세우는 것"이었습니다. 사실 DFS나 BFS를 통해 임의의 ..

문제 설명 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 풀이 회고 우선 해당 문제는 문제를 잘못 이해함으로 인해 삽질하는 시간이 많았습니다. 문제에서 요구하는 것은 "논문 n편 중, h번 이상 인용된 논문이 h편 이상일 때 h의 최대값"을 구하는 것입니다. 이때 h라는 수의 범위는 무엇일까요? 저는 처음에 이 문제의 h라는 수가 매개변수(citations)로 주어진 배열에 존재하는 정수 중에 존재한다고 착각하고 있었습니다. 하지만 이에 대한 풀이를 확실하게 구해도 정답이 나..

문제 설명 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 회고 해당 문제에서 요구하는 것은 일자별로 주가가 주어졌을 때 주식을 샀다 팔았다(단타) 해서 낼 수 있는 최대 이익을 구하는 것입니다. 즉, 핵심은 쌀 때 사서 비쌀 때 파는 것입니다. 해당 문제에서 두고 있는 시간 제한은 5초로 다소 여유(?) 있다고 생각했었습니다. 그리하여 처음에는 단순 무식한 방법으로 2중 for문을 통해 문제에 접근했었습니다..😅 일자별 주식을 그 이후의 주식의 가격과 일일이 비교해보면서 가장 비싼 주식을 찾..