1. 문제 1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2. 풀이 이 문제에서 핵심은 "어떤 칸을 최초 방문할 때 해당 칸에서 목적지까지 도달할 수 있는 경우의 수에 대한 정보를 기록해 놓고, 다음 방문 시 기록된 값을 참조해서 반복된 연산을 피하는 것이다" dp[y][x]를 (x,y)에서 (n-1,m-1)까지 조건에 맞는, 도달하는 경우의 수라고 정의하자. m,n = map(int,stdin.readline().split()) maps = [list(map(in..
1. 다차원 배열(multidimensional array) 2차원 이상의 배열 배열 요소로 또 다른 배열을 가지는 배열 2차원 배열은 배열 요소로 1차원 배열의 참조를 가진다 3차원 배열은 배열 요소로 2차원 배열의 참조를 가진다 3*3 배열이 stack에 전체 주소를 가지고, 그 주소를 따라가면... 3개 공간의 배열이 있는데.. 각 공간에는 역시 어떤 1차원 배열의 주소를 가지며 그 주소를 따라가면.. 실제 값들을 가지는 1차원 배열이 있는... 2. 2차원 배열 선언 1) 타입[][] 이름: int[][] iArr 이 방법을 주로 사용함 2) 타입 이름[][]: int iArr[][] 3) 타입[] 이름[]: int[] iArr[] 3. 2차원 배열 생성 1) 배열의 이름 = new 타입[1차원 ..
1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..
1. 문제 N*N 배열에 숫자가 들어있는데, 각 행에서 하나씩 숫자를 골라 그들의 합이 최소가 되도록 만들고 싶다. 그런데 세로로 같은 줄에 2개 이상의 숫자를 고를 수는 없다. 어떻게하면 합이 최소가 되도록 숫자를 고를 수 있을까? 2. 나의 풀이 어떻게 풀어야할지 도저히 모르겠더라 그래서 천천히 pseudo code를 생각해보았다 2-1)한 행에 0부터 n-1까지에서 숫자를 하나 고른다 2-2)고른 숫자를 더해준다 2-3)행수에 1을 더해서 다음 행으로 이동한다 2-4)이전 행에 고른 열이 아닌 다른 열에서 숫자 하나를 고른다 2-5)고른 숫자를 재귀적으로 반복함 이런식으로 생각해보고 하나하나 천천히 짜보니까 길이 좀 보이긴 하더라 def pick_num(x,y,sum_value): sum_value..
1. 그래프의 기본 구조 그래프는 노드(node)와 간선(edge)으로 표현되고 이때 노드를 정점(vertex)이라고도 말한다 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'(adjacent)라고 말한다 노드를 도시, 간선을 도로라고 생각해보자. A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서 A와 B를 연결하는 도로(간선)를 거친다고 이해하면 쉬울 것이다 2. 프로그래밍에서 그래프를 표현하는 방식 인접행렬(adjacency matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접리스트(adjacency list) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접행렬 방식은 2차원 배열에 각 ..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr N*M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
