코딩복습장

오늘은 dynamic programming문제를 풀고 리뷰하려고 한다. 리뷰 시작~! 문제는 매우 간단하게 설명이 되어있다. 문제를 푸는 방법은 여러가지가 있을 것 같지만 나는 백트레킹과 dfs를 조합하여 풀었다. local에서 푼 뒤에 leetcode를 적으려고 했는데, leetcode는 class형식으로 코드를 짜야해서 다시 코드를 변경하느라 고생했다.. (좀 더 문제를 잘 읽어야겠다. ) 문제를 푼 방식은 다음과 같다. 재귀형태의 dfs함수를 만든다. 여기에 현재까지 만들어진 괄호 문자열을 전달하는 인자, 문자열의 최대 길이, '(' 남은 수, ')' 남은 수 등을파라미터로 전달했다. curr_pt: 현재까지 만들어진 괄호 문자열을 전달하는 인자limit_len: 문자열의 최대 길이le..

깊이 우선 탐색(DFS)란 그래프나 트리를 탐색하는 기법 중 하나이다. 시작노드에서 자식의 노드를 순서대로 탐색하는데, 깊이를 우선하여 탐색한다. 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에 완전탐색 알고리즘에 속하지만보통 특정 조건을 만족할때까지 탐지하도록 만든다. DFS는 주로 반복문이나, 재귀문을 사용하여 구현한다. DFS의 탐색과정DFS의 기본 탐색과정은 특정 점에서 시작하여 역추척(backtracking)하기 전에 나눠지는 지점을 따라가능한 멀리 탐색하는 것이다. 1. 현재노드를 방문한 것으로 표시한다. 2. 방문한 표시가 되어있지 않는 각각의 인접한 지점을 탐색한다. 3. 더 이상 방문하지 않은 정점이 없다면 이전 정점으로 역추적(backtracking)한다. 4. 모든 정점을..

문제 링크: https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 55592 28081 20120 49.253% 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각..

문제 링크: https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 512 MB 27824 13029 8901 46.052% 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고..