본문 바로가기

전체 글

 (403)
백준 16928번 - 뱀과 사다리 게임(C++) https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 다익스트라, 그래프 등 많은 것을 고민했지만 그냥 bfs 풀이가 가장 쉬운 풀이이다. #include #include #include using namespace std; map jump; bool visited[101] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL..
백준 1967번 - 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가장 먼저 생각난 풀이는 플로이드-워셜 알고리즘이었다. 그러나 플로이드 워셜의 시간복잡도는 O(N^3)이기 때문에 불가능했다. 그래서 트리에서의 DP를 생각해보았지만 딱히 해결법이 생각나지 않았다. 가장 쉬운 방법은 모든 지점에서 dfs를 수행하는 것이다. 노드의 개수가 1만이기 때문에 O( (V + E )^2 ) = 2만 제곱 = 4천만으로, 해결이 가능하지만 이게 정해라면 ..
백준 9466번 - 텀 프로젝트 (C++) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 위 문제를 보고 그래프 문제라는 것을 깨닫는 것이 첫번째 단계다. 여기서 1~7을 노드라고 생각하자. 그리고 아래 숫자들은 노드가 가리키는 또다른 노드라고 생각하면, 위 표는 아래같은 그래프로 나타낼 수 있다. 이제 이 문제가 파악이 될 것이다. 이 문제는 그래프로 나타낸 뒤 사이클을 파악하는 것이 핵심이다. 이제 이것을 어떻게 파악해야할까. 가장 쉬운 것은 모든 노드에서 dfs를 돌리면서 자기 자신으..
방향 그래프에서 사이클 찾기 Cycle? 사이클은 모두 알다시피 그래프에서 시작과 끝이 같은 형태를 말한다. 그래프에서 사이클은 언제나 성가신 존재인데, 무한루프를 발생 시킬 수도 있고, 쓸 대 없이 몇 번 돌다가 나와서 성능이 안 좋아질 수도 있다. 이것은 현업에서도 골치이고 PS에도 자주 등장하는 문제이다. 이것을 어떻게 판별할 수 있을까 방향 그래프에서 싸이클 판별 방향 그래프에서 사이클을 판별할 수 있는 방법은 가장 익숙한 DFS 이다. dfs는 방향이 계속 같기 때문에 다음 노드를 판별하기 용이하기 때문이다. 그리고 방향 그래프에서의 사이클이란 Back Edge가 존재하는 것과 같다. 이제 문제는 Back Edge를 판별하는 것으로 바뀌게 된다. void dfs(int NowNode) { visited[NowNode] = ..
벨만-포드 알고리즘 (Bellman-Ford Algorithm) Bellman-Ford Algorithm 벨만 포드 알고리즘은 음수 간선이 존재하고 그것이 사이클을 만들어낸다고 해도 최단거리를 만들 수 있는 알고리즘이다. 다익스트라 알고리즘은 익히 알다시피, 음수 간선이 존재하면 사용할 수 없는 것을 알고 있을 것이다. 다익스트라와 벨만 포드의 차이 다익스트라와 벨만 포드는 둘 다 1차원 dist 배열을 갱신하며 최소치를 기록하는 스킬은 똑같다. 그러나, 다익스트라는 모든 노드를 살펴보지 않는다. 가능한 경우에만 다음 노드로 이동하기 때문이다. 그러나 이 효율적인 방식 때문에 음수 간선이 있으면 다익스트라를 사용할 수 없다. 그러나 벨만 포드는 효율적이지 않게도 모든 노드를 살펴본다. 그래서 시간복잡도가 N*M이다. 그리고 음수간선이 있어도 사용이 가능하다. 바로 아..
프로그래머스 - 단어 변환 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs/bfs 문제라는 것을 확인했기 때문에 쉽게 풀 수 있었다. 난 bfs방식을 택했다. 중요한 것은 하나의 단어에 도달하면 다른 단어들은 이 단어에 도달할 수 있어도 할 필요가 없음을 인지해야한다. 만약 지금 이 단어에 도달했는데, 다음으로 이 단어에 도달한다는 것은 결국 최단거리가 아니라는 의미이기 때문이다. 그러므로 방문표시를 하고 bfs 탐색을 하면 문제는 풀린다. 이 문제가 레벨3인 이..
백준 1520번 - 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 길찾기 문제 + 경로 개수 찾기 문제이다. 만약 이 문제가 내리막길을 찾으면서 가장 빨리 도착해야겠다면 다익스트라 혹은 BFS문제였을 것이다. 그러나 이 문제는 경로의 개수 를 찾는 문제이다. 답만 찾으려면 dfs로 조건만 돌리면 되지만, 이렇게하면 4^500*500 으로 당연히 시간초과가 난다. 그러므로 메모이제이션을 통해 지금이 노드를 이용하면 마지막 노드까지 갈 수 있는지 없는지를 저장해놔..
Spring Boot 외부 파일 경로 설정 Spring Boot 외부 파일 경로 @Configuration public class WebMvcConfig implements WebMvcConfigurer { @Override public void addResourceHandlers(ResourceHandlerRegistry registry){ String resourcePath = "file:///TistoryImages/"; String connectPath = "/image/{subfolder}/**"; registry.addResourceHandler(connectPath) .addResourceLocations(resourcePath); } } Spring Boot는 내부적으로 static 안에 있는 파일만 가져올 수 있도록 세팅되어있음...

티스토리툴바