개인사

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

리뷰 최소 한 개의 모음과 최소 두 개의 자음으로 구성된 정렬된 문자열의 암호를 찾는 문제https://www.acmicpc.net/problem/1759 전역 변수l, c : 암호의 길이 l, 암호로 사용했을 법한 문자의 종류 clst : 암호로 사용했을 법한 문자를 저장할 문자 배열, 크기는 16으로 초기화 한다.v : 방문 처리를 체크할 용도의 정수형 배열, 크기는 16으로 초기화 한다. 함수1. btvoid bt(int level, string cur, int ja, int mo) 백트래킹을 통해 암호가 될 수 있는 문자열의 조합을 찾아내는 함수매개변수로 재귀 단계 level, 현재의 문자열 cur, 자음의 개수 ja, 모음의 개수 mo를 전달받는다.c개의 문자열을 탐색해 준다, 만약 방문 처리가..

리뷰 각 단계별 맵과 현재 위치를 고려하여 목표 위치까지 이동할 수 있는지를 구하는 문제https://www.acmicpc.net/problem/16954 전역 변수lst : 초기 맵 정보를 저장할 문자열 벡터, 크기는 8로 설정한다.ans : 정답 정보를 저장할 정수형 변수v : 각 단계별 현재 위치에 대한 방문 정보를 저장할 3차원 정수형 배열, 8 * 8 * 8크기로 설정한다.dx, dy : 상하좌우, 대각선, 제자리를 고려한 방향배열Pos : 현재 위치를 나타낼 구조체 함수1. movingvoid moving(vector& map) 현재 맵에 존재하는 벽들을 모두 한칸씩 내려주는 시뮬레이션을 진행한다.맵의 아래서 부터 swap을 통해 각 행을 변경해 주고, 마지막에 0번행을 빈 칸으로 세팅해 준다..

리뷰 11명의 선수가 각 포지션의 최대 기량을 가질 수 있게 완전 탐색을 하는 문제https://www.acmicpc.net/problem/3980 전역 변수lst : 각 선수의 포지션별 기량 정보를 저장할 정수형 2차원 배열v : 방문 처리를 위한 정수형 배열tc, ans : 테스트케이스 수를 저장할 tc, 각 테스트 케이스마다 정답을 저장하고 출력할 ans 함수1. btvoid bt(int level, int sum) 완전 탐색에 사용할 함수 매개변수 level = 재귀 단계, sum = 현재 단계까지의 기량의 합이다.level은 재귀 단계이기도 하면서 현재 선수를 의미하기도 한다.따라서 level이 0일 경우엔 첫번째 선수의 11개 포지션에 대한 기량을 탐색한다.만약 0보다 클 경우 해당 선수를 해..

리뷰 알고리즘 분류에 다이나믹 프로그래밍이 있어 혼란이 왔었는데 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개의 간선 정보를 입력 받아 양방향 인접 리스트를 생성해 준다.루트를 방문..

리뷰 문제를 제대로 읽지 않아 대각선까지 일치해야 하는줄 알았다.처음엔 해쉬 + Find를 통해 풀어야 하나 고민했는데 깊게 생각하지 않고 열, 행, 그룹으로 방문처리 하며 재귀를 사용하면 된다. 너무 어렵게 생각하지 말자https://www.acmicpc.net/problem/2239 문제 풀이전역 변수lst : 맵 정보를 나타낼 정수형 2차 배열cnt : 맵에 남아있는 0의 개수를 체크할 변수flag : 스도쿠 퍼즐이 완성되었는지 체크할 변수cols : 현재 행 기준 모든 열의 방문처리를 체크할 정수형 2차 배열rows : 현재 열 기준 모든 행의 방문처리를 체크할 정수형 2차 배열groups : 3*3 크기의 그룹 내의 방문처리를 체크할 정수형 3차 배열 9 * 9 크기의 for문을 개행해 준다 처..

리뷰 시작 문자열이 특정 조건을 가진 문자열을 더해 도착 문자열로 변할 수 있는지 여부를 체크하는 문제https://www.acmicpc.net/problem/12919 문제 풀이문자열 a와 b를 입력 받고, b의 크기에서 a크기를 뺀 값을 limit으로 저장한다. 이는 백트래킹의 기저조건이 될 값이다.변수 flag를 0으로 초기화 하고 함수 bt에 매개변수 0을 전달하여 백트래킹을 시작한다. 이때 0은 재귀 단계를 나타낸다.백트래킹의 기저조건은 flag가 1일때와 level이 limit에 도달했을 때다, 이는 둘의 문자열의 길이가 동일할때를 의미한다.문자열 a에서 b로 가는 재귀 말고, 문자열 b에서 a로 가는 재귀를 실행해 줄 것이다.만약 문자열 b의 앞이 B라면 문자열을 뒤집은 후 맨 뒤의 B를 삭..

리뷰 벽을 정확히 3개를 세워 학생들이 선생님의 눈을 피할 수 있게 하는 완전 탐색 문제https://www.acmicpc.net/problem/18428 문제 풀이전역 변수로 맵의 변의 크기 n, 정답 여부체크용 ans, 맵 lst, 방문 여부 v, 방향배열, 선생님 정보 T를 설정해 준다.input 함수를 통해 n값과 맵의 정보를 받는다, 이때 T가 입력된 경우 구조체 Pos타입 벡터 T에 추가해 준다.dfs 함수를 통해 완전 탐색을 돌려준다. 매개변수 level은 벽 설치 개수, row는 탐색을 재개할 행 정보다.벽의 개수가 3개가 되면 기저조건에 해당된다, bfs를 통해 시뮬레이션을 돌려준다.선생님을 순회하며 4방향으로 감시를 시작한다, 범위를 벗어나거나 벽을 만나기 전까지 해당 방향을 쭉 탐색한..

리뷰 문제 풀이전역변수로 테케의 수 tc와 지렁이의 수 n, 이동과 대기한 수를 나타낼 Move, Stay 정답 변수 ans를 설정한다.init 함수를 통해 ans를 최대한 큰 값, Move와 Stay를 0으로 초기화 해준다.input 함수를 통해 n값과 n개의 지렁이의 좌표를 Pos 구조체를 활용하여 pos배열에 저장해 준다.dfs 함수를 통해 각 지렁이가 짝을 지었을때의 좌표 벡터값을 구해줄 것이다.매개변수로는 지렁이 인덱스를 나타낼 level과 x좌표의 값 sumX, y좌표의 값 sumY를 전달해 준다.Move와 Stay가 각각 n / 2보다 작을 경우 Move와 Stay를 각각 증가시켜주고 재귀를 진행하면 된다.재귀를 전달할땐 level인덱스의 x, y좌표를 sumX, sumY에 더해주고 leve..

리뷰 큐를 사용하여 적절한 조건문과 BFS를 조합하여 풀었다.https://www.acmicpc.net/problem/2573 문제 풀이전역 변수로 n, m, ans = 0과 2차원 배열로 맵용 lst 및 섬 덩어리를 찾을 chk와 방향배열을 넣어주었다.좌표와 현재 값을 나타낼 Pos 구조체를 정의해 주고 Pos구조체 타입의 큐 q를 초기화 해주었다.input함수를 통해 n, m값을 입력 받고, 맵의 정보를 받아온다. 이때 빙산은 q에 저장해 준다.solution함수를 통해 시뮬레이션 및 전반적인 답을 도출해 낼 것이다.재귀를 통해 직관적으로 확인해도 되지만, 나는 그냥 while문을 통해 시간의 흐름을 나타냈다.time을 0으로 초기화 하고 while문을 항상 true로 실행한다.chk_island 함..