알고리즘/알고리즘 문제 풀이 (17) 썸네일형 리스트형 [백준/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개의 사이트, 오른.. [프로그래머스/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였다. 사실 시간 초과가 날 것같은 불안감에 코드를 작성하면서도 자신.. [백준/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; /.. [백준/c++] - 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net DFS와 BFS모두 써야했던 문제이다. 문제에서 총 3개의 벽을 세우는 코드를 어떤 식으로 짜야할지 고민하다가 정답 코드를 참고했는데 대부분 DFS로 하였길래 DFS를 활용했다. 벽을 세우는 위치를 어떻게 결정하지? 라는 생각을 가지고 문제를 보다가 맵의 크기가 최대 8 x 8인 것을 확인하고 '아 백트래킹 문제구나' 라는 것을 깨달았다. 그리고 그것을 DFS로 구현해서 빠르게 구현하는 것이 포인트인 문제라고.. [백준/c++] - 1987 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음에는 그래프 문제같아서 BFS로 접근해볼까 했다. 근데 잠깐 생각해보니 어느 지점에 대한 최단 경로를 구하는 것이 아니라서 아 이건 DFS로 풀면 되겠다 라는 생각까진 떠올렸는데 DFS가 익숙치 않아서 정답코드를 보고 참고해서 다시 풀게 되었다. DFS로 풀면되서 특별하게 어려운 문제는 아니지만 보통 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있다고 생각했었는데 그렇지 않은 문제도 .. 이전 1 2 3 다음
