java 썸네일형 리스트형 [Algorithm/Java][백준] 2775번 부녀회장이 될테야 [BOJ] 2775번 부녀회장이 될테야 https://www.acmicpc.net/problem/2775 문제 접근 백준에서 에제로 준 입력과 출력을 하나씩 쓰다보면 규칙이 보이게 된다. 000 -> 0 001 -> 1 002 -> 2 003 -> 3 100 -> 0 101 -> 1 102 -> 3 103 -> 6 200 -> 0 201 -> 1 202 -> 4 203 -> 10 이때 103호에는 003호와 102호를 합친 값이 있고, 203호에는 103호와 202호를 합친 값이 있다. 이를 점화식으로 바꿔보면 (k0n)호 = k-10n호 + k0n-1호 코드로 바꿔보면 dp[floor][room] = dp[foor-1][n] + dp[floor][n-1]이 된다. 이를 코드로 바꾸면 다음과 같다. Co.. 더보기 [Algorithm/Java][백준] 14226번 이모티콘 [BOJ] 14226번 이모티콘 https://www.acmicpc.net/problem/14226 문제 접근 화면에 있는 이모티콘을 S개 만드는 최소 시간을 구하는 문제이다. 화면에 있는 이모티콘 개수와 클립보드에 있는 이모티콘 개수 그리고 시간 정보를 저장할 수 있는 Emoticon 클래스를 만들고 isVisited 배열을 화면에 있는 이모티콘 수와 클립보드에 있는 이모티콘 수를 고려할 수 있도록 2차원 배열로 만들었다. 그리고 BFS를 이용해서 화면에 있는 이모티콘을 클립보드에 저장하는 경우, 화면에 있는 이모티콘 한개를 제거하는 경우, 클립보드에 있는 이모티콘을 붙여넣는 경우 세가지를 고려해서 문제를 해결했다. 문제를 보고 이차원 배열로 해결할 생각을 하지 못해서 푸는데 꽤나 오래걸렸다...근데 .. 더보기 [Algorithm/Java][백준] 2252번 줄 세우기 [BOJ] 2252번 줄 세우기 https://www.acmicpc.net/problem/2252 문제 접근 위상 정렬을 통해서 쉽게 푼 문제이다. 위상 정렬이란 순환이 없는 그래프에서 정점간의 순서를 구할 수 있는 알고리즘이다. 각각의 학생들을 정점이라고 생각하고, 입력으로 들어오는 순서들을 그래프들의 간선이라고 생각하면 쉽게 문제가 풀린다. 위상 정렬이란 우선 들어오는 간선의 개수를 세는 linkCnt의 값이 0인 정점들을 큐에 넣고, 하나씩 큐에서 빼면서 해당 정점과 연결된 정점들에 대해서 linkCnt를 -1 해주고 다시 linkCnt의 값이 0인 정점들을 큐에 넣는 방식으로 진행된다. Code import java.util.ArrayList; import java.util.LinkedList; .. 더보기 [Algorithm/Java][백준] 1916번 최소비용 구하기 [BOJ] 1916번 최소비용 구하기 https://www.acmicpc.net/problem/1916 문제 접근 양의 가중치를 가진 간선으로 이루어진 그래프에서 최단 경로를 찾는 문제여서 다익스트라와 벨만포드 알고리즘 2개를 모두 적용해서 구현했다. 다익스트라 알고리즘은 우선순위 큐를 이용해서 시간복잡도를 줄였고, 다익스트라와 벨만포드 알고리즘은 포스트에 정리했다. [알고리즘] 다익스트라 & 벨만포드 Code 다익스트라 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Node implements Comparable { int to; int .. 더보기 [Algorithm/Java][백준] 1806번 부분합 [BOJ] 1806번 부분합 https://www.acmicpc.net/problem/1806 문제 접근 투 포인터를 이용해서 문제를 풀었다. deque와 이분 탐색을 이용해서도 풀 수 있다고 하는데 분류가 투 포인터라서 투 포인터를 사용해서 풀었다. start와 end인 두 개의 인덱스를 사용하고 sum이 t(목표 값)보다 작거나 같으면 end를 +1해서 한개를 더 더하도록 하고, sum이 t(목표 값)보다 크면 start를 +1 해서 합에서 한개를 빼서 목표 값에 접근하도록 한다. 투 포인터를 사용하게 되면 O(N)으로 문제를 해결할 수 있게 되는 장점이 있다. Code import java.io.BufferedReader; import java.io.IOException; import java.io.. 더보기 [Algorithm/Java][백준] 1700번 멀티탭 스케줄링 [BOJ] 1700번 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 문제 접근 예전에 운영체제 시간에 배웠던 페이지 교체 알고리즘과 비슷해서 쉽게 풀 수 있었다. 멀티탭에 자리가 있거나, 이미 꽂혀있을 때는 고려할 것 없이 그냥 꽂거나 넘어가면 되지만 자리가 없을때 고려해야 될 경우의 수가 있다. 경우의 수를 정리해 보면 다음과 같다. 멀티탭에 자리가 있는 경우 이미 멀티탭에 꽂혀 있는 경우 멀티탭에 자리가 없는 경우 3.1. 사용하지 않을 전자기기가 꽂혀 있는 경우 3.2. 모든 전자기기가 다시 사용할 전자기기인 경우 사용하지 않을 전자기기가 꽂혀 있으면 그 전자기기를 제거하고 새로운 전자기기를 꽂으면 해결된다. 모든 전자기기가 다시 사용할 전자기기인 경우 우선순위를.. 더보기 [Algorithm/Java][백준] 1062번 가르침 [BOJ] 1062번 가르침 https://www.acmicpc.net/problem/1062 문제 접근 백트래킹을 이용해서 모든 경우의 수를 탐색해보는 문제였다. 시간 복잡도를 줄이기 위해서 모든 단어가 포함하는 anta, tica 에 포함된 5개의 단어를 필수 단어로 포함시키고, 공백으로 바꿔주어서 탐색해야 하는 단어의 길이를 줄였고, 배울 수 있는 단어가 5개 보다 적을때 0, 26개 일 때 모든 단어를 배울 수 있으므로 n을 출력했다. 백트래킹을 할 때도 a~z까지 순차적으로 학습하기 때문에 시작 인덱스를 매개변수로 추가해서 이미 지나간 곳은 탐색하지 않도록 했다. Code import java.io.BufferedReader; import java.io.IOException; import jav.. 더보기 [Algorithm/Java][백준] 2504번 괄호의 값 [BOJ] 2504번 괄호의 값 https://www.acmicpc.net/problem/2504 문제 접근 Stack을 이용해서 열린 괄호를 저장하고, 괄호가 닫힐 때 X값을 다시 스택에 저장한다. 괄호 속에 숫자가 있으면 그 숫자들을 다 더해서 해당 괄호 값을 곱해주었다. 그리고 스택을 Character 자료형으로 하면 괄호와 숫자를 구분하지 못하기 때문에, String으로 해서 이 경우를 해결했다. 코드가 너무 복잡하고 올바른 괄호가 아닌것을 검사하기가 까다로웠다... Code import java.util.Scanner; import java.util.Stack; public class BOJ2504 { public static void main(String[] args) { Scanner sc .. 더보기 이전 1 2 3 4 ··· 8 다음
