키자드에 등록된 twenty-begin-new의 티스토리 포스트 목록

twenty-begin-new의 등록된 링크

twenty-begin-new로 등록된 티스토리 포스트 수는 4건입니다.

[c++] 백준 11066 파일 합치기 - 동적계획법 점화식 설계 실패, Bottom-up을 위한 문제 풀이 재 설계 [내부링크]

문제 설명 https://www.acmicpc.net/problem/11066 동적계획법을 사용해서 푸는 문제. 가능한 조합을 전수조사해서 그 중 minimum 값을 구해 dp 배열을 채워나가면 된다. 점화식을 세우는 과정에서 많은 어려움이 있는 문제이다. 점화식 조건이 어려울 뿐 아니라, 단순히 dp의 이전 인덱스들과의 단순 연산보다 조금 더 심화되었다. 나의 문제 풀이 시도 및 발생한 문제점 가능한 모든 조합을 찾아야 한다는 점을 빠르게 캐치하지 못했음(dp 점화식 설계 실패) 문제를 쪼개서 해결해야한다는 점은 이해하고 있었지만, 점화식 설계가 틀렸다. 나의 접근은, 2차원 dp 배열에서 i 인덱스는 '어디까지 보았는가', j 인덱스는 '몇 개를 더했는가' 였고, dp 배열을 업데이트 할 때, 이전의..

[c++] 코딩 테스트 대비 - 그래프 이론, 그래프 탐색 문제 접근법 정리 [내부링크]

추후 빠른 문제 이해 및 개념 정리를 위해 정리해놓습니다(앞으로도 계속 추가 예정) 기본 DFS BFS 접근법 DFS(Depth First Search) 첫 번째 방법: 재귀 + visited 배열 사용하기 // Recursive Approach 예시 void dfs_search(vector graph[], int vertex, bool _visited[]){ for(int i=0; i

[c++] 백준 1325 효율적인해킹 - 연결된 노드 개수 구하는 방식 실패원인 분석 및 해결, 반례 [내부링크]

문제 설명 https://www.acmicpc.net/problem/1325 A->B 라는 방향이 주어지는 그래프이며, 이 관계에서는 B가 A를 신뢰한다, B 입장에서 A를 해킹할 수 있다, 즉 B가 기준이 되는 문제이다. B 기준에서 연결된 노드의 개수가 몇 개인가, 노드별로 구분해서 카운트하고 정렬하는 문제이다. 방향 그래프 + 탐색 + 정렬 의 간단한 응용문제이나, 기계적으로 문제들을 풀었다면 사소한 부분들에서 헷갈리기 쉬운 문제이다. 문제풀이 시도 1 도착지점의 노드가 중요한 문제이므로, A B 라는 인풋이 주어졌을 때, A를 기준으로 graph를 그리지 않고, B를 기준으로 그래프를 그렸음(push_back을 거꾸로 했다는 의미) B 기준에서 연결된 노드의 개수를 세는 문제와 동일하다. B 기준..

[c++] 백준 2294 동전2 - dp 점화식 구상 실패 및 시간복잡도 분석 이후 문제풀이 [내부링크]

문제 설명 https://www.acmicpc.net/problem/2294 Dynamic Programming의 정석과도 같은 문제 유형 중 하나이다. 주어진 동전의 가치로 목표 가치를 달성하기 위해 필요한 최소의 동전 개수를 계산하기 위해 다이나믹프로그래밍으로 접근해야 한다. 문제에 따라서 완전탐색 등의 다른 방식으로도 접근이 가능하나, 해당문제는 조건에 의해 시간복잡도를 계산해서 제한 시간 안에 계산이 가능한지 확인한 후, 완전탐색으로는 불가능하다는 점을 인식해야 한다. 문제 풀이 시도 및 문제점 고찰 첫 번째 아이디어: 목표 가치(ex. 15)까지의 크기를 갖는 배열을 생성한 후, 0부터 해당 목표 index까지의 최소 동전 개수를 하나씩 계산해서 배열을 채워나가는 방식을 구상하였으나, 주어진 동..