Algorithm (66) 썸네일형 리스트형 10799 : 쇠막대기 ( 백준 / java ) www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net * 풀이 과정 이 문제는 괄호에 관한 문제이기 때문에 stack을 이용해야겠다는 생각을 했습니다. 그리고 막대를 자르는데, 계층마다 수가 늘어나기 때문에 '('가 증가할 때마다 변수를 같이 증가시켰습니다. 혹시 여러분 예시문제 2개가 제대로 맞지 않는다면 '()' '(())' '(()())' 와 같은 비슷하지만 간단한 케이스를 만들어보고 한번 테스트해보기 바랍니다. 테스트를 만들어서 반례를 찾는 것도 실력입니다. 가끔 너.. 4963 : 섬의 개수 ( 백준 / java ) www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net *해결 과정 BFS를 통해서 섬을 계속 확인하면서, visited를 이용해 섬을 방문했는지 안했는지 확인합니다. 특히, 상 하 좌 우 4방향을 살피는 것 뿐만 아니라 대각선도 포함하기 때문에 같이 세주어야 합니다. import java.util.*; public class Main { static int N; static int M; static int[][] array; static boolean[][].. 20 : Valid Parentheses ( leetcode / java ) * 해결 방법 마찬가지로 괄호는 stack에 관한 문제입니다. 단, 이 문제에서는 괄호 모양이 3개가 있습니다. 이 괄호모양이 유효한지 확인해야 합니다. 정상적인 괄호라면, ')' '}' ']'가 나올 때 stack.peek()이 해당 괄호와 맞는 모양이어야 한다는 것입니다. 따라서 그것을 체크해주면서 하나씩 풀이하면, O(N)에 확인이 가능합니다. import java.util.*; class Solution { public boolean isValid(String s) { Stack stack = new Stack(); for(int i=0;i 32 : Longest Valid Parentheses ( leetcode / java ) * 해결 과정 괄호에 관한 문제이기 때문에 스택을 떠올렸고 스택을 이용하기로 생각했습니다. 그래서 저는 '(' 가 나오는 지점에서 검사를 시작하도록 했습니다. 그래서 ')'의 갯수에 따라 다시 변수를 + - 해준다음에, 최종적으로 0이 나오면 통과이고 아니면 종료입니다. 또한 ')'가 훨씬 많아 변수가 음수가 되면 종료입니다. 하지만 이 풀이법은 시간효율이 너무 좋지 않습니다. 먼저 확인해보겠습니다. class Solution { int answer=0; public int longestValidParentheses(String s) { for(int i=0;i 예산 : Summer/Winter Coding(~2018) ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/12982?language=java 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr *해결과정 dp로 푸는 방법과 일반적으로 접근하는 방법 2가지가 있다. 여기서 동전은 중복되서 사용되지 못하기 때문에 dp보다는 if문을 통해 바로 이동시켜 주는 것이 편리하다. dp로 계산하면 오히려 불필요한 연산들을 계속하여 O(동전의 갯수*예산)의 시간복잡도를 나타내고 통과는 하지만 효율적인 결과는 내지 못한다. 1. DP import java.ut.. 14430 : 자원 캐기 ( 백준 / java ) *해결 과정 오른쪽과 아래쪽만 이동하는 것에 유의하여 최대탐색 할 수 있는 숫자를 구하는 것이다. 그렇다면, BFS, DFS의 접근이 아니라 DP의 접근을 하는 것이 딱 눈에 띈다. 행이 0일때와, 열이 0일 때 2가지 경우를 나누어 먼저 초기 작업을 하고 이후에 (1,1)부터 왼쪽과 위쪽 값 중에 큰 값을 자신과 더하면서 업데이트하면 된다. 마지막으로 (N-1,M-1)의 숫자를 출력한다. 정형화 된 문제이다. package bj; import java.util.*; public class Main { static int N; static int M; static int[][] array; public static void main(String[] args) { // TODO Auto-generated .. 538 : Convert BST to Greater Tree ( leetcode / java ) * 해결 과정 BST이므로 이진탐색 트리임에 유의합니다. 하지만 이 문제에서 딱히 상관은 없습니다. 주어진 Tree에서 val값들을 변경 해야 합니다. 처음에는 어떤 방식과 흐름인지 이해하지 못했습니다. 단순히 전위순회, 중위순회, 후위순회 3가지 안에 포함되어 있을 것이라고 생각했습니다. 하지만 오른쪽 맨 아래로 이동 후, 부모로 올라오고 다시 왼쪽 노드로 가는 방식이었습니다. 문제가 원하는 순회의 방법으로 적절하게 이동할 수 있는지가 관건입니다. class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if(root!=null) { convertBST(root.right); sum += root.val; root.val = s.. 501 : Find Mode in Binary Search Tree ( leetcode / java ) *해결 과정 이진탐색 트리라는 것을 친절하게 설명하고 있습니다. 그것보다도, 중복된 요소를 찾고 list로 반환하는 것이 더 중요해보입니다. Integer만을 다루는 Map의 형태이며 중복을 찾아야 하기 때문에 모든 요소 값에 따라서 등장할 때마다 +1씩 하도록 했습니다. 그리고 처음부터 순회하면서 value값이 최대로 큰 경우를 고르고 key값을 list에 넣어서 반환합니다. import java.util.*; class Solution { Map map = new HashMap(); public int[] findMode(TreeNode root) { if(root==null) return new int[]{}; DFS(root); int max = Collections.max(map.values().. 이전 1 2 3 4 5 6 7 ··· 9 다음
