본문 바로가기

분류 전체보기

 (263)
[백준 20152] Game Addiction 조합론 문제 www.acmicpc.net/problem/20152 [문제 풀이] (N, N)에서 (M, M)으로 가는 최단경로의 개수 중, $y x$는 사용하지 않습니다. (N, N) 지점의 dp테이블 값을 0으로 설정한 뒤, 오른쪽 위로 이동하면서 dp테이블의 값을 (왼쪽의 dp테이블 값) + (아래쪽의 dp테이블 값)으로 설정해주면 풀이가 가능합니다. 점화식으로는 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]입니다. 그러나 이 문제는 조합으로도 풀이가 가능합니다. 우선, $y > x$인 부분을 사용하지 않는다는 조건이 없었다면 더 쉬운 문제입니다. 높이가 h고 너비가 w인 2차원 평면에서 양 끝점으로 이동하는 최단 경로의 개수는 $\dbinom{h + w}{h}$입니다. 해당 ..
[알고리즘] 벨만-포드 (Bellman-Ford) 최단 경로 [알고리즘 소개] 가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘. [알고리즘 특징] 음수 가중치 가능 모든 간선에 대해 조사 음수 사이클 판정 가능 [코딩 방법] 간선에 대한 정보를 저장할 클래스(구조체) 생성, 배열에 저장 dp용 배열 생성, INF로 배열을 채우고 시작점에 대해서만 0으로 초기화 V - 1회동안 모든 간선을 확인하면서 최단경로 갱신 이후 V회동안 모든 간선에 대해 더 확인하면서 음수 사이클이 발생했는지 확인 음수 사이클의 존재만 알고 싶다면 1회만 모든 간선에 대해 확인해도 무방 [시간 복잡도] $O(VE)$ [공부용 링크] youtu.be/Ppimbaxm8d8
[알고리즘] 다익스트라 (Dijkstra) 최단 경로 [알고리즘 소개] 가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘. [알고리즘 특징] 우선순위 큐 사용 dp와 그리디 음수 간선 불가 [코딩 방법] 인접 리스트 그래프를 정점과 가중치를 저장할 클래스(구조체)로 구성 dp용 배열과 클래스 타입 최소 우선순위 큐 생성 시작점에 대해 배열의 가중치 0으로 초기화, 우선순위 큐에 시작점 정보 넣음 우선순위 큐가 빌 때까지 원소를 제거 제거한 원소에 대해 dp값보다 원소의 가중치가 더 큰 경우 가지치기 가지치기 후 인접 정점 확인, dp값보다 작다면 dp 갱신 후 우선순위 큐에 삽입 [시간 복잡도] $O(E logE)$ [공부용 링크] m.blog.naver.com/ndb796/22..
[딥러닝] 0. Tensorflow 설치 딥러닝을 시작하기에 앞서 Tensorflow를 먼저 설치해야 한다고 합니다. 해당 책에서는 pip을 사용한 설치 방법을 소개하였습니다. 그런데 반 페이지 정도로만 소개했던 Tensorflow 설치부터 문제가 생겼습니다. 여러 번의 시도 끝에 Tensorflow 설치를 성공했습니다. 제가 겪었던 문제들과 해결법을 적어보려 합니다. pip install tensorflow tensorflow를 설치하는 명령어입니다. 터미널에서 해당 명령어를 입력하면 설치가 가능합니다. 설치 자체는 간단합니다. 그러나 해당 명령어를 실행하기까지 많은 고비들이 존재합니다. 1. 'pip'은(는) 내부 또는 외부 명령, 실행할 수 있는 프로그램, 또는 배치 파일이 아닙니다. tensorflow 설치 시에 가장 많이 마주하는 문구..
[프로그래머스 코딩테스트 고득점 Kit - 정렬] K번째수 정렬 문제 programmers.co.kr/learn/courses/30/lessons/42748 [문제 풀이] 주어진 배열에 대해 [i, j] 범위에 대해 k번째 수를 구하는 문제입니다. 배열을 주어진 범위에 대해 잘라서 정렬한 후 k번째 수를 출력하면 해결이 가능합니다. for문을 사용하여 특정 범위만큼을 잘라 새 배열에 넣거나 c++의 경우는 포인터를 사용하여 for문 없이 간결하게 떼어낼 수 있습니다. i, j, k는 1번째부터 시작하고 인덱스는 0번째부터 시작함에 주의하셔야 합니다. 문제를 꼬아놓거나, 기술적으로 어려운 부분이 없는 문제라서 간단한 문제입니다. [소스 코드] / C++ #include #include #include #include using namespace std; vecto..
[백준 7662] 이중 우선순위 큐 우선순위 큐 문제 www.acmicpc.net/problem/7662 programmers.co.kr/learn/courses/30/lessons/42628 해당 문제와 동일합니다. [문제 풀이] kangwlgns.tistory.com/35 [소스 코드] C++ / 이중 우선순위 큐 구현 #include #include #include #include #include #include using namespace std; typedef long long ll; template class dual_priority_queue { priority_queue maxq; priority_queue minq; unordered_map maxdel, mindel; public: dual_priority_queue() ..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 이중우선순위큐 우선순위 큐 문제 programmers.co.kr/learn/courses/30/lessons/42628 www.acmicpc.net/problem/7662 위 문제와 동일한 문제입니다. 테스트 케이스는 백준이 더 강력합니다. [문제 풀이] 이중 우선순위 큐를 구현하는 문제입니다. 사실 자료구조에 대해 숙련이 되어 있다면 매우 간단한 문제입니다. 레드 블랙 트리 기반의 자료 구조들은 최댓값, 최솟값을 무려 $O(1)$에 불러올 수 있기 때문입니다. 즉 C++의 multiset같은 경우, 그 자체로 이중 우선순위 큐의 역할을 할 수 있습니다. 자바의 경우 TreeSet은 중복이 안되므로 TreeMap을 사용하여 중복 처리를 해주는 방식으로 해결할 수 있습니다. 자바는 TreeSet이면 first, last..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 디스크 컨트롤러 구현 문제 programmers.co.kr/learn/courses/30/lessons/42627 [문제 풀이] 모든 작업에 대해 (작업이 끝난 시간) - (작업이 요청된 시간)의 합을 최소로 만드는 문제입니다. 하나의 디스크는 하나의 작업만 처리가 가능합니다. 작업 시간이 전혀 겹치지 않는다면 이 문제는 전혀 문제가 아닙니다. 그러나 작업 시간이 겹치는 경우에 어느 작업부터 시작해야 하는지 골라야 하는 것이 어려운 문제입니다. (작업이 끝난 시간) - (작업이 요청된 시간)만 보면 생각하기 쉽지 않으니 조금 형태를 바꿔보겠습니다. (작업이 끝난 시간) - (작업이 요청된 시간)은 (작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)으로 치환할 수 있습니다. 이해가 안 될 수도 있으니 그..

티스토리툴바