본문 바로가기

Algorithm

 (172)
[BOJ-14503][백트래킹/DFS] 빵집 - Java 문제 바로가기 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 2차원 배열에서 맨 왼쪽에서 맨 오른쪽까지 갈 수 있는 경로의 최대 개수를 구하는 문제입니다. 삼방 탐색으로 쭉~~ 가주면 됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[] dy = {-1, 0, 1}; static in..
[BOJ-14425][문자열 처리(Trie)] 문자열 집합 - Java 문제 바로가기 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어� www.acmicpc.net 문자열 집합이 주어지고 입력으로 들어오는 문자열이 집합에 속하는지 체크하는 문제입니다. 인풋이 크기 때문에 단순히 N^2로 풀면 안됩니당. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; import java.uti..
[2020 KAKAO BLIND RECRUITMENT][Trie] 가사 검색 - Java 문제 바로가기 코딩테스트 연습 - 가사 검색 programmers.co.kr 와 진짜 겨우 풀었네 공부 열심히 해야겠ㅅ브니다 문제에서 요구하는 걸 구하는건 크게 어렵지 않은데 효율성 테스트를 보기 때문에 무식하게 N^2 때리면 난리납니다. Trie라는 자료구조를 사용해서 멋있게 풀어야 합니다... 카카오 블로그 보고 겨우겨우 풀어씀니다.... 그와중에 queries 반대로 볼때는 뒤집어서 넣어야되는데 그거 안해서 식겁했습니다... import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Solution { static class TrieNode{ Map childNodes = new HashMap(); boo..
[BOJ-2206][시뮬레이션/BFS] 벽 부수고 이동하기 - Java 문제 바로가기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 어디서 어디까지의 최단 거리를 구하는 문제입니다. 최단 거리 구하는 문제는 웬만하면 BFS로 풀 수 있습니다. 다만 벽을 최대 한번 부수고 움직일 수 있기 때문에 한가지 더 고려해줘야 합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import..
[BOJ-17406][시뮬레이션/순열] 배열 돌리기 4 - Java 문제 바로가기 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 2차원 배열을 얼마나 잘 다루는지 요구하는 문제라고 생각합니다. 돌리는 연산의 순서에 따라 배열의 값이 달라지기 때문에 순열을 만들어서 모든 케이스를 체크합시다. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.ut..
[2020 KAKAO BLIND RECRUITMENT][시뮬레이션/완전 탐색] 자물쇠와 열쇠 - Java 문제 바로가기 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 휴.. .겨우 풀었슴니다.... 괜히 똘똘하게 풀어볼려다가 다 실패하고.. 완전탐색으로 풀었스빈다.. import java.util.ArrayList; import java.util.List; class Solution { static int M; static int N; static class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } public boolean check(int[][] entireMap) { for(int i ..
[BOJ-15686][시뮬레이션/조합] 치킨 배달 - Java 문제 바로가기 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 조합을 만들어서 그거갖고 문제에서 요구하는 답을 구하는 문제입니다. 2차원 배열이 입력으로 주어지지만 좌표값을 담은 리스트들로 표현해서 풀 수 있답니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java..
[2020 KAKAO BLIND RECRUITMENT][문자열 처리] 괄호 변환 - Java 문제 바로가기 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴� programmers.co.kr 괄호를 다루는 문제입니다. 파라미터의 조건이 많아서 고려해줘야 할게 비교적 적어서 쉽게 풀 수 있었씁니다. import java.util.Stack; public class Solution { public boolean isAlright(String s) { Stack stack = new Stack(); for(int i = 0; i < s.length(); i++) { if(!stack.isEmpty() && stack.peek() == '('..

티스토리툴바