scieneer

Window 환경에서 Rust 설치하기

Window 환경에서 Rust 설치하기

Window 환경에서 Rust 설치하기

Rust 재단 설치 홈페이지로 이동하여 Rustup 설치하기 https://www.rust-lang.org/tools/install Install Rust A language empowering everyone to build reliable and efficient software. www.rust-lang.org 위 홈페이지 접속하여 64-bit를 설치하면 된다. Rust 가 올바르게 설치되었는지 확인하려면 Window CMD를 열고 다음의 커맨드 실행 rustc --version Rust 프로그램을 작성하기 위한 개발 환경 세팅 터미널 CLI 환경 IDE를 사용한다면 Jetbrain의 IntelliJ Rust / VScode +) VScode 에서 아직 Rust 가 완벽히 지원되는게 아니라서 Int..

플로이드 와샬 (Floyd - Warshall)

플로이드 와샬 (Floyd - Warshall)

플로이드 와샬 (Floyd - Warshall)

플로이드 와샬 알고리즘은 최단경로 알고리즘중 하나이다. 정점 V개가 있고 거리가 다 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다. 3중 for문으로 구성되어있으므로 O(V^3) 에 동작한다. 동적계획법 어김없이 등장하는 동적계획법. 동적 계획법으로 문제를 풀기 위해서는 재귀 관계식을 찾고 상향식으로 표현해야한다. D : 각 정점의 쌍이 가지는 최단 경로의 길이를 나타내는 행렬 이라고 하자 즉, D[i][j] : vi 에서 vj 로 가는 최단 경로의 길이이다. 그렇다면 가장 초기에 주어지는 정점들과 거리의 정보들을 D(0) 이라 하자 이 배열은 바로 옆 노드만 이동 가능한 행렬일 것이다. 왜냐하면 초기 정보들은 한 노드에서 다른 노드까지의 거리 정보이기 때문이다. 이제 k..

동적계획과 이항계수

동적계획과 이항계수

동적계획과 이항계수

동적계획법 문제를 더 작은 문제로 분할 -> 상향식(Bottom - Up) 으로 문제 해결 재귀적으로 하향식(Top - Down)으로 푸는 분할정복과 대비 동적 계획법으로 문제를 풀기 위해서는 재귀적 정의(점화식)을 상향식으로 구성 이항계수 - 분할정복 위의 성질을 사용하여 코드를 구성 def binomial(n,k): if (k==0 or n==k): return 1 else: return binomial(n-1, k-1) + binomial(n-1, k) 하지만, 한 이항계수 값을 구하는데 있어서, 중복되는 계산이 여러번 발생하는 문제점(비용증가)이 있다. 따라서, 동적계획의 방법을 생각해 보아야 한다. 동적계획 - 이항계수 위의 식을 하향식(재귀) 가 아닌 상향식으로 변환 B : 이항계수 배열 de..

백준 11726 - 2 x n 타일링 : dynamic programming

백준 11726 - 2 x n 타일링 : dynamic programming

백준 11726 - 2 x n 타일링 : dynamic programming

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 다이나믹 프로그래밍 방법 기본적인 다이나믹 프로그래밍 방법은 계산을 용이하게 하는데에 있다. 즉, 일반적인 완전탐색처럼 모든 계산을 다 하되, 다이나믹 프로그래밍의 간단한 개념은 주어지는 모든 계산을 하지 않고, 필요한 계산이 있으면 재사용하는 것이다. 간단히 예를들어, 피보나치수열처럼 같은 계산 구조가 반복될 경우, 새로운 해를 구할 때마다 모든 계산을 반복하지 않고 1번 계산했던것을 재사용한다면 계산량을 엄청나게 줄일 수 가 있다. 풀이 (1) 직사각형을 채우는방법은 2가지 밖에 없다. 1x2 타일을 1개 두거나 2x1 타일을 위아..

백준 N과 M (9) ~ (12) / 파이썬 백트래킹

백준 N과 M (9) ~ (12) / 파이썬 백트래킹

백준 N과 M (9) ~ (12) / 파이썬 백트래킹

문제번호 문제이름 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 15654 N과 M (5) 15655 N과 M (6) 15656 N과 M (7) 15657 N과 M (8) 15663 N과 M (9) 15664 N과 M (10) 15665 N과 M (11) 15666 N과 M (12) 지난 포스팅에서는 약간 응용을 하면 8번까지 풀이 가능한 1번 문제에 대한 코드를 살펴보았다. 이번에는 9번문제를 다뤄보도록 하겠다. 백준에서 N과M 9번 문제만 유일하게 정답률이 50%미만이다. 오늘날짜로 약 49% 이다. N과 M (9) www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수..

백준 N과 M (1) ~ (8) / 파이썬 백트래킹

백준 N과 M (1) ~ (8) / 파이썬 백트래킹

백준 N과 M (1) ~ (8) / 파이썬 백트래킹

문제번호 문제이름 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 15654 N과 M (5) 15655 N과 M (6) 15656 N과 M (7) 15657 N과 M (8) 15663 N과 M (9) 15664 N과 M (10) 15665 N과 M (11) 15666 N과 M (12) 백준 N과 M 파이썬 백트레킹 풀이 먼저, Backtracking 기법은 완전 탐색과 비슷하다. 즉 문제풀이에 가능한 모든 경우의 수를 고려하는 풀이법이다. 다만 한가지 더 추가하자면, 일반적으로는 어떠한 '조건'을 만족하는 경우의 수를 구할때 이 용어를 사용한다. 그러므로 일반적으로 모든 경우의 수를 구하는것보다 빠른데 그 이유는, 단순히 모든 경우를 구하는것이 ..

백준 11660 - 구간 합 구하기5 / 2차원 구간 합 알고리즘

백준 11660 - 구간 합 구하기5 / 2차원 구간 합 알고리즘

백준 11660 - 구간 합 구하기5 / 2차원 구간 합 알고리즘

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5..

백준 11659 - 구간 합 구하기4 / 구간 합(Prefix Sum) 알고리즘

백준 11659 - 구간 합 구하기4 / 구간 합(Prefix Sum) 알고리즘

백준 11659 - 구간 합 구하기4 / 구간 합(Prefix Sum) 알고리즘

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 첫 번째 도전 - 가장 기본적으로 파이썬의 리스트 슬라이싱을 이용하여 풀이하였다. 예를들어 3번째부터 6번째까지의 합을 구하라고하면 result = sum(nums[3-1 : 6]) 로 구하면 된다. 하지만 이 문제는 케이스수가 최대 10만, 각 케이스별로 최대 배열 10만 이라서 이렇게 풀면 ..

Greedy Algorithm (1) - 백준 1931 : 회의실 배정

Greedy Algorithm (1) - 백준 1931 : 회의실 배정

Greedy Algorithm (1) - 백준 1931 : 회의실 배정

그리디 알고리즘 (탐욕법) 을 적용할 수 있는 방법은 여러가지가 존재한다. 그리디 알고리즘은 단순히 설명하자면, 완전탐색이나 동적 프로그래밍처럼 가능한 모든 해를 둘러보지않고, 부분적으로 지금 당장 좋은 방법만을 선택해가는 방법이다. www.acmicpc.net/problem/1931 회의실 배정 문제를 풀어보며 익혀보자. 회의실 배정 문제에 그리디 알고리즘을 적용하여 푼다고 생각했을 때 (다른방식으로도 풀 수 있다.) 단순히 첫번째회의(회의시간 오름차순 정렬) 를 선택하고, 겹치는 것들을 제거한 후에 다시 가장 먼저 나오는 회의를 선택할 수도 있다. 다른 방식으로, 회의 길이가 짧은 순서대로 선택해 나갈수도 있다. 이처럼 문제를 푸는 방식은 여러가지가 존재한다. (물론 다 옳은 답을 내는것은 아니다. ..

티스토리툴바