이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 1. 문제분석 - 처음에는 맨 처음 숫자를 눌러 가장 가까운 채널로 이동해 +, - 버튼에 따라 목표지점에 도달하는 최단 거리만 구하면 된다고 생각해서 BFS로 쉽게 풀 수 있을 것이라 생각했다. 하지만, 가장 가까운 채널로 이동하기 위해 가장 가까운 채널을 구하는 방법이 꽤나 복잡해져서 포기했다. 결국에는 이동 가능한 모든 채널로 이동해보고 해당 채널에서 목표지점까지 ..

0. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 문제분석 - 외판원 순회(TSP, Traveling Salesman Problem)라는 유명한 알고리즘에 관한 문제이다. - 그래프 내 각각의 노드의 방문 상태를 알아야 하고 또 이전의 방문 상태 및 현재 방문 노드를 기준으로 다음 방문하는 노드와 상태가 정해진다는 점에서 각 노드의 방문 상태를 나타내기 위한 bitmask와 dynamic pr..

0. 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제분석 - 트리라는 자료구조의 특성을 잘 알고 있다면 어렵지 않게 풀 수 있는 문제로, 트리가 가지고 있는 특성을 통해 리프노드를 찾기 위해서는 dfs를 사용해 문제를 풀어야 함을 알 수 있다. 트리는 cycle이 존재하지 않는 그래프이다. 하나의 트리는 하나의 루트만 존재한다. 루트가 여러 개라면 그것은 트리가 여러 개인 forest. 트리는 방향성이 존재하는(부모-자식)..

0. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제분석 - 기존의 상태(기존에 배낭에 넣은 다른 물건들로 인해 결정된 무게)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존 배낭에 새로운 물건을 넣는 것) 중, 그 최댓값을 찾는다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다. - dp[n][w] : n번째 물건까지 ..

일은 다니고 있지만...개발에 대한 의지를 다시 세우기 위해서... 블로그 다시 시작!!

1. IoC 와 Container inversion of control. 역제어. 전통적 개발 방식에서 개발자(클라이언트 코드)가 가지고 있던 객체에 대한 제어권(control)이, 프레임워크를 사용하게 되면서 컨테이터(container)에게 넘어가게 된 현상. 프레임워크 기반의 개발에서는, 컨테이너가 객체의 생성부터 생명주기까지 모두 관리한다. 2. DI dependency Injection. 의존성 주입. 한 클래스에서, 그 클래스와 연결된 다른 객체를 클래스 내부에서 생성하는 것이 아니라, 외부에서 주입해 주는 것. Spring과 같은 프레임워크에서는 보통 IoC 컨테이너에서 의존성 있는 객체를 만들어준 후, 이를 대상 클래스에 주입(Injection)해 줌으로써 의존성을 설정한다. DI는 sett..

django의 View에서는 Template에서 사용될 context 변수들과 함께 해당 웹 페이지를 띄우게 되고, template에서는 이러한 context들을 웹 페이지 내에 적절히 배치함으로써 웹 페이지를 작성한다. 일반적으로 context 변수들은 object 형태로 주어지게 되는데, 각각의 object는 각각의 Model(class)에 속하게 되므로, 해당 인스턴스에서 클래스 메소드들을 사용할 수 있다. 이를 위해 해주어야 할 작업에 대해 알아보고자 한다. 1. Python의 decorator 기능 def example_decorator(func): def decorated(): print("decorated!") func() return decorated class ExampleDecorato..

0. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 1. 문제분석 - 한 칸(노드)에서 시작해서 상하좌우로 인접한 칸을 연속해서 탐색한다는 점에서 DFS 또는 BFS 알고리즘을 사용..