Ikjo's Technology blog

문제 설명 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 접근 방법 입력받은 사용자별 기록들(String[] record)에 대해 순서대로 split를 통해 상태(Enter, Leave, Change), 아이디, 닉네임을 분리하고 별도의 UserState 구조체를 선언하여 사용자의 상태와 아이디를 저장하여 List 자료구조에 add 합니다. 다만 Change의 경우 기존 사용자의 닉네임을 바꾸는 작업이므로 UserState에 포함시키지 않습니다. UserState의 구조체는 다음과 같이 선언해주었습니다. s..

문제 설명 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 회고 해당 문제는 BFS를 이용하여 풀이할 수 있었는데, 익은 토마토를 기점으로 익지 않은 토마토들이 점차 확산되어가며 익어간다는 점 그리고 익는데 며칠이 걸리는지를 구해야 한다는 점에서 BFS를 떠올릴 수 있었습니다. 이때 DFS를 사용하지 않았던 이유는 익은 토마토들이 여러 개 있을 때 익은 토마토들을 기점으로 동시 다발적으로 익지 않은 토마토들로 확산되어 갈텐데 DFS는 우선적으로 하나의 익은 토마토를 기점으로 확산시..

문제 설명 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 접근 방법 (1 단위로 압축 시) 문자열의 첫번째 문자를 가지고 두번째, 세번째 등 각각의 문자를 순서대로 비교하면서 일치하는지 여부를 검사합니다. (1번 검사 작업에 대해) 일치하는 경우 multiple 변수(초기값 1)의 값을 1씩 증가시킵니다. (1번 검사 작업에 대해) 일치하지 않는 경우 별도의 압축 문자열(zipString) 변수에 multiple 값(문자열 형태로)과 첫번째 문자를 추가 할당해줍니다. 이후 두번째 문자를 가지고 세번째..

문제 설명 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 회고 해당 문제에서 요구하는 것은 오름차순으로 동전의 가치가 주어졌을 때 해당 동전들로 k원을 만드는데 필요한 동전 개수의 최솟값입니다. 이 문제는 그리디 알고리즘의 유형으로 정답을 구하기 위해서는 가장 가치가 큰 동전들을 토대로 k원을 구성해야합니다. 이때 입력 받은 동전의 가치들을 저장한 배열은 오름차순으로 정렬되어있으므로 배열의 끝 부분부터 k원을 나누면서 몫이 존재할 때(1 이..

문제 설명 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 회고 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. 우선 문제에서 요구하는 것은 최소 m 만큼의 나무 높이를 얻기 위해 n개의 나무를 자를 절단기의 최대 높이를 구하는 것입니다. 우선 이분 탐색을 위해 다음과 같이 n개의 나무의 높이를 배열 각각의 요소에 할당한 후 오름차순으로 정렬합니다. for (int i = 0; i < n; i++) { trees[i] = Integer.parseInt(st..