알고리즘 썸네일형 리스트형 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 + .. 더보기 백준 - 13614 행복 유치원(Java) https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 그리디 문제입니다. 문제를 요약하면, 구간(조)를 나눠 구간에서 최대와 최소의 합이 가장 작게 만들어야 하는 문제입니다. 즉, 문제 풀이 순서는 다음과 같습니다. 구간을 나눈다. 최대와 최소의 차이를 구한다. 1. 구간을 나눈다. 최소로 차이를 만들기 위한 구간은 간격이 가장 큰 쪽부터 나누면 된다는 것입니다. 아래 그림으로 보겠습니다. 예제 입력과 같이 n 크기가 5이고,.. 더보기 백준 - 1707 이분 그래프(Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net bfs 문제입니다. 이분 그래프는 아래 그림과 같이 두 가지의 집합으로 구분할 수 있어야 합니다. 때문에, bfs로 완전 탐색을 하면서 두 가지 집합으로 구분하시면 됩니다. 아직 방문을 하지 않았다면 0(default), 1번 집합인 경우 2, 2번 집합인 경우 1로 구분하시면 됩니다. if(visited[nn] == 0){ qu.add(nn); visited[nn] = 3 - visited[cn.. 더보기 프로그래머스 - 미로 탈출(Java) bfs 문제입니다. 시작 지점이 레버를 거쳐 종료 지점 까지 가는 최단거리를 구해야 합니다. 이는 각각 시작 -> 레버, 레버 -> 종료 경로의 최단 거리를 각각 구해서 그 결과를 합치면 됩니다. [구현 코드] class Solution { final int[] dx = {1, -1, 0, 0}; final int[] dy = {0, 0, -1, 1}; int n, m; public int solution(String[] maps) { int answer = -1; n = maps.length; m = maps[0].length(); Road start = null; Road lever = null; Road exit = null; char[][] map = new char[n][m]; for(int i.. 더보기 프로그래머스 - 혼자서 하는 틱택토(Java) 구현 문제입니다. 3*3 보드에 'O', 'X', '.'이 주어질 때, 해당 보드의 말판들이 틱택토 게임 규칙에 벗어나지 않는지 확인해야 합니다. 틱택토 게임 규칙은 다음과 같습니다. 'O'와 'X'를 번갈아 가면서 '.'위치에 놓는다. ('O'가 선공) 'O' 또는 'X'의 직선 길이가 3이되면 게임이 종료된다. 즉, 두 번째 조건에 의해 말판의 개수와 길이가 3인 직선의 유무를 확인하여 판단하면 됩니다. 'O'와 'X'의 말판 개수 차이는 무조건 1이내여야 합니다. 직선 판단의 조건은 아래와 같이 하면 됩니다. 'O'와 'X'의 직선이 모두 만들어질 때 하나의 직선이 만들어지면 게임이 종료되기 때문에 불가능하다. 'O'의 직선만 만들어질 때 선공이 'O'이기 때문에, 'X'와 개수가 같아질 수 없다... 더보기 이전 1 2 3 4 5 ··· 17 다음
