![]()
1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. Logic 이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다. binary search를 구현해서 푸는 방법과 C++의 ..
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. Logic 2252번 문제와 동일하게 위상정렬로 푸는 문제지만 살짝 다르다. 1766번 문제집은 문제를 푸는 조건이 있다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 이중 키포인트는 3번이다. 나는 위상정렬을 BFS를 활용하여 푸는데 1..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 1. Logic - 전형적인 투포인터 문제이다. 양쪽 끝에서 중간까지 오는 포인터 두개를 선언한 뒤 각 포인터에 해당하는 컨테이너 값을 더한 값이 이전의 sum값보다 작으면 값을 갱신해준다. 현재 포인터에 해당하는 sum값이 0보다 크면 값을 줄여줘야하기 때문에 right 포인터를 하나 줄여주고 이외에는 값을 키워야하기 때문에 left 포인터를 하나 올려준다. 2. Code #include ..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. Logic 해당 문제의 조건을 보면 사무실의 범위가 최대 8 * 8로 아주 작은것을 알 수 있다. 그렇기 때문에 완전탐색으로 구현할 수 있다. 시간복잡도는 모든 사무실을 다 탐색할 경우 8 * 8, CCTV의 4방향을 다 탐색한다는 가정 하 최악의 경우 8 * 8 * 4 정도가 나올 것 같다. 먼저 각 cctv 타입 별 탐색할 수 있는 범위의 경우의 수는 1번 CCTV : 상, 하..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. Logic - 먼저 시간 복잡도를 계산해봤을때 넉넉잡아 계산해도 50 * 50 * 13 * 13을 해도 42만정도가 나오기 때문에 충분히 돌 수 있다. 그러므로 완전탐색 문제인 것을 알 수 있다. 폐업시키지 않을 치킨집의 최대 갯수를 준다고 했는데 치킨집은 많으면 많을 수록 좋기 때문에 다 골라준다고 생각하면 된다. 여기서 폐업시킨다는 뜻은 고르지 않는다로 생각하고 치킨..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. Logic - 첫번째 문자부터 확인하면서 각 문자열의 끝까지 확인하고 만약 각 인덱스의 서로의 문자가 같으면 값 +1 Topdown형식으로 풀었다. 2. Code #include using namespace std; int dp[1001][1001]; string str1, str2; int solve(int s1Idx, int s2Idx) { /..
![]()
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. Logic - 집중국의 수신 가능 영역을 최소화 시키기 위해서는 집중국을 세울수 있는 갯수로 지어진 k만큼 다 세워 줘야 한다. 센서를 세우는데 가장 적합한 위치는 오름차순 정렬을 했을 때 인접한 두 센서의 가운데에 세워야 한다. 케이스에서 나온 1 6 9 3 6 7 > 오름차순 정렬 1 3 6 6 7 9 > 인접한 두 노드의 거리를 빼주기 dist : 2 3 0 1..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..
1. 개요신입 개발자로 취업하기 위해서는 코딩테스트는 거의 필수인 듯하다. 처음 시작할 때 백준 티어 기준 브론즈 5에서 현재 골드 1까지 올라오고 나서 회고 겸 처음 시작할 때 뭐부터 어떻게 해야 할지 정말 모르겠는 알고리즘 공부에 대해서 정리해 볼 것이다. 이 글은 지극히 주관적인 기준이며 알고리즘 및 코테 공부를 하는데 하나의 작은 기준?으로만 생각하고 각자 자신에게 맞는 공부법을 찾길 바란다.2. 알고리즘 공부 방법1. 약 30분 ~ 1시간 정도 시간을 정해놓고 그 시간을 넘겨도 못 풀면 구글링으로 다른 사람이 푼 코드를 보고 공부한다. 2. 풀이를 보고 복붙 하지 말고 이해하고 찾아보며 직접 따라 쳐본다. 백문이 불여일타 > 그냥 복붙 하면 살 뺀다고 하고 운동 유튜브 보고 운동했다고 하는 거랑..
