전체 글 (31) 썸네일형 리스트형 [Algorithm] 다익스트라(Dijkstra) 1. 개요 - 단일 출발지 최단거리 알고리즘 - 가중 그래프에서 사용할 수 있다. - 구현에 우선 순위 큐가 사용되며, BFS와 거의 유사하다. 2. 설명 다익스트라 알고리즘의 핵심 개념은, 각 정점 간 최단 거리를 구하면, 결국 출발지를 기준으로 모든 정점에 대한 최단 거리를 구할 수 있다는 것이다. 이는 BFS과 같이 너비 탐색을 하며, 탐색 시간을 줄이기 위해 "우선 순위 큐"를 사용하게 된다. - 초기 각 정점의 최단 거리는 모두 무한 값으로 설정이 되어야 한다. - 우선 순위 큐에 들어가는 정보는 (시작점 - 현재 정점 까지의 거리, 현재 정점)과 같다. - 시작 정점은 우선 순위 큐에 넣을 때 거리 0으로 지정하여 넣는다. - 시작 정점의 최단 거리는 0 이다. 1) 동작 절차 다익스트라 알고.. [CS] Sync/Async, Blocking/Non Blocking 1. Sync/Asyncronous - 주로 Sync/Async는 일반적인 Operation 관점에서 얘기한다. - Call된 Function의 결과를 누가(Caller, Callee) 신경쓰느냐의 차이 1) Syncronous - Caller가 Function Call의 결과를 신경쓰는 방식 - Function Call을 한 후, 그에 대한 Return이 오기까지 Thread가 대기하는 방식 - ex) HTTP Request를 날린 후, Response가 오기까지 대기 2) Asyncronous - Callee가 Function Call의 결과를 신경쓰는 방식 - Function Call을 한 후, Call을 한 Function의 결과와 상관없이 완료를 기다리지 않고, 다음 동작을 수행하는 것 - Ca.. [Design Pattern] 00. 디자인 패턴이란? 1. "디자인 패턴"이란? "디자인 패턴"이라는 개념은 사실 소프트웨어에서 처음 생겨난 것이 아닙니다. 바로, 건축의 영역에서 등장한 개념이었죠. 엥? 건축이랑 소프트웨어랑 무슨 관계가 있길래 영향을 받은 거죠? 건축과 소프트웨어, 단순히 단어만 들으면 무슨 상관이 있는지 이해가 안 가실 수도 있습니다. 하지만, 곰곰이 생각해보면 건축과 소프트웨어 개발은 닮은 점이 무척 많습니다. 고객의 요구사항을 파악하고, 이를 토대로 설계하고, 설계한 대로 프로젝트를 진행한다. 아니, 거의 같다고 해도 무방할 것 같습니다. 하지만, 여기서 큰 차이점이라고 함은 소프트웨어는 언제든 기능을 수정, 추가할 수 있는 반면에 건물은 짓고 나면 건드리기가 참 힘든 정도겠네요. 디자인 패턴은 "어떠한 설계 문제 상황에는 ~패턴이.. [BOJ][DP] 1937. 욕심쟁이 판다 문제 -> https://www.acmicpc.net/problem/1937 처음에는 메모이제이션 생각을 안하다가 혹시 탐색으로 풀어야 하나 해서 해봤더니 바로 성공.. 너무 틀에 박힌 생각만을 해온것이 아닌가 걱정이다. 재귀도 꼭 고려해보자 이 놈아 ㅠㅠ ============================================ 메모이제이션, 즉 메모화 재귀도 DP에 포함되는 분야다. 메모이제이션이 무엇이냐 하면은,.. 간단히 말해서 재귀 호출로 인한 어떤 값을 저장하여 똑같은 값을 얻으려 재귀가 시도될 때 연산을 하지않고, 그 기억된 값을 사용하는 것 . 즉, 중복을 없앤다. ============================================ 어떻게 푸냐 하면은 1. 그 곳에 있는 .. [BOJ][DP] 2225. 합분해 문제 -> https://www.acmicpc.net/problem/2225 자릿수가 증가함에 따라 어떻게 경우의 수를 구해야 할지 단순하게 생각해야 한다. 뭐든지, 문제는 단순화 시킨 후 확장. 예를들어 N = 7, K = 3인 상황을 생각해보자. 단순하게 K자리에 N 부터 0 까지 차례대로 들어가고, N - K자리에 있는 값을 합으로 가지는 K-1 자리의 dp값을 가져오면 된다. 즉, 점화식은 아래와 같다. dp[i][j] += dp[i - 1][j - k]; (3중 for문으로 쓰여서 i, j, k가 쓰였다.) 그림을 보면 이해가 될지도 모른다. 아래는 위 과정을 표로 나타냈다. 소스(Github) [BOJ][DP] 1965. 상자넣기 문제 -> https://www.acmicpc.net/problem/1965 LCS인가 여튼 이와 비슷하게 접근하여 문제를 해결할 수 있다. 문제를 잘 읽어보아야 하는게, 입력된 상자의 데이터가 있을 때, 그 데이터의 위치를 가지고 판단을 해야한다. (처음에 그냥 막무가내로 풀었다가 실패) 또한, 저 상자들을 최대한 넣어서 어떤 무지막지하게 큰 상자에 넣는것이다. 즉, 조건을 만족하는 상자의 개수를 세는 것. 그러면 상자는 어떻게 세느냐? arr[i]보다 작은 값 arr[x] (x < i) 에 대해 dp값을 조사한다. 제일 큰 dp값을 기억해서 + 1. 1, 5, 2, 3, 7 의 예시로 해보자. 처음에는 모든 값이 0. 1의 왼쪽에는 작은 더 작은 수가 없으므로 그냥 +1. 이어서 "5"는 왼쪽에 더 .. [BOJ][DP] 1309. 동물원 문제 -> https://www.acmicpc.net/problem/1309 코드 자체는 짧지만 아이디어가 중요한 문제. 단순하게 문제를 생각해야 비로소 답이 보인다. 한 사자가 놓여져있을 때, 그 놓인 사자의 가로, 세로의 방향으로는 사자를 놓을 수가 없으므로 아래와 같이 대각선으로 놓든, 아무 사자도 놓지 않는 경우가 있다. N번째줄 칸에 칸이 놓일 수 있는 경우는 N-1번째줄 칸의 사자 배치의 상태에 따라 달라진다. 위 그림을 보면 알아 챌 수도 있지만, N-1번째줄에 어떤 한 칸이 있으면 그 밑에 사자를 배치할 수 있는 경우의 수는 각각 2개씩. N-1번째줄에 아무 사자가 없으면 그 밑에 배치할 수 있는 경우는 3개. 즉, 경우를 두 개로 나누어서 생각해야 한다는 것. 그렇다면 점화식은 dp[i].. [BOJ][DP] 1904. 01타일 문제 -> https://www.acmicpc.net/problem/1904 N이 홀수일 때, N이 짝수일 때 어떤 경우가 나올지 잘 생각해보면 금방 답이 도출이 된다.. 아래 그림을 보자. 먼저 N=0일 때, 타일을 배치하지 않는다 라는 선택도 경우의 하나에 속하므로 1. N = 1일 때, 1밖에 놓을 수 없으므로 경우는 1. N = 2일 때, 00, 11 두 개밖에 놓을 수 없으므로 2. 이제부터가 중요하다 . N = 3일 때, 100, 001, 111로 총 세가지이다. N이 홀 수라면,낱개로서 배치할 수 있는 타일인 "1"한개가 들어가는 경우가 생긴다. 그래서 경우의 수에 영향을 주게된다. 여기서 가만보면 어떤 점화식을 도출해낼 수가 있다. dp[i] = dp[i - 2] * 2 + dp[i-3] .. 이전 1 2 3 4 다음
