알고리즘 썸네일형 리스트형 백준 - 3197 백조의 호수(Java) 구현 문제입니다. 물과 인접한 얼음이 1초마다 없어지는데, 몇 초 후에 두 마리의 백조가 만나는지 구하는 문제입니다. 얼음을 녹이고 백조를 움직이면 입력 범위가 매우 커 시간 초과가 발생했습니다. 때문에 저는 두 가지 방법을 통해 이 문제를 해결했습니다. 얼음 두께 구하기 한 마리의 백조만 이동 1. 얼음 두께 구하기 얼음 두께는 물과의 최대 거리가 됩니다. 즉, 얼음 두께만큼 시간이 지나야 해당 얼음이 녹아 물이 됩니다. 이는 네 방향으로 알 수 있습니다. 다음과 같은 얼음이 있다고 하겠습니다. 우선 오른쪽 방향으로 얼음의 두께를 확인합니다. 물을 0로 두고, 얼음을 1로 둔 상태의 누적 최솟값을 구하는 것과 같습니다. 왼쪽으로 최솟값을 갱신합니다. 아래로 최솟값을 갱신합니다. 위로 최솟값을 갱신합니다.. 더보기 프로그래머스 - 상담원 인원 (Java) 구현, 그리디 문제입니다. 상담원 인원과 참가자의 상담 요청 정보가 주어졌을 때, 대기시간을 최소로 하는 시간을 구하는 문제입니다. 우리가 해야하는 것은 대기시간을 최소로 하도록 상담원 배치를 하고 나서, 최소 대기 시간을 구해야 합니다. 어떻게 하면 최소 대기 시간을 만들도록 상담원을 배치할 수 있을까요? 문제 조건에 의해 모든 유형에는 상담원이 한 명씩은 배치되어야 합니다. 우선 한 명씩 상담원을 배치하고, 상담원이 추가되었을 때 가장 많이 대기 시간이 줄어드는 타입에 우선적으로 배치하면 됩니다. 가장 많이 대기시간이 줄어들게 되면 전체에서도 최소로 만들어지는 경우이로 만들어지기 때문에 그리디로 접근할 수 있습니다. 문제 접근 순서는 다음과 같습니다. 유형마다 상담 요청 시간 분리 각 유형마다 1~(.. 더보기 백준 - 17825 주사위 윷놀이 (Java) 구현 문제입니다. 문제 조건 자체는 이해하기 어려운 부분은 딱히 없는거 같습니다. 하지만, 이것을 코드로 구현하려니 마땅한 아이디어가 떠오르지 않았습니다. 3~4일간 이 문제만 붙잡고 백준 질문게시판에서 얻은 테스트 케이스를 직접 써보면서 경우의 수를 확인하고, 수많은 디버깅을 한 끝에 맞출 수 있었습니다. 제가 문제를 해결한 방법을 아래 글을 통해 공유하겠습니다. 1. 그래프로 윷놀이 판 구현하기 문제에서 주어지는 주사위 윷놀이 판의 모습은 아래 그림과 같습니다. 이 모습을 보자마자 그래프를 떠올렸고, 그림을 그래프로 표현하고자 했습니다. 우선 파란색으로 갈 수 있는 곳을 지름길(Shortcut)이라 가정했습니다. 💡 [10, 20, 30에서 출발해 40까지의 길이 모두 지름길입니다.] 💡 [편의상 빨.. 더보기 백준 - 17822 원판 돌리기 구현 문제입니다. 1. 문제 설명 원판과 조건이 주어지고, 조건처럼 행동했을 때 원판에 남아있는 수의 총합을 구하는 문제입니다. 원판과 그에 인접한 위치를 이차원 배열 그림으로 나타내면 아래와 같습니다. 기본적으로 4방 탐색을 하면서 세로는 위아래 끝이 연결되지 않습니다. 가로는 양옆 끝이 연결되어 있습니다. 또, 원판이 회전하게 되면 가로의 방향으로 만 움직입니다. D가 0일때는 아래와 같이 오른쪽(시계 방향)으로 움직입니다. D가 1일때는 아래와 같이 왼쪽(반시계 방향)으로 움직입니다. X는 회전할 세로 위치를 의미하며, K는 회전의 양을 의미합니다. 2. 접근 방법 접근 방법은 문제 자체에서 주어진 그 순서와 크게 다르지 않습니다. x의 배수의 위치의 배열들을 회전한다. d가 0일경우 오른쪽(시계 .. 더보기 SW Expert - 달란트 2 (Java) 그리디 문제입니다. 문제를 요약하면 다음과 같습니다. N개를 P 묶음으로 나누고, 각 묶음의 곱이 최대가 되게 하라. 만약 P가 3이게 된다면 아래와 같은 식이 도출될 수 있습니다. 합이 일정할 때, 곱을 최대로 하려면 어떻게 해야 할까요? 각 원소의 차이를 최소로 하면 됩니다. N = 8, P = 3 일 때, 아래와 같이 달란트 묶임이 만들어집니다. (2, 3, 3) 과 같이 그 차이가 최소로 만들 때 곱이 최대가 됩니다. [구현 코드] import java.util.*; import java.io.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new Buff.. 더보기 SW Expert - 1812 수정이의 타일 자르기(Java) 그리디 문제입니다. 이 문제를 풀기 위해서는 한 가지 아이디어가 필요합니다. 필요 타일의 크기 중 가장 큰 것 먼저 자른다. 즉, 내림차순으로 문제를 해결하면 됩니다. M*M에서 N*N 만큼 타일을 자르면 아래의 그림과 같이 구역이 나눠집니다. 즉, M*(M-N) 과 (M-N)*N이 남습니다. 문제 전체 접근 순서는 다음과 같습니다. 필요 타일의 크기(N*N)들을 구해서 리스트에 저장한다. 크기를 내림차순으로 정렬한다. 내림차순으로 정렬된 요소를 하나씩 확인하면서 타일을 자른다. 타일을 자를 수 있으면 자르고 남은 두 개의 타일을 저장한다. 타일을 자를 수 없다면 하나의 새로운 타일을 추가하고 타일을 자른다. [구현 코드] import java.io.*; import java.util.*; public .. 더보기 SW Expert - 1267 작업 순서 dfs 문제입니다. 선행 조건이 있는 방향 트리가 주어졌을 때, 순차적으로 탐색할 수 있는 순서를 구하는 문제입니다. 문제 접근 방법은 다음과 같습니다. 각 시점에서 시작한다. 연결된 노드로 이동한다. 선행 조건을 만족하지 않으면 이동하지 않는다. 선행 조건을 만족하면 이동한다. 현재 노드에서 더이상 이동할 게 없으면, 선행 조건이 완료된 노드로 이동한다. 모든 노드가 연결되면 전부 종료한다. 코드 이해를 돕기위해 리팩토링을 하지 않은, 날것의 코드로 공유합니다. [구현 코드] import java.io.*; import java.util.*; public class Solution { private static int v; private static List answer; private static M.. 더보기 백준 - 1339 단어 수학(Java) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디 문제입니다. 단어의 위치에 따라 가중치를 더해 가장 큰 가중치를 가진 문자부터 숫자를 할당하면 됩니다. 말로만 하면 이해가 힘드니 예시로 보겠습니다. /* 'A'~'Z'는 0~9의 숫자이므로 각 일의 자리라 생각했을 때, 아래 주석과 같은 다항식이 나옵니다. */ 10 ABB // 1. 100*A + 10*B + 1*B BC // 2. 10*B + 1*C BC // 3. 10*B + .. 더보기 이전 1 2 3 4 ··· 16 다음
