본문 바로가기

Algorithm/코드 풀이

 (183)
백준: 17144번 (미세먼지) [JAVA] 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 문제에서 요구하는 대로 공기청정기를 통한 먼지의 이동 함수, 각 먼지들이 퍼지는 함수를 구현 주어진 T초마다 이들을 반복 호출 후, 남은 먼지들의 총 합을 계산해 반환 문제 해결을 위한 알고리즘 구현 난이도는 거의 없지만, 문제 자체에서 요구하는 로직 구현이 상당히 복잡하여 이들을 구현하는 것이 핵심인 문제이다. 우선 문제에서도 보이다시피 초마..
백준: 2638번 (치즈) [JAVA] 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 우선 주어진 데이터를 저장할 2차원 배열 초기화 외부와 접촉한 공기를 체크하는 BFS 함수를 통해 2차원 배열에 표시 전체 2차원 배열 속 녹을 수 있는 치즈 좌표를 큐에 저장한 후, 전체 큐 속 치즈 좌표들을 공기로 바꾸며 추가적인 외부와 접촉한 공기 표시 작업을 진행 3번의 과정을 전체 while문으로 돌며 그 때마다 answer..
프로그래머스: 다단계 칫솔 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 주어진 enroll, referral 배열을 한 번에 돌며 이름을 인덱스화, 해당 이름(노드)의 상위 노드를 저장 이후 주어진 seller, amount 배열을 돌며 나누어 가질 이익금을 계산 후 누적 문제에서도 예시로 보여진 것처럼 우선 문제 해결을 위해선 주어진 데이터들을 가지고 트리를 구성할 수 있어..
프로그래머스: 최고의 집합 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 길이 n만큼의 배열을 생성 s를 n으로 나눈 몫을 각 배열 요소에 넣고, 남은 나머지 개수만큼 배열 요소들에 +1 문제에서 요구하는 각 원소의 합이 s만큼이고 곱이 최대가 되기 위해서는, 각 요소들이 최대한 s/n이 되도록 고르게 나누어져야 한다. 그렇기 때문에 s/n의 값이 0이라면 ..
프로그래머스: 풍선 터트리기 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 배열의 좌측에서 우측으로 진행하며 0부터 현 위치까지의 최소값 계산해 저장 배열의 우측에서 좌측으로 진행하며 배열 마지막부터 현 위치까지의 최소값 계산해 저장 배열 양 끝을 제외한 각 위치(i)에 대해 0~i-1 까지의 최소값, 현 위치 값, i+1~배열 마지막 까지의 최소값 3개를 비교해 값 계산. (이 때 현 위치 값이 남은 2개의 값보다 크지만 않다면 답 +1) 문제에서 요구하는 과정(인접한 2개를 뽑아 계산)을..
프로그래머스: 야근 지수 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 주어진 works 배열을 오름차순으로 정리한 다음, 최소 작업량 기준으로 이후 작업들에 대해 차이를 더해 누적 계산 (추가로 작업량의 총합도 계산) 이후 반복문을 통해 최소값 기준 차이나는 작업들의 누적합(diffWorkSum)이 소화 작업량(n)보다 작을 때까지 기준 최소값을 높임 추가로 (di..
프로그래머스: 숫자 게임 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 주어진 A, B 배열을 오른차순 정렬할 수 있는 각각의 우선순위 큐(pqA, pqB) 생성 후 A와 B 배열의 요소를 모두 삽입 이후 pqB의 숫자들이 모두 없어질 때까지 pqA와 pqB 숫자를 뽑아 비교 만약 뽑은 숫자에서 pqB 쪽이 더 크면 답 + 1 그렇지 않다면 pqB 쪽에서 뽑은 숫자가..
프로그래머스: 스티커 모으기 2 [JAVA] 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 풀이 전체적인 풀이 과정은 다음과 같다. 쉽게 풀을 수 있는 sticker 배열 길이가 4 이하인 경우 단순히 뽑아 비교 그보다 긴 sticker 배열에 대해선 2개의 dp 배열(마지막 값 포함되는 경우, 마지막 값 포함안하는 경우)을 통해 누적 값 (현 위치 기준 2번째, 3번째 인덱스 뒤 dp 배열 중 최대값 + 해당 위치 스티커 ..

티스토리툴바