'Algorithm' 태그의 글 목록

본문 바로가기

Algorithm

[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][백준] 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 .. 더보기

[Algorithm/Java][백준] 1987번 알파벳 [BOJ] 1987번 알파벳 https://www.acmicpc.net/problem/1987 문제 접근 가로 R, 세로 C로 된 보드에 대문자 알파벳이 적혀있고, 가장 왼쪽 위부터 알파벳 당 한번씩만 방문해서 가장 멀리 갈 수 있는 길이를 구하는 문제이다. 처음에는 아무생각 없이 bfs로 했다가 생각해보니까 dfs가 더 맞는 것 같아서 방향을 틀었다. 처음에는 보드에 방문 여부를 저장하는 isVisited와 알파벳 방문 여부를 저장하는 alphabetVisited를 사용하려 했는데, 생각해보니까 한번 방문한 알파벳은 방문하지 못하니까 보드에 방문여부를 저장할 필요가 없고, 경로를 String으로 계속 추가해가면서 하면 알파벳 방문 여부도 따로 저장하지 않아도 될 것 같아서 dfs에 가려는 x,y와 지금.. 더보기

이전 1 2 3 4 ··· 8 다음

티스토리툴바