알고리즘 (21) 썸네일형 리스트형 [백준/c++] - 1005 ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 목차 1. 문제 풀이 2. 코드 문제풀이 더보기 처음에는 문제 분류가 dp로 되어 있어서 왜 dp로 풀리는 지에 대해 고민해 보았다. 건물의 건설은 주어진 순서대로 진행해야 하기에 그리디 방식으로 단순하게 구현하면 되지 않을까하고 생각해 보았으나, 건물이 지어지는 순서를 제대로 파악하기 힘들뿐만 아니라, 문제에서 무조건 마지막에 지어지는 건물의 건축 시간만 물어보는 게 아니므로 모든 건물에 .. [백준/c++] - 1010 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 목차 1. 문제 풀이 2. 코드 문제풀이 처음 문제를 보고선 고등학교 확통때 배운 조합(Combination)이 떠올랐다. 하지만 알고리즘 분류가 DP여서 dp로 풀어보는 쪽으로 접근하였다. dp로 풀기위한 핵심은 이전에 계산한 값들을 통해 다음 값들을 계산할 수 있는가를 판단하는 것이다. 이 문제의 경우 이 조건을 충족하기에 dp로 풀 수 있었다. 다음 예시를 보자. 왼쪽에 2개의 사이트, 오른.. [알고리즘 정리] - 동적 계획법(Dynamic Programming) 목차 1. 들어가며 2. 동적계획법이란 3. 예제 적용 들어가며 코딩테스트 단골 문제로 등장하는 동적 계획법, 일명 DP에 대해 정리해보려고한다. 정말 자주 출제되는 유형임에도 문제 유형이 DP인지 파악하기가 정말 어렵다. 그리고 그만큼 어려운게 사실이니 이번에 알아보자. 동적계획법이란 더보기 동적계획법 (Dynamic Programming) 먼저 동적 계획법이란 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 즉, 작은 문제들을 해결하여 큰 문제를 해결하는 방식의 기법인데, 동적 계획법이라는 이름과 전혀 매칭이 되지 않는다. 위키백과에는 이 이름의 유래에 대해 아래와 같이 설명한다. 알고리즘과 그 이름이 매칭이 안되서 찾아.. [프로그래머스/c++] - 빛의 경로 사이클 https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 목차 1. 문제 접근 2. 풀이 3. 느낀점 문제 접근 더보기 BFS와 비슷한 개념으로 접근하였다. 큐를 사용하지 않았기에 BFS라고 할순 없지만 방문확인 배열을 사용하여 사이클을 체크하였으므로 BFS와 비슷한 방식이라 볼 수 있다. 문제에서 중요한 것은 지금 위치에서 이동하였을 때 사이클이 발생하는 지를 판단할 수 있어야하는 것이었다고 생각한다. 예를 들어 이전에 방문한적이 있는 노드일지라도 그.. [백준/c++] - 12865 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 유명한 DP문제이다. DP문제를 푼지 너무 오래되어서 다시 풀어봤는데, 다시 봐도 점화식을 떠올려내기 쉽지않다. #include #include #include #include using namespace std; struct Thing { int W; int K; }; int dp[101][100001]{ 0, }; // i개까지.. [프로그래머스/C++] - 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스에서 코테 준비를 하다가 만난 문제이다. 특별히 유별나게 어려운 문제는 아니었지만 코드 작성에 어려움을 많이 겪었기에 한 번 정리해보려 한다. 문제는 단순하다 집이 있는 좌표를 (1, 1)이라고 할 때, (n, m)지점에 있는 학교까지 갈 수 있는 최단 경로의 수를 구하는 것이다. 문제를 읽고 최초로 시도한 것은 DFS였다. 사실 시간 초과가 날 것같은 불안감에 코드를 작성하면서도 자신.. [알고리즘 정리] - Kruskal 알고리즘 목차 1. 들어가며 2. 최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘 3. 유니온 파인드(Union-Find) 들어가며 이번 글에서는 크루스칼(Kruskal) 알고리즘에 대해 정리해보려고 한다. 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하고자 할 때 사용하는 알고리즘이다. 최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘 더보기 최소 신장 트리(Minimum Spnning Tree) 위의 그림과 같이 방향이 없는 가중치 그래프가 있다고 가정해보자. 여기서 최소 신장 트리란 모든 노드를 잇는 가중치가 최소인 신장 트리를 의미한다. 간단히 말하면 모든 노드들을 최소의 비용으로 방.. [백준/c++] - 1916 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 연습겸 풀었던 문제인데 개인적으로 꼭 기억해야할 부분이 있어서 글을 써본다. 문제 자체는 특별할 것 없는 다익스트라 구현 문제이다. 문제 풀이 자체에는 문제가 없었는데 계속해서 메모리 초과가 났다. 일단 코드를 보자. #include #include #include #include #include #include using namespace std; /.. 이전 1 2 3 다음
