개인사

리뷰 https://www.acmicpc.net/problem/9251문자열 두개 중 최장 공통 부분 수열의 길이를 구하는 문제 전역 변수dp : 문자열 a, b의 LCS를 동적계획법으로 찾으며 각 단계를 저장할 2차원 정수 배열 크기는 1001 * 1001로 초기화 함수없음  문제풀이문자열 두개를 각각 문자열 변수 a, b에 저장한다.a, b의 길이를 각각 정수형 변수 len1, len2에 저장한다.len1 * len2 크기의 2중 for문을 개행해 준다. 이때 인덱스는 1부터 문자열의 길이까지 포함되도록 한다.a, b의 현재 탐색범위 이전의 문자가 같을 경우 현재 dp인덱스를 이전 dp인덱스 + 1로 저장해 준다.같지 않을 경우 i의 현재 인덱스, j의 이전 인덱스값과 i의 이전 인덱스, j의 현재 ..

리뷰 max이 하나가 정답을 좌지우지 했다 ㅠㅜhttps://www.acmicpc.net/problem/2056 전역 변수n : 작업의 개수 함수없음  문제풀이n값을 입력 받고 작업 시간 정보 times와 인접 리스트를 초기화할 정수 벡터 path를 n + 1크기로 초기화 한다.1부터 n개의 각각의 작업에 걸리는 시간을 times 벡터에 저장해 준다.이후 선행이 필요한 작업을 인접 리스트로 추가해 준다, 역방향으로 삽입해 주어야 한다.선행 작업의 개수를 저장할 벡터 cnt를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.각 작업을 순회하며 작업의 인접리스트에 저장된 작업을의 cnt를 증가시켜준다.정수형 큐 q를 초기화 한 후에 cnt가 0인 작업을 큐에 넣어준다.정답을 저장할 정수형 벡터 ans를 ..

리뷰 트리에서의 다이나믹 프로그래밍을 활용하여 얼리어답터의 최소 갯수를 구하는 문제https://www.acmicpc.net/problem/2533 전역 변수n : 노드의 개수lst : 인접 리스트를 통해 노드간 양방향 간선 정보를 저장할 2차원 정수형 벡터dp : 각 노드가 얼리어답터일때와 아닐때의 정보를 저장할 배열v : dfs탐색 시 노드의 방문 정보를 저장할 배열 함수1. dfsvoid dfs(int cn) 깊이 우선 탐색을 통해 얼리어답터의 개수를 재귀적으로 구해줄 함수현재 노드를 매개변수를 통해 전달받고, 각 인접리스트의 노드를 매개변수로 전달해 준다.함수 실행 시 현재 노드가 얼리어답터일때는 1, 아닐때는 0으로 초기값을 세팅해 준다.인접리스트를 순회하고 자식 노드가 방문하지 않았을 경우 우..

리뷰 노드의 개수가 적을 경우 고려할 수 있는 최단 경로를 구하는 방법인 플로이드 와샬을 사용하는 문제https://www.acmicpc.net/problem/11404 전역 변수MAX_D : 거리의 최대값 보다 크게 설정해줄 정수형 상수 변수, 10만 * 10만 이상으로 초기화 해주면 된다.n, m : 노드의 개수 n, 간선의 개수 mlst : 인접 리스트를 행렬으로 변환할 정수형 2차 배열, 행, 열을 노드의 최대 개수인 100보다 크게 설정해 준다.path : 인접 리스트를 저장할 벡터, 다음 노드, 간선 두개를 모두 저장해야 한다.dist : 특정 노드끼리의 거리를 저장할 정수형 2차 벡터 함수1. inputvoid input() 노드와 간선의 개수를 입력 받고 인접리스트와 인접 행렬을 초기화 해..

리뷰 알고리즘 분류에 다이나믹 프로그래밍이 있어 혼란이 왔었는데 DFS로도 충분히 AC가 가능한 문제였다.https://www.acmicpc.net/problem/15681 문제 풀이전역 변수n, r, q : 노드의 개수 n, 루트 노드 r, 쿼리의 개수qdp : 각 노드가 루트인 서브트리에서의 하위 노드의 개수(자신을 포함한다.)v : DFS 내부에서 사용할 방문처리 배열, 최대 노드의 개수보다 크게 설정해 준다.path : 인접 리스트를 저장할 정수형 벡터 배열, 최대 노드의 개수보다 크게 설정해 준다. n, r, q를 각각 입력 받아주고, dp를 n + 1크기로, 기본값은 자기 자신을 포함하기 위해 1로 세팅해 준다.n - 1개의 간선 정보를 입력 받아 양방향 인접 리스트를 생성해 준다.루트를 방문..

리뷰 입력되는 숫자의 범위가 10000이므로 10000까지의 값을 미리 구해놓은 뒤 O(1)의 속도로 쿼리를 처리하는 문제https://www.acmicpc.net/problem/15989 문제 풀이정수형 배열 dp를 10001 크기로 설정한 후, dp[1], dp[2], dp[3]은 1로 초기화를 해준다.n이 10인 경우까지 손코딩을 해보면 쉽게 점화식을 도출할 수 있다.점화식 : dp[i] = dp[i - 3] + i / 2 + 1t값을 입력 받고 t번에 입력되는 테스트케이스를 dp의 인덱스로 출력해 주면 된다. 참고 사항n = 1 ~ 10까지의 케이스11 121 1 12 131 1 1 12 1 12 23 11 1 1 1 12 1 1 12 2 13 1 13 21 1 1 1 1 12 1 1 1 12 2..