전체 글207

• 

  백준 - 2981 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 방법 어떤 문제에 이은 무식하면 용감하다 시리즈 2번째 최근에 유클리드 호제법을 공부하고 관련된 문제를 풀어서 이번에도 쉬울 줄 알고 도전했는데...세상에 이렇게 어려운 문제일 줄은 몰랐다. 물론 풀고 나니까 내가 몰랐었던 혹은 까먹었던 부분들 - 정수론, 나머지 정리 - 을 잘 버무리고 활용하면 쉽게 풀릴만도 했지만 나는 문과였고ㅠㅠ 유클리드 호제법도 정수론도 이제야 보게 되었다ㅠㅠ 여튼 그래도 저런거 다.. Java - 알고리즘 2022. 9. 5.

• 

  백준 - 4485 녹색 옷 입은 애가 젤다지? 풀이 방법 오랜만에 도전한 골드 문제!! 처음에 생각없이 BFS 로 코드를 짰는데 메모리 초과가 발생해서 방향을 다시 잡고 코드를 치기 시작했다. 이 문제의 핵심 포인트는 녹색옷을 입을 애가 젤다라는 점!! 이 아니고ㅋㅋㅋㅋ 2차원 배열로 입력받는다고 하더라도 결국 n-1, n-1 좌표에 도착하는 최소값을 구하는 문제라는 점이다. BFS 나 DFS 로 푸는것이 아니라 다익스트라 알고리즘을 사용해야한다. 다만 우리는 그래프 형식이 아니고 배열로 입력받기 때문에 어떻게 좌표(노드)에서 좌표(노드) 로 넘어갈 수 있는지 고민해야한다. 나는 이 부분을 DFS, BFS 에서 사용하던 dx, dy 배열을 사용해서 풀이를 하였다. 즉, dx, dy 를 통해 계산된 nx, ny 좌표가 배열의 범위 안에 존재하면 이전 .. Java - 알고리즘 2022. 9. 2.

• 

  Spring Boot Web Chatting : 스프링 부트로 실시간 채팅 만들기(2) chatDTO, DAO, Socket.js 코드 알아보기 10.29 추가 : 일반(문자) 채팅만 구현하는 코드는 git 의 master 브렌치를 참고해주시기 바랍니다. master-Webrtc-jpa 는 화상 채팅과 jpa 를 이용한 DB 연결을 포함하는 브렌치입니다. 1. 기본 개념 설명 STOMP - STOMP 는 Simple Text Oriented Messaging Protocol 의 약자로 메시지 전송을 위한 프로토콜이다. 기본적인 Websocket 과 가장 크게 다른 점은 기존의 Websocket 만을 사용한 통신은 발신자와 수신자를 Spring 단에서 직접 관리를 해야만 했다. 즉 WebSocketHandler 를 만들어서 WebSocket 통신을 하는 사용자들을 Map 등으로 저장하고 이를 직접 관리하며 클라이언트에서 들어오는 메시지를 다른 사용.. 토이 프로젝트/Spring&Java 갖고놀기 2022. 9. 1.

• 

  백준 1193 : 분수찾기 풀이 방법 백준 브론즈의 탈을 쓴 실버 문제...매번 느끼는 것이지만 백준에서 '수학' 이 붙은 애들은 모두 실버 이상의 난이도라고 생각이된다ㅠㅠ 특히나 규칙을 못 찾으면 차라리 BFS, DFS 문제 푸는게 더 쉽다고 느껴질 정도이다. 이 문제가 특히 그랬는데 뭔가 보일듯 말듯 하면서 시간이 정말 오래걸려서 풀었다. 사실 수학 관련 문제가 그렇듯, 이 문제도 점화식을 세우면 혹은 그에 준하는 규칙을 찾으면 해결의 실마리가 보이는 편이다. 짝수 층과 홀수 층에 관한 규칙, n번째 층에 총 몇개의 분수가 오는지 규칙을 찾아서 점화식을 세워야 한다. 나는 문제의 지그재그 순 이라는 것을 하나의 층으로 생각하였다. 즉 1층에는 1/1, 2층에는 1/2, 2/1 ---- 이런 식이다. 여기에 각 층에 몇개의 분수.. Java - 알고리즘 2022. 8. 30.

• 

  백준 - 2839 설탕배달 풀이 방법 스터디에서 곧 풀게될 문제라서 미리 풀어보았던 문제였다. 그런데 그리디 알고리즘이라는 것을 알고 한번 좌절ㅠㅠ 하였다가 몇번이나 틀리고 코드를 완성시켰다. 문제를 풀고나서 보니까 이게 나처럼 무식하게 풀 필요가 없이...규칙을 찾아서 풀면 풀리는 문제라는 것을 알고 한번 더 좌절했다ㅠㅠ 나는 PriorityQueue 와 BFS 를 사용해서 풀었다. queue 에 넣는 값에는 sum 과 cnt 를 사용하였다. cnt 는 n-5 또는 n-3 했을 때 각각 cnt+1 이 되도록 했고, sum 은 n-5 또는 n-3 된 값을 넣어두었다(사실 변수명이 sum 말고 minus 로 설정해야될 것이다). 이후 sum 과 cnt 를 queue에 넣어서 보다 작은 sum 값이 먼저 나오도록 만든다. 이를 통해서.. Java - 알고리즘 2022. 8. 29.

• 

  Spring Boot Web Chatting : 스프링 부트로 실시간 채팅 만들기(1) stomp, socketjs, websocket 각 브렌치 및 포스팅 별 내용- 일반 채팅 : master => 2 ~더보기2022.09.01 - [토이 프로젝트/Spring&Java 갖고놀기] - Spring Boot Web Chatting : 스프링 부트로 실시간 채팅 만들기(2) chatDTO, DAO, Socket.js 코드 알아보기 - 시그널링 서버를 구현한 화상채팅 & 화면 공유(P2P) : master-webrtc-jpa => 6~7 번 포스팅더보기2022.10.29 - [토이 프로젝트/Spring&Java 갖고놀기] - Spring Boot Web Chatting : 스프링 부트로 실시간 채팅 만들기 (6) WebRTC 를 이용한 실시간 화상 채팅 구현하기(feat. https 인증서 적용) - Kurento 미디어 서버를 활용한 화상채.. 토이 프로젝트/Spring&Java 갖고놀기 2022. 8. 29.

• 

  백준 - 1238 파티 풀이 방법 다익스트라 알고리즘을 공부했기에...도전했던 문제ㅠㅠ 근데 '공부한 것' 과 공부한 것을 문제에 적용하는 것은 다르더라는 것을 깨달았다. 수학 공부하면서 공식을 아는 것과 적용하는게 다시 한번 느꼈달까ㅠㅠ 이 문제의 포인트는 각 마을에서 X 를 방문했다가 다시 X에서 각 마을로 돌아오는 것! 을 모두 계산해야한다는 점이다. 단순히 가는 것만 계산해서도 안되고, 집으로 오는 것만 계산해서도 안된다. 때문에 이 문제는 다익스트라 알고리즘을 총 2번 사용해서 답을 구하게 된다. 정확히는 X 에서 각 마을로 가는 최소 방문 비용을 구한 후 bakHome 에 저장하고, 각 마을에서 X 로 가는 최소 방문 비용을 구해서 goX 에 저장한다. 이때 X -> 각 마을 까지는 다익스트라를 이용하면 되는데, 각.. 카테고리 없음 2022. 8. 28.

• 

  다익스트라 알고리즘 데이크르스라 알고리즘 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.