열심히해보겠씁니다

현상금 사냥꾼 김정은 문제와 유사하다. DP 배열을 이용하고, dp[i][j] 는 첫 번째 벽장이 i 번 자리로 이동하고 두 번째 벽장이 j 번 자리로 이동했을 때, 남은 것을 수행하는는데 필요한 최소 거리를 뜻한다. 즉 dp[0][0]이면 처음 자리에서 모든 쿼리를 다 해결했을 때 최소 거리가 나온다. 점화식은 다음처럼 유도했다. dp[0][0] = min( dp[1][0] + dist(0->1) , dp[0][1] + dist(0->1) ) ... next = max(i, j) + 1; dp[i][j] = min(dp[next][j] + dist(i->next) , dp[i][next] + dist(j->next) ); 초기값은 i, j 가 마지막 질문을 받았을 때, 그 자리로 이동하는 거리만 ret..

x 좌표로 정렬된 행성 리스트가 주어지며, 행성을 이동할 때, 다음 행성은 항상 지금 행성보다 x 좌표가 커야 한다. 또한 전체 이동거리가 최소가 되도록 해야 하므로 Greedy 방식은 특정 케이스에만 맞을 수 있으므로 DP를 이용한다. 중요한 것은 x,y 좌표 사이에 맨해튼 거리를 구해야하므로 square root( delta x ^2 + delta y ^2 ) 을 구해야하고, 소수점 2자리까지 맞아야하므로 double 형이나 float형을 써야 한다. dp 배열은 3가지를 중심으로 생각한다. 1. dp배열 정의 2. 초기값 3. 점화식 dp 배열을 정의하는 것이 가장 중요하며, 생각하기 힘들기 때문에 DP 문제의 가장 어려운 부분인 것 같다. 하지만 정의되기만 한다면 2,3 은 (거의) 자동으로 정해..

최단 경로에 쓰인 경로를 절대 사용하지 않고 그 다음 최단 경로를 찾는 문제이다. 아이디어는 아주 간단하다. 1. 최단 경로를 구한다. 2. 백트래킹으로 경로를 제거해준다. 3. 다시 최단 경로를 구한다. 아이디어가 간단하고 함정이 없기 때문에 구현에 무게를 두면 된다. fastest 배열에는 cur_node 로 오기전 어떤 node에 있었는지를 기록한다. 만약 같은 거리에서 온 node가 있다면 추가만 시켜준다.(그 다음 노트부터는 경로가 동일하므로 queue에 넣지 않는다.) 만약 지금 저장된 거리보다 짧은 거리로 왔다면, 지금까지 저장된 경로를 지워주고 새로 저장한다. 경로 제거는 dfs (del_fastest(int D) 함수), bfs (del_fastest() 함수) 둘 다 가능하다. 해당하는..

기민이의 고민을 만들어준 짜증나는 문제 원탑이다. 시작하자마자 틀린 것은 type 선언 문제가 컸고, 17% 혹은 18%에서 틀린 것은 사이클이 여러개 있다는 것을 간과해서 그럴 수 있다. 만약 벨만포드 알고리즘을 사용할 것이라면 1. 사이클 유무 확인 2. 사이클마다 목표지점에 닿는지 확인 두 가지를 필수로 사용해야 한다. 나는 도로를 지나가는데 사용한 비용을 음수로 넣고 city 에서 얻을 수 있는 돈을 city 배열에 저장해서 단순히 + 연산으로만 구현할 수 있게 만들었고, 초반에 distance 구하는 건 줄 알고 dist 배열로 선언한 것을 그냥 총 벌어들인 돈 배열로 생각하기로 했다. 예제에서는 다음과 같은 사실을 발견해야 한다. 1. 자기 자신으로 가는 간선이 존재한다. (dist[S] = ..

값이 빈번하게 수정될 때, 구간의 합을 효율적으로 구하라는 문제이다. 인덱스 트리나 세그먼트 트리 혹은 펜윅 트리를 강요하는 문제가 아닐까 싶다. Bottom-up 방식으로 구성하는 인덱스 트리가 가장 쉬워서 인덱스 트리로 구현했다. 세그먼트 트리도 가능한데 물론, 구현하기가 쉽지 않아서.. (재귀) ㅠㅠ 인덱스 트리는 1차원 배열에다가 배정하며, (부모 인덱스 * 2 , 부모 인덱스 * 2 + 1) 이 자식의 인덱스이다. 물론 완전 이진 트리로 만든다. 고민할 점은, tree 배열을 선언할 때 할당할 메모리를 잘 생각해야 한다는 점이다. 데이터 수가 N 이면 2^n 으로 배정하여 부모-자식 사이의 관계가 유지되도록 만들어줘야 한다. 여기서 루트 노드의 인덱스는 1이고, 배열의 크기는 2^n 으로 보면 ..

임의의 트리를 주고 LCA 를 이용하여 비용과 지나가는 노드를 추출하는 문제이다. 접근 방식 1. 주어진 N-1 개의 입력을 트리로 구성한다.(이진트리조차 아닐 수 있음) 2. LCA 를 위한 parent 배열을 구성한다. 3. Cost 를 빠르게 계산하기 위해 cost 배열을 미리 계산해 놓는다. 이용할 때, a에서 parent[a] 까지 간선을 이동하는데 쓴 비용 = cost[a] - cost[ parent[a] ] 이다.(makeTree에서확인) 4. start node 가 첫 번째이고, k 번째 node 를 구하기 위해 LCA 를 또 이용한다.(query_node 확인) LCA 를 presum 으로 이용하는 방식에 대해 공부한 것 같다. 4번 정도 틀린 것 같은데 오류의 원인은 다음과 같았다. 1..

파이썬 변수와 Namespace 메모리 Namespace 에 사용하는 name(변수명, 함수명, class명, method명, module 명 등) 들이 저장되며, reference 에 name의 주소가 저장된다. name binding name의 reference 영역에 객체의 id를 저장하여 객체를 연결시키는 과정 assignment( =), augmented assignment(*=, +=, -=,...), class method function 정의, import 할 때 발생 del name을 통해 지울 수 있다. id(name) 을 통해 실제 메모리 값 접근 Identifier 변수명 등 식별자 interpreter 는 identifier를 발견하면 namespace에서 탐색한다 읽기 - loc..

기초적인 파이썬과 자바의 문법을 익히기 위해 알고리즘 문제를 풀어보기로 했다. 어려운건 힘들기 때문에(c로 해도 힘든데...) 쉬운 실버부터 차근차근 풀어보도록 하자. 위 문제는 알파벳이 연속적으로 오느냐(1개만 있어도 ok) 혹은 알파벳 사이에 다른 종류의 알파벳이 껴있느냐를 묻는 문제이다. 즉, aaabbbcdd 같은 형태는 가능하고, aaabbbaaa 같은 형태는 불가능하다. 주어진 입력에서 그룹 단어의 개수를 체크하여 출력하면 된다. 자바와 파이썬 코드의 풀이 방식은 동일하다. 1. 입력받은 단어에서 a~z까지 하나씩 확인한다. 2. a를 확인한다면 index를 찾아서 연속되는지 (next-prev==1)인지를 확인하고 연속하지 않고 떨어져있다면 세지 않는다. 파이썬 코드 def group(s:s..

백준에 엄청 자주 등장하는 증가하는 부분 수열 문제이다. N이 1백만 scale 을 가지므로 최대 NlogN 안에 풀어야한다. 그러므로 수열 순회는 N번 안에 종료해야하고 나머지 연산이 log N 안에 끝내야하므로 Binary Search 를 적용하여 풀 수 있을 것으로 기대한다. 1. 문제 접근 - 가장 긴 부분 수열을 만들기 위해 수열을 탐색하며 부분 수열을 지속적으로 갱신한다. 2. 문제 해결 - 가장 긴 수열의 정보를 지속적으로 갱신하며 진행하여 수열을 1번만 순회할 수 있도록 한다. - 가장 긴 수열의 정보를 수정할 때, 수정할 위치를 찾는 것은 Binary Search를 이용하여 logN안에 수행한다. 가장 긴 증가하는 부분 수열 2 문제는 부분 수열의 값이 어떤 것인지 중요하지 않고, 총 갯..

예외처리(Exception Handling) 런타임에서 발생하는 에러를 다루기 위해서, C에서는 조건문을 이용하여 제한을 주었다. C++에서는 드디어 일반적인 조건문과 예외처리문을 구별하여 쓸 수 있게 되었다. try, catch, throw 예외가 발생할 수도 있는 문장과 그 덩어리를 try{} 블럭 안에 작성하고, 예상되는 에러를 처리하기 위해 catch(에러){}의 블럭 안에 예외 처리 코드를 작성한다. 따라서 try와 catch 는 항상 붙여서 작성해야 하므로 가운데 다른 문장이 들어오는 등 따로 작성할 수는 없다. try 문 안에는 예외객체를 전달해주는 throw 키워드가 존재한다. try 안에서 오류가 발생한다면 throw에 의해서 예외가 던져지고 try는 종료되고 catch 블록에서 예외를 ..