본문 바로가기

전체 글

 (336)
방향 그래프에서 사이클 찾기 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 안에 있는 파일만 가져올 수 있도록 세팅되어있음...
백준 2651번 - 자동자경주대회 (C++) https://www.acmicpc.net/problem/2651 2651번: 자동차경주대회 전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비소들은 www.acmicpc.net 어떤 코테에서 봤던 문제인 것 같다. 역시나 코테의 문제들은 모두 백준에 존재한다. 많이 풀어보고 완벽하게 익히고 있어야한다. 먼저 이 문제를 봤을 때 떠올랐던 풀이는 다익스트라, 배낭문제, 다이나믹 프로그래밍이었다. dp[N][2] 를 선언하고 충전을 하였을 때와 안하였을 때를 넣으려고 했는데 생각보다 잘 안됐다. 이 문제를 해결하기 위해 필요한 건 글쎄,, 이런 문제를 풀어본 경험 혹은 아주 뛰어난 ..
Docker - Image pull, run 명령어 Computer Docker App Store docker hub Program image Process Container 일반 컴퓨터와 도커는 위의 이름들이 대응된다. 도커에게 프로그램은 이미지와 같고, 도커에서 동작하는 것들은 컨테이너라 한다. PULL 앱스토어에서 다운로드 받듯이 도커 허브에서 프로그램이 설치된 이미지를 다운받을 수 있다. 이것을 Pull 이라하며 https://hub.docker.com/search?q= 이 사이트에서 자신이 원하는 도커 이미지를 찾아 다운받을 수 있다. 난 테스트로 httpd를 다운받아 보았다. 여기서 도커 오피셜 이미지 마크는 이 이미지가 매우 안전하다는 것을 보여준다. 그리고 오른쪽의 명령어를 입력하면 터미널에서 패키지를 다운받는 것 처럼 손쉽게 이미지를 다운..
백준 1623번 - 신년 파티 (C++) https://www.acmicpc.net/problem/1623 부모가 참가하지 않으므로 자식이 참가해도되고 안해도 된다. dp[2][1] => 내가 무조건 참가한다. 자식은 참가하지 못한다. 이것이 이루어진다. 이것을 코드로 바꿔보면 void dfs(int n) { dp[n][0] = 0; dp[n][1] = score[n]; for (int i = 0; i < node[n].size(); i++) { int next_n = node[n][i]; dfs(next_n); dp[n][1] = dp[next_n][0] + dp[n][1]; dp[n][0] = max(dp[next_n][0], dp[next_n][1]); } } 여기서 끝났으면 이 문제는 골드1 난이도가 아닐 것이다. 이 문제는 더 나아가서..

티스토리툴바