공부&일상 기록

문제 정보https://www.acmicpc.net/problem/20926 문제문제 해결과정문제 분석 및 시간복잡도 계산 1. 출발점 ~ 도착점까지의 최단시간을 구하는 '최단경로' 문제였다.2. 정점 사이의 (인접한 두 좌표간의) 가중치(미끌시간)이 달랐다. ⇒ BFS를 사용할 수 없다. (BFS는 가중치가 동일해야 함)3. 각 가중치는 0이상 9이하라고 주어졌으므로, 가중치가 양수였다. ⇒ '다익스트라'와 '플로이드워셜' 모두 사용 가능다익스트라 : '시작점 ~ 다른 모든 정점' 사이의 최단거리 구함. 시간복잡도는 O(E*logV)플로이드워셜 : '모든 정점 쌍' 사이의 최단거리 구함. 시간복잡도는 O(V^3)시간복잡도는 이전 블로그 포스팅을 참고4. 출발점과 도착점이 주어졌으므로, 시간복잡도가 더 ..

문제 정보https://www.acmicpc.net/problem/14501 문제  문제 해결 과정완전 탐색 풀이Ti와 Pi를 살펴보면, 상담기간이 길다고해서 상담금액이 큰 것이 아니었다. 즉, 상담기간과 상담금액은 랜덤하게 주어졌으므로, 그리디와 같은 방법으로는 접근할 수 없고 완전탐색이 필요한 문제이다. 각 날짜의 상담을 진행하거나 미진행할때의 모든 경우를 생각해보면, 가능한 경우의 수는 다음과 같다.1일(상담/미상담) x 2일(상담/미상담) x ... x n일(상담/미상담) = 2^n가지 문제에서 n이 최대 15라고 주어졌으므로, 시간복잡도는 O(2^15)이므로 주어진 시간 내에 풀 수 있다.하지만, 퇴사2와 같은 경우에는 n이 최대 1,500,000이므로 주어진 시간 내에 불가능하다.그렇다면, 랜..

문제 정보https://www.acmicpc.net/problem/2579 문제  문제 해결 과정완전 탐색 풀이매 번 계단을 한 칸(+1칸)  또는 두 칸(+2칸)을 오르는 경우, 가능한 경우의 수는 다음과 같다. 이동 1(+1칸/+2칸) x 이동 2(+1칸/+2칸) x ... x 이동 k(+1칸/+2칸) = 2^k가지 이때 계단의 개수가 최대 300개이므로, 이동은 최소 150번(+2칸으로만) 최대 300번(+1칸으로만) 일어나게 된다.따라서, 150 ≤ k ≤ 300이므로, 2^150  DP 풀이계단 4에 도착할 수 있는 경우를 주목해보았을 때, 다음과 같이 나뉘어 질 수 있다.계단 3에서 + 1칸계단 2에서 + 2칸연속하여 세 개의 계단을 밟을 수 없으므로, 불가능한 경우를 삭제(위에서 빨간색 x)..

그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡합니다. 지금부터는 이러한 경우의 최단경로를 구하는 알고리즘에 대해서 소개하겠습니다.1. 다익스트라 (Dijkstra)특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘입니다. 예를 들어 5개의 정점(1 ~ 5번)이 있고 1번 정점에서 출발한다고 가정하면, 1번에서 2 ~ 5번으로 가는 최단거리를 구해줍니다.양의 가중치만 있는 그래프에서만 다익스트라를 이용해 최단거리를 구할 수 있으며, 음의 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist값이 더 작아질 수 있기 때문에 최단거리임을 보장할 수 없게 됩니다. 다익스트라의 아이디어다른 지점까지의 거리는 모르지만, A라는 지점까지 가는 ..

문제 정보https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWxQ310aOlQDFAWL 문제 문제 해결 과정완전 탐색 풀이1) 각 우리별 햄스터 숫자 순열 생성각 우리별로 최소 0마리 최대 x마리의 햄스터를 배치할 수 있고, 이러한 우리가 n개가 있다고 하였다. 각 우리별로 햄스터 숫자를 배치하는 순열을 만들어 보면 경우의 수는 다음과 같다.1번 우리(0~x마리 → x개) * 2번 우리(0~x마리 → x개) * ... * n번 우리(0~x마리 → x개) = x^n가지 x는 최대 10이고 n은 최대 6이라고 하였으므로, 우리별로 햄스터 숫자를 배치하는 순열의 경우의 수는 10^6이 된다. (정확히는 0~x마리는 x+1..

1. 그래프 (Graph)그래프의 정의여러 개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조로, 관계를 추상적으로 표현한 구조입니다.예를 들어, 정점은 SNS라면 각각의 유저를, 지하철 노선도라면 역을 의미하고, 관계는 SNS라면 팔로우 관계를, 지하철 노선도라면 역과 역을 잇는 길을 의미합니다. 그래프의 분류그래프는 방향성과 가중치 유무 등에 따라 몇 가지 유형으로 나뉩니다.방향성에 따른 분류무방향(Undirected) 그래프 : 간선에 방향이 없는 그래프입니다. 즉, 그래프 내 모든 길을 양방향으로 이동할 수 있음을 의미합니다.방향(Directed) 그래프 : 간선에 방향이 있는 그래프입니다. 즉, 그래프 내 한쪽 방향으로만 갈 수 있는 길이 하나라도 있음을 의미합니다. 차..

1. 동적계획법동적계획법의 정의동적계획법이란 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법을 뜻합니다.점화식(작은 문제와 큰 문제간의 관계식)을 기반으로 하는 방법이며, for문을 이용하여 해결할 수도 있고, 재귀함수를 이용하는 것도 가능합니다.2. Memoization (Top-Down Approach)Memoization의 정의재귀함수를 이용하여 문제를 해결하는 과정에서, 이미 한번 계산한 결과를 기록하여, 동일한 작업의 계산을 반복하지 않는 것입니다. 즉, 각 n에 해당하는 값을 정확히 한 번씩만 계산하게 됩니다. 이런식으로 값을 기록하고, 그 기록한 값을 참조하는 것을 메모이제이션이라고 부릅..

1. 해싱해싱의 정의해시함수는 임의의 데이터를 입력받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수입니다. 즉, 어떤 값을 넣더라도 특정 범위에 해당하는 값을 반환합니다. 만약, 해시 함수의 반환값을 0부터 시작하는 양의 정수가 되도록 조절한다면, 특정 값을 배열(해시 테이블)에 넣기 위해 해시 함수에 그 값을 넣고, 값에 해당하는 인덱스에 그 값을 넣어주는 방법을 사용할 수 있습니다.function append(key, value) set index = hash_function(key) hash[index] = value function find(key) set index = hash_function(key) if hash[index] != null return hash[in..

1. 트리 (Tree)트리 개념노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프Unrooted tree : 부모 자식 관계가 정의되지 않은 트리 (루트 노드 존재하지 않음) Rooted tree : 부모 자식 관계가 정의되어 있는 트리로, 루트 노드는 단 하나만 존재합니다.Unrooted tree에서 루트 노드는 사람이 정하기 나름입니다. 트리 용어노드(정점) : 각 지점을 의미합니다.간선(에지) : 두 노드를 연결하는 선을 의미합니다.루트 노드: 트리에서 맨 꼭기를 의미합니다.부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부릅니다. 한 노드의 자식노드 개수는 제한이 없지만, 부모 노드는 최대 1개만 존재합..

문제 정보https://www.acmicpc.net/problem/12865 문제 문제 해결 과정완전 탐색 풀이서로 다른 N개의 물품품으로 배낭을 채울 수 있는 경우의 수는 다음과 같다.물품 1(사용/미사용 → 2개) x 물품 2(사용/미사용 → 2개) x ... x 동전 N(사용/미사용 → 2개) = 2^N개 문제 조건에서 N이 최대 100이라고 하였으므로, 2^100 ≒ 10^30이므로, 문제 제한인 2초를 많이 초과한다. 따라서, 서로 다른 N개의 물품으로 배낭을 채울 수 있는 모든 경우의 수에 대해 이 무게가 K를 넘는지 확인하는 방식은 적합하지 않다. DP 풀이우선 그리디 풀이(가치 큰 것부터, 무게 작은 것부터, 단위무게당 가치 큰 것부터)를 생각했지만, 무게가 무겁다고해서 가치가 큰 것은 아..