문제 링크 14890번: 경사로 풀이 구현 문제 길은 세로, 가로로 있기 때문에 입력받으면서 arr1에는 가로, arr2에는 세로를 넣는다. 한 줄씩 길을 체크할 것이다. 먼저 현재 길인 i와 다음 길인 i+1을 비교해간다. 경사가 같을 때는 continue 1 올라가는 경우 (arr[i]+1 == arr[i+1])에는 앞에 i부터 l개를 확인하며 범위를 벗어나거나, 경사의 차이가 나서 경사로를 못놓거나, 이미 지어진 경우에는 return 0을 한다. slope[i] = 1을 해서 경사로를 넣는 것을 빼먹지 않는다. 1 내려가는 경우 (arr[i]-1 == arr[i+1])에는 뒤에 i+1부터 l개를 확인하며 3번과 같이 return하고 경사로를 놓는다. 1,2,3번 경우가 아니라면 경사의 차이가 2 이..
문제 링크 9370번: 미확인 도착지 풀이 문제가 복잡해보이지만 1504번 풀었다면 그렇게 어렵지 않은 문제 최단 경로에서 특정한 노드를 지나는 최단 경로를 구하는 문제이다. 값을 입력받으며 인접 리스트를 만든다. 루트 3개를 비교할텐데 s -> g -> h -> 후보지, s -> h -> g -> 후보지 중 작은 값과, s -> 후보지 값을 비교해서 같다면 해당 경로를 지났단 뜻이므로 answer에 추가해준다. 루트를 지나는 경로의 길이를 구할 때는 다익스트라 알고리즘을 사용한다. 출발 노드에서 모든 노드까지의 거리는 무한대로 만든뒤, 자신의 노드 dist만 0으로 만들어준다. 우선순위 큐를 이용하여 거리가 작은 노드부터 순서대로 방문한다. 해당 노드를 방문할 때 거리가 최소로 갱신된다면 pq에 넣고 ..
문제 링크 1504번: 특정한 최단 경로 풀이 다익스트라로 푸는 최단 경로 문제. 1 -> u -> v -> n과 1 -> v -> u -> n을 비교하면 되는 문제 입력 받으며 인접리스트를 만든다. 위에서 설명한 루트대로 다익스트라로 최단 경로를 구한다. 다익스트라는 거리 벡터를 모두 무한대로 초기화 하고 현재 시작할 노드를 0으로 만들고 현재 노드부터 우선순위 큐에 넣어 시작한다. dist의 값이 최소로 갱신될 때마다 pq에 노드를 넣어준다. 그렇게 while문이 끝나면 dist에 현재 노드부터 각 노드까지 최소 거리가 만들어질 것이다. 도착 노드를 return 그렇게 두 개의 루트의 값을 구해 최솟값으로 출력해주는데, 이 값이 무한대보다 크거나 같다면 -1을 출력한다. 코드 #include #inc..
문제 링크 입국심사 풀이 이분탐색으로 푸는 문제.. 떠올리는 게 어렵다.. 기준은 제일 빠르게 처리하는 1분과 가장 느리게 처리하는 심사관 * n이 될 것이다. 이 둘을 left와 right로 잡는다. 여기서 주의할 것은 long long 타입이기 때문에 right를 만들 때 int * int형으로 곱해져 int형이 나오기 때문에 형변환을 해주어야 함 mid는 left와 right의 중간 값을 잡고 이분 탐색을 시작할텐데, 이 기준은 mid시간에서 몇 명의 사람이나 처리할 수 있느냐로 본다. cnt가 n보다 크거나 같으면 right의 범위를 줄여주고 answer를 갱신해주고, 작으면 left의 범위를 키워준다. left의 위치가 right보다 작거나 같을 때까지 반복해준 뒤 answer를 출력한다. 코드..
문제 링크 롤케이크 자르기 풀이 set으로 풀었는데 시간 초과가 나서 힌트를 얻은 문제 굳이 기준을 잡아서 할 필요 없이 둘로 나누는 것이기 때문에 기준에서 하나씩 빼면 된다. set1에 toppings를 다 넣는다. 이 때 토핑의 개수를 생각해야하기 때문에 cnt 벡터로 토핑의 개수를 세준다. 이제 토핑을 하나씩 빼서 set2에 넣어줄텐데, 하나 뺀 토핑의 개수가 0일 경우 set1에서 지워준다. set1과 set2의 사이즈를 비교해서 같다면 answer++ 해준다. 코드 #include #include #include using namespace std; int solution(vector topping) { int answer = 0; set set1, set2; vector cnt(topping...
문제 링크 1922번: 네트워크 연결 풀이 최소신장트리 문제. 난 union-find 알고리즘으로 풀었다. 간선을 cost 기준으로 오름차순 정렬한다. 각 노드들은 각자의 부분집합으로 자기 자신 값을 넣는다. (subset) 이제 사이클이 생기지 않도록 비용이 적은 간선부터 연결한다. 이 사이클을 확인하는게 union-find이다. unionFind 함수에서는 a노드와 b노드의 부모 노드를 비교하여 같지 않으면(다른 부분집합이면) 연결한 뒤 true를 return한다. parent 함수는 노드의 부모 노드를 찾는 함수인데, 재귀 함수를 통해 따라가서 return한다. merge 함수는 각자 다른 부분집합을 합치는 함수이다. a노드의 부모와 b노드의 부모를 찾아 서로 연결한다. 부모의 숫자가 작은 쪽으로 ..
문제 링크 1516번: 게임 개발 풀이 그냥 위상 정렬인줄 알았지만.. 동시에 건물을 지을 수 있는 것을 간과해버려서 조금 헷갈렸다. 3번째 건물을 지으려면 10시간이 걸리고, 1과 2번째 건물을 지어야 가능하다고 할 때, 1번째 건물을 짓는 데에 1시간, 2번째 건물을 짓는 데에 3시간이 걸린다고 해보자. 1번째와 2번째 건물을 서로 간섭하는 게 없으니 동시에 짓고, 더 오래 걸리는 2번째 건물을 짓고 나서 3번째 건물을 지을 수 있다. 그러므로 우선순위 큐를 이용해 지어주어야 한다. 입력 받으며 인접리스트와 진입차수 벡터를 만든다. 위상 정렬을 진행할 큐는 오름차순 우선순위 큐로 만들어서 더 빨리 걸리는 건물을 먼저 짓도록 한다. n번 반복하여 위상 정렬을 실행한다. cur 노드와 연결된 노드들의 진..
문제 링크 2252번: 줄 세우기 풀이 위상 정렬 알고리즘을 알아야 풀 수 있는 문제. 모르겠어서 찾아봄 .. 알고리즘 자체는 간단하다. 사이클이 없는 방향 그래프에서 순서를 찾을 때 사용하는 듯하다. 해당 노드로 들어가는 간선이 없어야(다 해치워야) 그 노드를 방문할 수 있는 형태이다. 입력을 받으며 인접 리스트를 만들고 진입 차수 벡터도 만들어준다. 노드 1부터 n까지 확인하는데, 맨 첫번째 순서인 노드를 찾기 위해 진입차수가 0이고, 방문하지 않은 노드라면 위상 정렬을 실행한다. queue에 첫 번째 노드를 넣고, 방문 처리 뒤 queue가 빌 때까지 반복한다. q에서 나온 노드를 출력하고, 해당 노드 cur과 연결된 노드들을 cur과의 간선을 끊었을 때(진입차수를 줄이고), 진입차수가 0이 된다면..
문제 링크 1946번: 신입 사원 풀이 그리디 문제. n이 10^5라서 완탐으로 풀기엔 시간 초과가 남 a와 b를 입력 받으면서 a의 등수 인덱스에 b의 등수를 넣는다. 1등은 무조건 합격이기에, minNum을 1등의 b 점수로 넣고 2등부터 확인한다. minNum보다 arr[i]가 크다는 것은, 나보다 a 점수가 좋은 사람들이 b 점수도 좋다는 뜻이므로 제외한다. minNum은 계속해서 최솟값으로 갱신한다. 예제를 통해 arr를 만들면 이런 식이 될 것이다. a 등수 인덱스 1 (등) 2 3 4 5 6 7 arr (b 등수) 4 (등) 5 6 2 7 1 3 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0..
문제 링크 16234번: 인구 이동 풀이 DFS로 풀긴 했는데, BFS가 편했을 것 같다.. 값을 입력 받으며 벡터를 만든다. 인구 이동이 있어 다시 확인해야 하는지 체크하기 위한 변수 flag가 true라면 계속 인구 이동 시킨다. 첫번째는 인구 이동을 해야하는지 체크해야 하므로 do-while문을 쓴다. 벡터를 돌며 visited[i][j]가 0이면 탐색되지 않았다는 것이므로 dfs 함수로 탐색을 시작한다. dfs 함수에서는 상하좌우를 확인하며 gap이 범위 안에 있다면 재귀 호출을 한다. 영역 내의 총 합을 구하기 위한 sum과 영역 칸의 개수를 구하기 위한 cnt를 갱신한다. 영역 구분이 끝나면 arr의 값을 바꿔줘야 하므로 해당 위치 값을 갖는 unionArr에 추가한다. dfs를 돌고 한 영역..
