본문 바로가기

분류 전체보기

 (308)
[백준] 11279 최대 힙(JAVA) 풀이 이 문제는 어렵게 생각할것 없이 그냥 우선순위큐를 사용하면 된다. 특이점으로는 오름차순이 아니라 내림차순으로 우선순위를 정해야하는데 나는 그냥 넣을때는 전부 - 부호를 붙혀서 넣었고 뺄때는 -부호를 다시 붙혀서 빼내었다. import java.io.*; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Bu..
[백준] 7562 나이트의 이동 (JAVA) 풀이 위의 문제는 BFS의 정석이라고도 할수있는 문제이다. 그렇다고 풀었는건 아니다... 문제에서 주어지는 나이트의 최단이동경로에 초점을 두어 최단경로를 구하는 알고리즘을 생각하다 보니 풀지 못하였던 것 같다. 그냥 다음으로 이동할때 이동하기전의 이동횟수에 하나씩 더해가다 어느 순간 goal의 좌표와 현재 좌표가 같게 되면 그때의 이동횟수를 출력하면 문제는 풀린다. 살짝 dp와도 비슷한 점이 있는것 같다. 느낀점은 구현만 확실히 해놓으면 부담없이 전부 탐색하면 될듯하다. package com.company; import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class ..
[백준] 1182 부분수열의 합 (JAVA) 풀이 살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다. 백트랙킹 문제를 더 풀어봐야 할것 같다. package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int N; static int S; static int count=0; static int Sum; static int[] Num; public static void main(String[] args) throws IOException { BufferedRea..
[백준] 9465 스티커 (JAVA) 풀이 이 문제는 쉬운 DP문제에 속하는 듯하다. 결국 못풀었지만... 일단 알고리즘의 기본 베이스는 DP를 통해 앞에 있던 수들중 가장큰 수를 구하는 것이다. 밑에 있는 코드에서 쉽게 알수있겠지만 DP의 점화식은 다음과 같다. DP[0][j] = MAX(DP[1][j-1] , DP[1][j-2]) + cost[0][j]이다. 나는 처음 이식을 보고 바로 뒤에(j-2)의 같은 행은 왜 비교를 안하는지 궁금했다. 그러나 잠깐 생각해보니 바로 풀렸다. 왜냐면 같은 행의 두번째 뒤까지 비교해서 구한다면(DP[0][j-2])이는 DP[0][j-2]에서 바로 현재 위치로 온다는 것인데 그렇다면 중간에 더하고 올수있는 대각선을 DP[1][j-1] 그냥 뛰어 넘어 버리기 때문에 이는 문제에서 요구하는 최대값이 될수없다..
[백준] 1541 잃어버린 괄호 (JAVA) 풀이 이문제는 어렵게 생각할 필요없이 현재 파싱한 문자열중에 -가 나온적이 있다면 그 뒤에 나오는 수들은 전부 빼버리면 된다. 왜냐면 문제에서 괄호를 적절히 처서 최소로 만들라고 했기때문에 -가 하나가 나오든 여러개가 나오는 한번 나온후라면 괄호를 나온만큼 치면 음수가 되기때문이다. 간단한 문제이기에 코드또한 짧고 이해하기 쉬울것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Bu..
[백준] 4963 섬의 개수 (JAVA) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 위의 문제는 예전에 풀었던 백준1012번과 동일하다 문제에서 갈수있는 섬의 개수를 구하라고 했는데 이는 DFS혹은 BFS로 탐색할수있는 섬들의 집합이 몇개나 있는지 물어보는 문제이다. 우선 상하좌우 대각선으로 갈수있는 집합을 만들어주고 그다음 BufferdReader로 읽어서 visit와 map을 초기화 시켜준다. 그 이후 만약 현재 위치가 바다가 아닌 섬이고 미방문한 지역중 섬인 지역..
[백준] 6603 로또 (JAVA) https://www.acmicpc.net/problem/6603 위의 문제는 DFS를 이용한 백트랙킹으로 풀수있다. 처음에는 문제를 계속 풀려고 해도 풀리지가 않아서 타 블로그의 글을 보았다. 그럼에도 잘 이해가 가지않아서 혼자 연습장에 끄적거리보기도 하고 유튜브에 강의를 찾아보기도 하였다. 그러던 중 정말 크게 도움이 된 강의의 주소를 올려놓겠다. https://www.youtube.com/watch?v=Ar40zcPoKEI - 코드없는 프로그래밍님의 강의이다. 아래의 코드를 통해서 내가 몰랐던것들과 새로 이해한것에 대해서 설명을 하겠다. 전역으로는 ary(원소들의 집합), k(집합의 크기), skip(현재 선택한 원소들에 대해서 나타내는 배열)과 출력을 할때 쓰일BufferedWriter를 선언했다..
DFS, BFS 복습(스택과 큐) 오늘은 BFS(큐)복습과 DFS는 재귀가 아닌 스택으로 해보았다. 직관적이면서 쉬운것은 재귀로 푸는것이지만 어느 하나에만 몰두해서 하다보면 스스로를 얽매이는 족쇄가 될것 같아 스택으로 풀려고 노력했다. 결과값은 잘나오는데 백준에서 틀렸다고 나오는 이유는 뭘까.. BFS는 그전에 하던 방식 그대로 여서 따로 더 설명할점은 없고 DFS는 아래와 같이 진행한다. 수정 - 혹은 오름차순으로 방문하고싶을떄는 선입후출의 특징을 이용해 그래프의 뒤부터 방문해도 될듯하다.(BFS의 탐색이 i=0부터 N까지 였으면 DFS는 i=N부터 0까지순으로 하면 가능할듯하다.) import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.uti..
애자일 소프트웨어 개발 선언 애자일 소프트웨어 개발 선언 우리는 소프트웨어를 개발하고, 또 다른 사람의 개발을 도와주면서 소프트웨어 개발의 더 나은 방법들을 찾아가고있다. 이 작업을 통해 우리는 다음을 가치 있게 여기게 되었다 공정과 도구보다 개인과 상호작용을 포괄적인 문서보다 작동하는 소프트웨어를 계약 협상보다 고객과의 협력을 계획을 따르기보다 변화에 대응하기를 가치 있게 여긴다. 이 말은, 왼쪽에 있는 것들도 가치가 있지만, 우리는 오른쪽에 있는 것들에 더 높은 가치를 둔다는 것이다. 공부를 하다보니 애자일 소프트웨어 개발선언이라는 것이 있어서 가져와보았다. 언젠가는 다시보겠지..
[spring] SOLID 원칙 최근 스프링을 공부하면서 SOLID 원칙(객체지향 5대원칙)이라는 단어를 들어보았다. 강의에서 말하는 내용을 듣기만 해서는 이해가 쉽게 가지않고 잊어버리지 않게 위해서 다시 정리하면서 포스팅을 할려고 한다. 객체지향 5대 원칙(SOLID원칙)이란 SRP(단일 책임 원칙), OCP(개방-폐쇄 원칙), LSP(리스코프 치환 원칙), DIP(의존 역전 원칙), ISP(인터페이스 분리 원칙)을 말하며, 앞자를 따서 SOILD 원칙이라고 부른다. 프로그래머가 시간이 지나도 유지 보수와 확장이 쉬운 소프트웨어를 만드는데 이 원칙들을 적용할 수 있다. 1. Single Responsibility Principle (단일 책임 원칙), SRP "소프트웨어의 설계 부품(클래스, 함수 등)은 단 하나의 책임만을 가져야 한..

티스토리툴바