본문 바로가기
반응형

분류 전체보기714

깊이/너비 우선탐색(DFS / BFS) : 단어변환 ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr * 해결과정 프로그래머스 레벨별 풀이는 모두 유형을 제공하고 있습니다. 이미 힌트를 얻는다는 점에서 해결책을 떠올리는 과정은 성장할 수 없으나 연습하기는 좋습니다. 이 문제는 DFS, BFS 모두로 해결이 가능한 문제입니다. 그 중에 저는 DFS로 풀었습니다. DFS로 풀 때 항상 주의해야 할 것이 있습니다. 종료조건, 반복내용 + .. 2020. 11. 7.
10799 : 쇠막대기 ( 백준 / java ) www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net * 풀이 과정 이 문제는 괄호에 관한 문제이기 때문에 stack을 이용해야겠다는 생각을 했습니다. 그리고 막대를 자르는데, 계층마다 수가 늘어나기 때문에 '('가 증가할 때마다 변수를 같이 증가시켰습니다. 혹시 여러분 예시문제 2개가 제대로 맞지 않는다면 '()' '(())' '(()())' 와 같은 비슷하지만 간단한 케이스를 만들어보고 한번 테스트해보기 바랍니다. 테스트를 만들어서 반례를 찾는 것도 실력입니다. 가끔 너.. 2020. 11. 7.
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[][].. 2020. 11. 7.
순수 java 코드를 이용한 Spring-MVC 등록 과정 개요 Spring MVC구조에 대해 공부하고 사용하다가 어떻게 순수 java 코드를 통해 Spring-MVC라는 패턴을 인식하고 작동을 시켜줄 수 있을까 궁금했습니다. Spring Boot는 상당부분 많은 설정들을 알아서 해주기 때문에 Spring Framework를 사용해서 설정해보며 공부해보도록 하겠습니다. 워밍업 Servlet 3.0 이상부터 javax.servlet.ServletContainerInitializer의 등장으로 web.xml 대신 코드 기반으로 servlet, filter, listener 컴포넌트 등록이 가능합니다. 스프링을 이용한다면 SpringServletContainerInitializer를 통해 이 전략을 사용합니다. 최종으로 개발자가 실제 구현해야 할 것은 org.spri.. 2020. 11. 5.
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 2020. 11. 3.
32 : Longest Valid Parentheses ( leetcode / java ) * 해결 과정 괄호에 관한 문제이기 때문에 스택을 떠올렸고 스택을 이용하기로 생각했습니다. 그래서 저는 '(' 가 나오는 지점에서 검사를 시작하도록 했습니다. 그래서 ')'의 갯수에 따라 다시 변수를 + - 해준다음에, 최종적으로 0이 나오면 통과이고 아니면 종료입니다. 또한 ')'가 훨씬 많아 변수가 음수가 되면 종료입니다. 하지만 이 풀이법은 시간효율이 너무 좋지 않습니다. 먼저 확인해보겠습니다. class Solution { int answer=0; public int longestValidParentheses(String s) { for(int i=0;i 2020. 11. 3.
예산 : 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.. 2020. 11. 3.
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 .. 2020. 11. 2.
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.. 2020. 11. 2.
반응형

티스토리툴바