본문 바로가기
백준 #1463. 1로 만들기 몇 번의 시도 끝에 성공했다.ㅠㅠ 다이나믹 프로그래밍 방법으로 풀었는데, 혼자 이런저런 패턴을 연구해서 적용해도 "틀렸습니다."가 떴다. 마음을 비우고 문제에서 원하는 조건 그대로 코드를 작성했더니 맞았다. 기본적으로 result[i]의 값은 result[i-1] + 1이다. 1을 뺀다는 조건이 있으므로 이전 result[i]의 값에서 1을 더하면 된다. 단, 이건 result[i]가 가지는 최댓값이 된다. 그래서 3으로 나눠 떨어지는 경우, 2로 나눠 떨어지는 경우는 result[i-1] + 1과 각각 result[i/3] + 1, result[i/2] + 1을 비교해 더 작은 값으로 설정한다. 다음은 소스코드이다. #include #include using namespace std; int main(..
백준 #1904. 01타일 00과 1의 조합으로 특정 숫자를 만들 수 있는 가짓수를 묻고 있다. 이런 문제는 세부적인 데이터에 집중하기보다, 패턴을 찾으면 쉽게 풀 수 있다. n 결과 1 1 2 2 3 3 4 5 5 8 보면, 피보나치 수열의 형태를 띄고 있다. 따라서, 입력된 n까지의 결과를 구한 다음, 문제에서 요구하는 대로 15746으로 나눠 주면 된다. 재귀적으로 풀면 n이 커졌을 때 연산량이 급속도로 증가하기 때문에, 배열(arr)에 구해둔 값을 저장해서 가져다 쓰는 Dynamic Programming 방식을 택했다. 다음은 소스코드이다. #include using namespace std; int main() { int n; cin >> n; int* arr = new int[n + 1] {0, 1, 2, }; //sa..
백준 #7576. 토마토 BFS를 이용해 풀 수 있는 문제이다! 입력받을 때, 토마토가 있는 위치를 큐에 넣어주고, 큐를 pop하면서 큐가 빌 때까지 큐의 원소를 하나씩 검사한다. BFS를 수행하는 인덱스 y, x를 인자로 넣어주고, box[y][x]의 상, 하, 좌, 우를 탐색한다. 영향을 미칠 수 있는 토마토가 있으면, 현재(box[y][x])의 숫자보다 1만큼 큰 숫자를 넣어준다. 이렇게 하면 날짜 변수를 따로 만들지 않아도, 함께 셀 수 있다! 주의할 점은, 농장의 사이즈 m, n이 들어올 때 가로줄 개수 -> 세로줄 개수 순서로 들어온다. 보통 2 3이 차례로 입력되면, (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) 이렇게 세로줄 먼저 입력되는 것이 일반적인데, 이 문제는 반대이다. 나는 기존 방식이 ..
백준 #1057. 토너먼트 김지민과 임한수가 몇 번째 라운드에서 만날지 카운팅하는 문제이다. 한 번 라운드가 진행될 때마다 참가자 수가 반으로 줄어드니 그에 따라 n, kim, lim 변수를 반으로 줄여준다. (홀수일 경우는 +1한 뒤, 반으로 나눔.) 그리고 토너먼트는 1과 2, 3과 4 등 바로 옆 인덱스끼리, 그리고 (홀수, 짝수) 이렇게 진행된다. 부전승일 경우도 마찬가지로, 바로 전 인덱스가 홀수일 때, 그 인덱스와 짝꿍이 될 경우에 경기를 치를 수 있다. 따라서, kim과 lim 중 더 작은 수(minIndex)가 홀수일 때, 그리고 서로 바로 옆의 수가 될 때까지 round를 1씩 증가시키며 loop을 돌린다. 조건에 일치하는 경우, break를 하고 바로 round를 출력해준다. 다음은 소스코드이다. #include..
백준 #1260. DFS와 BFS DFS는 재귀로, BFS는 큐로 풀어보았다. 우선 문제에서 방문 가능한 노드가 여러 개일 경우, 숫자가 작은 노드부터 방문하라고 했으므로 linked 안의 연결 정보를 sorting해줄 필요가 있다. linked[i][j]에서 j부분을 sorting해주면 되므로, sort의 시작 주소를 linked[i].begin(), 끝 주소를 linked[i].end()로 설정한다. DFS : 호출된 노드 x를 방문 처리(visited)하고, 출력한다. x의 인접 노드 중 아직 방문되지 않은 것이 있다면 해당 노드에 대해 DFS()를 호출해준다. BFS : 호출된 노드 x를 큐에 넣고, 방문 처리(visited) 후 출력한다. 큐가 빌 때 까지 x의 인접 노드 중 아직 방문되지 않은 노드를 큐에 넣고, 방문 처리 후..
백준 #2667. 단지 번호 붙이기 모든 집을 다 탐색해봐야 하므로 완전 탐색이라고 할 수 있다. DFS를 활용해 완전 탐색을 해 보았다. stack에 탐색한 집(x, y 좌표)을 넣고, 방문을 완료했으므로 visited[x][y]를 true로 바꿔준다. (방문 처리) 현재 있는 집부터 상하좌우를 탐색하며 집이 있으면 1을 추가하고, 방문 처리한 다음, 단지(group)에 속하는 집의 수를 1씩 증가해준다. 이것을 stack이 빌 때까지 반복한다. 주의할 점은 상하좌우로만 방문을 해야 한다는 것이다. newX와 newY의 범위를 x-1
백준 #1966. 프린터 큐 큐와 우선순위 큐를 이용해 풀 수 있다. 문제에서 요구하는 index의 출력 순서를 찾아야 하므로, queue에 {문서의 우선순위 값, index} 이렇게 값을 추가해준다. 그리고 priority_queue에는 문서의 우선순위 값만 따로 넣어준다. 그래서 queue의 front().first (현재 큐의 제일 앞에 있는 문서 우선순위 값) 과 priority_queue.top (현재 가장 우선순위가 높은 문서) 를 비교해서 같으면 출력, 아니면 pop 한 뒤 다시 push해주는 형태로 문제를 풀면 된다. #include #include using namespace std; int main() { int testcase; //number of testcase cin >> testcase; int *answ..
백준 #9012. 괄호 '('와 ')'가 한 쌍을 이루는 VPS(Valid Parenthesis String)이고, 그 쌍들로만 이루어진 test case에 YES를 출력하는 문제이다. 입력받은 문자열을 stack에 넣어주고, stack의 top부터 체크한다. 그러므로 입력받은 순서가 아닌 거꾸로 체크하게 된다. 따라서 VPS가 되려면 ')'의 개수를 세는 right 변수는 항상 0 이상을 유지해야 한다. 이 문제에서 NO가 출력될 경우는 다음과 같다. 1. 입력된 test case가 홀수 개수일 때 (stack에 문자열을 넣을 필요 없이, 바로 문자열의 size를 체크한다. 문자열 길이가 홀수이면, continue를 통해 다음 test case로 넘어간다.) 2. right 변수가 음수일 때 (거꾸로 체크하므로, ( ) ) ..

티스토리툴바