기록장

문제https://www.acmicpc.net/problem/18405 3055번 탈출(https://www.acmicpc.net/problem/3055) 문제와 비슷한 문제가 시험에 나왔다.탈출 문제를 완전히 이해하기 전에 시험을 쳐서 그런지 이 문제 또한 못 풀었다.오늘 풀이하고 집 가야지..풀이문제에서 고려할 점은 여러 개의 바이러스가1초 마다 번호가 작은 순서대로 확산된다는 것이다.k초에 수행되는 것 :'k-1초에 큐에 넣었던 좌표'의 모든 인접 좌표에 대해 bfs 수행단, 바이러스 크기가 작은 좌표부터 차례로 수행해야 함바이러스 크기가 작은 것부터 확산하는 아이디어 :우선순위 큐를 사용해서 좌표를 바이러스 크기 순서대로 꺼내기 :-> 잘못된 방식이다. 바이러스 1을 bfs로 퍼뜨리면서 바이러스 ..

문제https://www.acmicpc.net/problem/14888n개의 숫자와 n-1개의 연산자가 주어졌을 때숫자의 순서를 유지한 채 연산자의 순서만 바꿔서 계산한 결과의 최댓값, 최솟값을 찾는 문제이다.풀이재귀, 백트래킹으로 풀면 되겠다고 생각했는데 뭔가 연산자를 저장하고 있는 배열과 숫자를 저장하고 있는 배열이 달라서 설계하기 헷갈렸다.  n-1개의 연산자를 모든 순서로 선택하는 방법은 해당 연산자를 선택하거나 선택하지 않거나 둘 중 하나이므로특정 연산자를 선택하고 재귀로 넘긴 후 다시 선택하지 않는 상태로 백트래킹시키고 다음 연산자를 선택하게 만들면 된다.4개의 연산자 중 i번째 연산자를 선택했으면 i번째 연산자의 숫자를 1 감소시키고 백트래킹할 때는 다시 1 증가시킨다.선택한 연산자를 사용하..

문제https://www.acmicpc.net/problem/21606N개의 노드와 N-1개의 간선으로 이루어진 그래프가 있다.각 노드는 실내(1) 또는 실외(0)에 해당한다.출발 노드, 도착 노드가 실내이고 그 사이에 존재하는 노드들이 모두 실외인 경로가 몇 개인지 구하는 문제이다.풀이처음 아이디어처음에는 간선의 양쪽이 실내/실외로 다른 경우 간선 가중치를 1로 두고간선의 양쪽이 모두 실내인 경우 간선 가중치를 0으로 둬서모든 경로를 찾은 후 경로의 가중치 합이 0 또는 2가 되면 되지 않나...라는 아이디어를 떠올렸다. 그리고 실내를 시작점으로 두고 bfs 탐색 하는 방식으로 찾으면 될 것 같았다. 그러나 N의 최대값이 너무 크기 때문에 (2모든 경로를 3초 안에 브루트포스로 탐색할 수 없다.코드im..

문제https://www.acmicpc.net/problem/2665n*n 바둑판에서 검은 방(벽면)을 뚫어 시작점(0*0)부터 끝점(n-1, n-1)까지 갈 때, 뚫는 벽의 최소 개수를 구하는 문제이다.풀이0-1 BFS 알고리즘이 문제는 0-1 BFS 알고리즘을 사용하여 풀 수 있는 문제다. 간선의 가중치가 모두 다를 때 다익스트라로 최단 거리를 찾을 수 있었다면,간선의 가중치가 다르긴 한데 0과 1밖에 없는 경우 다익스트라보다 더 효율적인 방법으로 0-1 BFS를 쓸 수 있다. 이 블로그에 내용이 잘 정리되어있다.https://krrong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-0-1-BFS [알고리즘] 0-1 BFS📌 Intro 0-1 B..

보호되어 있는 글입니다.

오늘 시험에 다익스트라가 나온대서 정리하고 넘어가려고 한다.예전에 최소비용 구하기 풀면서 정리해둔 글이 있어서 풀이를 가져왔다.  https://nkdev.tistory.com/74 [백준/Java] 1916번 : 최소비용 구하기🌵 문제 분석https://www.acmicpc.net/problem/1916출발 도시 번호, 도착 도시 번호가 A, B로 주어질 때 A에서 B까지 가는 데 드는 최소 비용을 출력하여라.입력 :N(도시의 개수)M(버스의 개수)a(출발 도시 번nkdev.tistory.com 💡가중치가 있는 그래프의 최단 거리를 구할 때는 다익스트라를 사용  최단 거리를 구할 거면 BFS를 쓰면 되는데 왜 다익스트라를 또 배우는가? 일반적인 BFS는 가중치를 고려하지 않는다. 간선 가중치를 고려..

문제https://www.acmicpc.net/problem/1707완전탐색 활용 문제 너무 어려워..! 근데 구현 아이디어를 알고 나니까 코드 짜는 건 좀 재밌었다풀이🥹 처음 아이디어노드를 두 그룹으로 나눌 때, 같은 그룹 끼리는 간선이 없어야 함 이 개념만 가지고 노드를 두 그룹으로 어떻게 나눠야 할까 생각했다. 1. 간선이 있으면 다른 그룹으로 나누는 작업을 반복 -> 끝까지 진행 후 총 2그룹이면 YES  -> 고민: 같은 그룹인지 어떻게 구분함..?   -> 그룹이 뭔지 저장하는 group[v+1]을 만들고 노드 1부터 순차 탐색, 인접하지 않은 노드를 발견하면 다 같은 그룹으로 표시하기  -> 근데 이 방법은 시간 복잡도가 O(V^2)이기 때문에 틀린 풀이 (제한 시간 2초, V2. 단, 어..

문제https://www.acmicpc.net/problem/2178풀이이차원 배열 matrix에 0과 1을 저장하고 (0,0)부터 bfs 탐색한다.각 좌표를 노드 객체로 표현한다. 노드 객체는 행, 열, (0,0)부터 현재 좌표까지 도달하는 데 필요한 거리값을 가지고 있다.큐에서 좌표 하나를 꺼내서 다시 그 좌표의 인접 좌표들을 큐에 다시 넣는데, 이 작업을 할 때 노드의 w값을 현재 좌표의 w값+1로 증가시켜준다.큐에서 꺼낸 값이 (n-1,m-1)노드이면 그 w값을 출력한다.코드import java.io.*;import java.util.*;public class Main { static int n, m; static boolean[][] visited; static int[][] m..

@TagAPI 그룹 지정. Tag에 설정된 name이 같은 것끼리 하나의 API 그룹으로 묶는다. Controller 또는 Controller의 메서드 영역에 설정한다. REST API의 엔드포인트는 컨트롤러에 있으므로, 컨트롤러 클래스 위에 @Tag어노테이션을 붙여서 API 그룹을 설정할 수 있다. Target - ANNOTATION_TYPE, METHOD, TYPEname : 태그 이름description : 태그 설명@Tag(name="User", description="사용자 API")@RestController@RequestMapping("/users")public class UserApiController { //Post, Get, Patch, ... 에 해당하는 메서드들} @Operat..

Swagger을 설치하다가 내 애플리케이션이 single-page application(SPA)이면 swagger-ui를 쓰고, 그게 아니면 swagger-ui-dist를 쓰라는 말이 있길래, SPA를 찾아보다가 서블릿까지 와버렸다!MPA (Multi Page Application)SPA가 한 개의 페이지로 구성된 애플리케이션이라면 MPA는 그 반대! 여러 페이지로 구성된 애플리케이션이다. 그러니까 그게 무슨 말이나면. 클라이언트가 페이지를 접속할 때마다 HTTP Request로 서버에게 페이지 접속 요청을 보낸다는 사실은 이미 다 알 것이다. 예전에는 클라이언트의 요청이 있을 때마다 서버에서 페이지를 매번 새로 보내줬었다. 예를 들어 동적 요청이 있다면 서버는 요청에 맞게 데이터베이스에서 데이터를 꺼..