본문 바로가기

Algorithm

(172)
[2020 KAKAO BLIND RECRUITMENT][BFS/시뮬레이션] 블록 이동하기 - Java 문제 바로가기 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr ㄷ,ㅡㅡㅡㅡ디어~~~~~ 멀고도 험했던~~~~~~ 카카오오오오오오 작년 기출을 다 푸러부러슴ㄴ니다~~~~~ 진짜 오래 걸렸ㄴ ㅔ;;; 암튼 이 문제는.... 죽어라 풀었던 BFS 종류입니다... 하지만 갓카오 블채 마지막 문제이니만큼 예삿놈이 아니었습니다.... int[] dy = {1, -1, 0, 0}; int[] dx = {0, 0, 1, -1}; static class Robot{ int y, x, d; // d 방향으로 한 칸 더 있음을 의미. 0: 가로, 1: 세로 ..
[SSSP(1)] Dijkstra Algorithm Single Source Shortest Path Single Source Shortest Path란 하나의 출발점(Single Source)에서 모든 노드까지 도달하는데 걸리는 비용(시간)을 계산하여 최단 경로를 구하는 것입니다. 우선 최단 경로의 정의는 간선의 가중치가 있는 그래프에서 두 노드 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로라고 할 수 있습니다. 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 사용할 수 있습니다. 음수 가중치가 있을 때는 벨만-포드 알고리즘을 사용할 수 있습니다. 요것은 다음에 정리를 해보겠습니다. 참고로 모든 노드들에 대한 최단 경로(All Pairs Shortest Path)로는 플로이드-와샬 알고리즘이란게 쓰입니다. 얘는 삼중 for문으로 간단하게 구현..
[BOJ-18513][BFS] 샘터 - Java 문제 바로가기 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 신박한 BFS 문제입니다. 입력으로 들어올 수 있는 샘터의 위치가 무려 -1억~1억임니다. 억소리가 납니다. import java.io.*; import java.util.*; public class Main { static int[] dx = {1, -1}; static final int HMIL = 100000000; static class Dir{ int cur, next; Dir(int cur, int next)..
[2020 KAKAO BLIND RECRUITMENT][순열] 외벽 점검 - Java 문제 바로가기 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 힘드네여... 원형 모양을 어떻게 표현할지는 쉽게 생각났는데,,,, 휴.. import java.util.*; class Solution { boolean[] v; int answer; List perm = new LinkedList(); List between; public void wallCheck() { List temp = new ArrayList(between); for(int k = 0; k < temp.size(); k++) { int ..
[BOJ-2800][문자열 처리/비트 마스킹/스택] 괄호 제거 - Java 문제 바로가기 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 약간 카카오스러운 문제라고 생각합니다. 막 엄청 고오급 알고리즘을 요하는 문제는 아니지만 구현하는데 쪼끔 애먹었습니다.. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..
[BOJ-15961][슬라이딩 윈도우] 회전 초밥 - Java 문제 바로가기 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 먹을 수 있는 초밥의 가짓수의 최댓값을 구하는 문제입니다. 초밥 개수가 최대 300만개이기 때문에 무식하게 N^2 하면 난리가 납니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public..
[SWEA-3234][백트래킹] 준환이의 양팔저울 - Java 백트래킹 문제입니다. 문제의 제한 사항에 맞게 안되는 경우는 걍 안가면 됩니다. 시간이 빡빡하게 매겨집니다. 그래서 별짓 다해봤습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Solution { int N; int ans; void dfs(int cnt, int[] w, boolean[] v, int l, int r) { if(cnt == N) { ans++; return; } f..
[BOJ-5052][Trie] 전화번호 목록 - Java 문제 바로가기 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 트라이를 활용하는 가장 기본적인 문제인가봅니다. 백준 트라이 태그에 젤 위에 있는 문젭니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main{ public static void main(..