알고리즘/Baekjoon

[C++] 백준 2606번 바이러스

그래프 문제. 그래프 이론을 알고있다면 쉽게 풀 수 있는 문제였다. 문제풀이 그래프 구현을 위해 vector와 bfs구현을 위해 queue STL을 사용했다. 정점의 개수와 간선의 개수를 받는 변수를 만들었다. adj_list 벡터를 사용해서 그래프를 구현했고 visit 배열로 방문한 정점인지 체크했다. result 변수로 결과값을 출력했다. 시작점은 어차피 1부터 시작하므로 따로 매개변수로 받아서 시작하진 않았다. 그리고 1번을 큐에 넣고 방문했다고 기록하고 반복문을 큐가 비어있지 않다면 계속 반복하게 했다. 현재 방문중인 정점과 연결된 정점들 중 방문하지 않은(혹은 큐에 들어가있지 않은) 정점들은 큐에 삽입하고 방문했다는 기록을 남긴다. 그리고 결과값에 1을 더해준다. 그래프 이론은 실버 정도의 난이..

[C++] 백준 2579번 계단 오르기

다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수승이 어마어마하게 크기 때문에 잘못된 접근이다.) 사실 시간초과 부분에 관련해서 게시물을 찾다가 반복문으로 충분히 해결가능 하다는 답변을 보았고, 얼핏 스쳐가는 코드에서 max 메서드를 보았다. max 메서드는 오래동안 안 써왔어서 생각을 못했는데, max 메서드를 써서 접근하기로 했다. 따라서 이건 포기하고 다이나믹 프로그래밍의 Bottom Up 방식으로 접근하기로 했다. 다시 접근할 때 max 메서드를 오랜만에 써서 그런지 머리가 잘 안돌아갔다. max(A, B)는 A와 B중 큰 값을 return해주는 algori..

[C++] 백준 2667번 단지번호붙이기

그래프 이론 문제. 연결 요소(Connected Components)의 개수를 구하고 각 연결 요소에서의 정점의 개수를 오름차순으로 정렬해서 출력하는 문제. 연결 요소의 개수는 DFS, BFS로 구할 수 있다. 나는 DFS를 이용해서 해당 문제를 풀었다. 문제풀이 먼저 입력받는 정수 n, 그리고 지도를 나타내는 2차원 배열 map(1~25의 idx를 사용하기 위해 26의 크기로 만들었다.) 각 연결요소마다 집이 몇 개가 있는지 세기 위해 house_count라는 정수형 변수를 만들었다. 그리고 해당 정점이 이전에 방문했는지 체크하기 위한 bool형 2차원 배열 visit을 만들었다. house_vec 벡터형 변수로 각 연결요소에서 정점의 개수들을 입력해서 저장했다. DFS 메서드이다. 사실 이 부분에서 ..

[C++] 백준 11399번 ATM

그리디 알고리즘 문제. 그리디 알고리즘이란? 각 단계에서 최선일 것 같은 방법을 선택하는 알고리즘. 어떤 값을 최대화, 최소화하는 문제의 해를 찾는 문제이다. 큰 수 혹은 작은 수부터 각 단계에서 최대한 사용하는 것이다. 매 순간 최선인 방법을 선택하는 알고리즘이지만, 그게 전체적으로 봤을 때 항상 최적의 방법은 아닐 수 있다 ! 처음 접근 방식 이 문제를 처음 봤을 때는, Pi 이런식으로 설명해서 점화식을 유도하는 문제라고 생각했다. 그래서 DP로 풀려고 했는데 특별하게 보여지는 규칙은 없었고 그냥 최종적으로 총 걸리는 시간을 더할 때 Bottom Up 방식과 비슷하게 더하는 것 뿐이였다. 문제에 두번째 예시를 보면 결국 시간이 적게 걸리는 사람부터 정렬했을 때 최소 시간의 합이 된다. 중간에 다른 조..

[C++] 백준 1003번 피보나치 함수

시간 제한과 문제를 보더라도 쉽게 알 수 있는 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍의 Bottom Up 방식으로 문제를 접근했다. F[0] = 1 0 F[1] = 0 1 F[2] = 1 1 F[3] = 1 2 . . . 즉, An = A(n-1) + A(n-2)임을 알 수 있다. 먼저 테스트 케이스 변수, 입력받는 정수 n이 있다. 그리고 pair 자료형의 배열을 사용해서 각 수마다 0이 나오는 횟수와 1이 나오는 횟수를 저장했다. pair 자료형은 {A, B}의 형태로 입력할 수 있다. make_pair(A, B)의 형태로도 입력할 수 있다. 첫번째는 first, 두번째는 second의 형태로 접근한다. 0과 1은 알 수 있으므로 미리 배열에 입력해 놓는다. 각 테스트 케이스마다 n을 입력..

[C++] 백준 9095번 1, 2, 3 더하기

처음 이 문제를 봤을 때 n이 작아서 백트래킹으로 문제를 풀려고 시도했다. 시간제한이 1초이므로 1억번의 연산이 가능한데 이 문제는 n이 아무리 커도 1억번을 넘지 않을거라 생각했다. 문제풀이 테스트 케이스를 입력받고 정수 n을 입력받으며 backTracking 메서드를 구현했다. 그리고 매 케이스마다 1, 2, 3 합의 개수를 나타내는 output 변수도 만들었다. 메인 함수에서는 간단하다. 매 케이스마다 결과값 output 변수를 0으로 초기화하고 backTracking 메서드를 1, 2, 3부터 시작한다. 이렇게 풀면 쉽게 맞출 수 있다. 그런데 이 문제는 백트래킹이 아닌 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법은 큰 문제를 작은 문제로 쪼개어서 푸는..

[C++] 백준 1260번 DFS와 BFS

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있다면 계속해서 탐색하는 것. 시작점이 루트가 되어서 깊이를 1씩 더해가는 방식이다. 보통은 재귀함수를 이용해서 구현한다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 백트래킹(backtracking) 알고리즘이 DFS에서 파생됐다. BFS란? 너비 우선 탐색(Breadth First Search)라는 그래프 탐색 방법 중 하나로, 이번에 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통은 자료구조 queue를 이용..

[C++] 백준 1002번 터렛

수학 문제. 예전에 처음 이문제를 봤을 때 원의 접점을 구하는 문제라고 생각 못했던 것 같다. 항상 그렇듯 알고리즘 문제에는 문제에 정말 많은 힌트가 들어있다 여기서도 변수에 r이라는 힌트가 주어져 있다. 그 말은 r은 원의 반지름. 원을 이용해서 풀라는 말이다. 문제 접근 방식 우선 두 원이 있을때 어떤 경우들이 있는지 확인해 보았다. 그렇게 보니 총 여섯 가지가 나오게 되었다. 따라서 두 원의 중점 사이의 거리, 반지름끼리의 합과 차만 알면 이 조건들을 구현할 수 있다. 우선 math.h 라이브러리를 사용해서 두 원의 중점 사이의 거리를 구할때 제곱과 루트 메서드를 사용했다. pow(수, 지수) : 수를 지수승 한다. sqrt(수) : 수에 루트를 씌운다. 메인함수의 시작부분에는 테스트 케이스 수를 ..

[C++] 백준 10989번 수 정렬하기 3

문제에서 입력받는 수의 개수가 1000만개이다. 메모리 제한이 8MB이고, int 자료형이 4byte이므로 모든 수를 저장했을 때 40MB가 돼서 메모리 초과가 난다. 문제 끝에 수가 10,000보다 작거나 같은 자연수라는 조건을 잘 확인했으면 카운팅 소트를 시도해 봤을 것 같다. 뭔가 고민을 많이 안하고 그냥 sort, priority_queue를 사용해서 풀려고 시도하다가 많이 틀렸다. 구현 자체는 크게 어려운 게 없다. 카운팅 소트는 입력을 받으면서 sort하는 알고리즘이다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creati..

[C++] 백준 10282번 해킹

다익스트라의 기초적인 문제. 다익스트라란? 그래프에서 시작점이 있을 때, 시작점에서부터 최단 거리로 한 점씩 이동해보며 해당 점의 최소거리를 확정해 나가는 알고리즘이다. 이 때, 특정 점에서 다른 점들까지의 거리를 구한다는 뜻은 그 특정 점까지의 최단 거리는 확정됐다는 뜻이다. 그래프 이론에서 중요한 알고리즘이다. 이 때 모든 간선치는 양의 정수라고 가정한다. 다익스트라는 머리로는 그리기가 쉬운데, C++에서 구현하려면 복잡한 문법을 많이 알아야 한다. 내 구현 기준으로는 pair : pair 자료형은 특정 자료형 두개를 동시에 저장할 수 있다. make_pair(1, 2) 혹은 {1, 2} 이런 식으로 사용 가능하다. priority_queue : 우선순위 큐는 T 자료형을 container(vecto..