전체 글200 다익스트라 알고리즘 데이크르스라 알고리즘 Dijkstra Algorithm 일명 다익스트라 알고리즘이라고도 한다. - 보통 음의 가중치가 없는 가주치 방향 그래프를 기준으로 최소 비용으로 노드를 방문하거나 노드를 이어가는 문제들에 많이 쓰인다 => 가중치 방향 그래프란 노드에서 다른 노드로 갈 때 일정한 비용이 드는 그래프를 의미한다. - 기본적으로 O(V^2) 의 시간복잡도를 가지나 PriorityQueue 나 sort 를 사용해서 O(VlogV) 의 시간 복잡도를 만들어서 계산하게 된다. 다익스트라 알고리즘 코드 보통 아래와 같은 순서로 코드 작성한다. 0. 정점과 비용을 위한 Edge class 를 만들어둔다 1. n번째 노드에서의 최소 cost 로 방문할 수 있는 도로를 찾기위해 PriorityQueue 를 사용한다.. Java - 알고리즘 2022. 8. 27. 백준 - 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 방법 이전에 풀었던 1922 네트워크 연결 문제와 아주아주아주 동일한 문제 사실 가장 큰 차이점은 마을을 두개로 분리했을 때 도로 최소 유지비용을 찾는 것이다. 이 문제에서 가장 고민했던 부분이 바로 저 부분이었다. 최소 신장 트리를 만들어서 하는 것은 알겠는데...대체 어떻게 두개로 나누지...? 그리고 두개로 나눈 후 어떻게 최소 유지비용을 찾지..?.. Java - 알고리즘 2022. 8. 27. Spring Web Chatting : 스프링 채팅 만들기 웹소켓 맛보기 시작하면서 오랜만에 돌아온 자바 갖고놀기 프로젝트!! 이번에는 예전부터 정말정말정말 해보고 싶었던 spring 과 웹소켓을 이용한 채팅 프로그램 구현을 해보려고 합니다. 오늘 뼈대 만들기를 시작해서 stomp 를 사용한 채팅 구현, 파일 업로드, DB 와 연결 등등 여러가지를 더해서 만들겠습니다! 추가로 아래 코드 및 설명에서 등장하는 새로 공부하게된 어노테이션과 개념들은 따로 정리하도록 하겠습니다 그럼 시작하겠습니다 필수 라이브러리 임포트 - gradle 에 websocket 임포트 // WebSocket implementation 'org.springframework.boot:spring-boot-starter-websocket' websocket Handler 작성 웹 소켓 클라이언트로부터 채팅 메.. 토이 프로젝트/Spring&Java 갖고놀기 2022. 8. 24. 백준 - 1922 네트워크 연결(feat. 크루스칼 알고리즘) https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 방법 내가 무식해서 때문에 용감해져서 도전했던 문제ㅠ.ㅠ 사실 그래프 문제고 탐색하는 문제이기 때문에 DFS 나 BFS 로 하면 되는 문제겠네 하면서 풀었는데 당연히 다르게 푸는 문제였고, 메모리 초과만 5번은 뜬 것 같다. 2시간쯤 지나서 뭔가 이상하다고 느꼈고, 찾아보니 DFS 도 아니고, BFS 도 아니고 크루스칼 알고리즘과 이를 위한 union-find 구현을 통해 푸는 문제라는것을 알았다. 오늘도 새로운 것을 알아간다ㅋㅋㅋㅋ 이 문제는 최소 신장 트리를 찾는 문제이고, 이.. Java - 알고리즘 2022. 8. 24. 백준 - 1712 손익분기점 풀이 방법 매번 느끼는건데 백준에서의 수학 관련된 문제들은 옳곧이 수학적인 계산을 하는 것보다는 일종의 '꼼수'를 발견하는게 중요하다고 느낀다. 저번 A->B 문제도 그렇고, 이 문제도 그렇다. 오히려 수학 계산을 정말 하면 시간초과가 터지는 그런...? 사실 문제를 계산한다 라는 느낌보다는 '순수익이 어떻게 기준점을 넘길까?' 를 생각해보면 쉬워지는 문제이다. 예컨데 순수익을 먼저 계산한 후 순수익을 기준으로 고정비용을 몇일만에 넘길 수 있는가? 를 생각하면 되는 문제이다. A = 1000, B = 70, C = 170 인 경우 1일차 : 1000+70*1 , 170*1 을 비교 2일차 : 1000+70*2 , 170*2 을 비교 n일차 : 1000+70*n , 170*n 을 비교 이때 고정비용인 A .. Java - 알고리즘 2022. 8. 23. 백준 - 5397 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 방법 실버 2 문제라서 그래도 할만할 줄 알고 편하게 도전했다가 망해버린 문제 처음에는 ArrayList 로 접근해서 풀어보려고 했는데 문제를 읽다보니까 이렇게 풀어서는 안되는구나...를 끝없이 느끼고 LinkList 로 전환하여서 풀었다. 솔직히 LinkList 를 Queue 구현할때만 사용하고, 심지어 List 의 다양한 기능을 위해 사용하는 ListIterator 는 처음 써보는.. Java - 알고리즘 2022. 8. 22. 백준 - 2798 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, .. Java - 알고리즘 2022. 8. 21. 백준 - 11652 카드 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 .. Java - 알고리즘 2022. 8. 20. 백준 - 3055 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의.. Java - 알고리즘 2022. 8. 19. Spring - 예외 상황 처리 1) Servlet 예외 처리 : 404 error, 500 error 1. 서버 예외 처리 서버를 다루면서 다양한 에러를 만나게 된다. 특히나 서버단에서 프로그래밍을 잘못하면 404, 500 등등 엄청나게 다양한 오류를 클라이언트는 마주할 수 밖에 없다. 이때 이런 오류에 맞춰서 오류에 대한 예외처리 - 404 페이지, 500 오류 처리 등 - 을 할 수 있는 방법이 있다. 예외처리는 서블릿으로 예외 처리하는 방법과 스프링 부트를 통해 예외 처리를 하는 방법 2가지가 있다. 2. 웹 어플리케이션의 예외처리 웹 어플리케이션은 사용자 요청별로 별도의 쓰레드가 할당되고 서블릿 컨테이너 안에서 실행된다 이때 에플리케이션 안에서 예외가 발생하고 이를 try ~ catch 로 잡아서 처리하면 아무런 문제가 없다. 2) WAS 가 자체적으로 처리하도록 만들기 : 정확히는 Spring .. Java - Spring &&n SpringBoot 2022. 8. 19. 백준 - 20291 파일 정리 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 문제 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다. 바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. .. Java - 알고리즘 2022. 8. 19. 백준 - 10825 국영수 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소.. Java - 알고리즘 2022. 8. 18. 이전 1 ··· 3 4 5 6 7 8 9 ··· 17 다음