코딩스타트

1. 그래프 다익스트라 - 네트워크 복구(백준 2211번)

2. 다익스트라 알고리즘을 이용한 문제풀이

다익스트라 알고리즘을 이용하여 최소 경로를 구하는 문제이다. 하지만 여기에서 최소경로만 구하는 것이 아니라 최소 경로에 해당하는 노드들의 연결까지 출력하는 문제이다.(최소 경로 값만 출력하면 쉬운문제이다. 앞에서 다루었던 최소경로,최소비용 문제를 참고하면 된다. 다익스트라 알고리즘 설명은 따로 하지 않는다.) 위의 코드는 조금은 비효율적인 코드라서 나중에 수정하기는 하겠지만, 이 코드를 설명하면 무한대 값으로 초기화되있는 노드들의 값을 최단 경로로 변경될때 마다 result라는 리스트 배열에 두 노드의 값을 넣어 준다. 하지만 값을 넣어주기 전에 이전에 같은 노드의 값이 들어와있는지 반복문을 통해 검사해 만약 이전에 이 노드 값이 들어오지 않았다면 그냥 result 리스트 배열에 값을 넣어주고 만약 이전에 같은 노드가 들어왔었다면 count--해주고 이전에 들어온 값을 제거한 후에 최단경로가 변경된 노드의 값을 리스트 배열에 넣어준다. 그리고 모든 알고리즘이 종료된 후에는 최단 경로에 해당하는 노드들의 연결이 배열 리스트에 저장이 되어 있게된다.

1. 다이나믹 프로그래밍 - 동전1 (백준 2293번)

2. 다이나믹 프로그래밍을 이용한 문제풀이

이 문제를 예를 들어 설명한다면, dp메소드에서 반복문에 들어가게 되면 우선 memo[0]=1 이라고 초기화를 한다. 이 것은 동전을 아무 것도 선택하지 않는 경우를 한 경우로 보고 1로 초기화하는 것이다.(확률에서 선택하지 않는 것도 하나를 1로 생각하는 것과 같다 보면된다.) 그리고 반복문을 들어가게 된다. 여기서 i=0 일때를 보면 j-coin[i]>=0 에서 j=1부터 성립을 하게 된다. 그래서 memo[1]=memo[1]+memo[0] 에서 memo[1]=1 이 되게 된다. 여기서는 coin[1]이 1이므로 k+1까지 모두 1가지 경우로 값이 대입되게 된다. 하지만 2,3 혹은 어느 값이 들어오더라도 그 값의 배수에만 경우의 수 1이 들어가게 된다. 예를 들어 coin[1]=2일때 j가 2부터 j-coin[i]>=0 이 성립하고 memo[j]=memo[j]+memo[j-coin[i]] 값은 2의 배수인 경우에만 1 값이 들어오게 된다. 여기서 보면 특이한 것이 coin[1]=2 이고 j=2면 memo[j-2=0] 의 경우를 더해주고 j=4 이면 memo[j-2=2]의 경우의 수를 더해주고 규칙이 보일 것이다. 그럼 문제의 조건으로 돌아와서 coin[2]일때를 보면 j=2 일경우부터 조건문이 성립하고 memo[2]=memo[2]+memo[2-2] 이 된다. 이 말은 1과 2를 이용해 2를 만드는 경우의 수는 1->2개(1을 2개이용) , 1->0 && 2->1(2를 1개이용) 두가지의 경우의 수가 나온다. 여기서 1->2는 i=0일때 1로 2를 만들수 있는 경우의 수(이전 경우의수,이값은 빨간색으로) 1->0 && 2->1은 1을 0개 선택하고 2를 하나 선택한 경우(파란색)이다. 이 경우의 수를 색으로 표현한다면 

memo[2]=memo[2]+memo[0] 이 된다. 여기서의 이해가 중요하다. 앞의 memo[2]는 현재의 동전이 아니라 이전의 동전으로 2를 만들수 있는 방법, memo[0]은 2라는 동전을 하나 선택해서 2라는 값을 만들었으므로 이전의 동전으로 0이라는 값을 만드는 경우의 수를 더하는 것이다. 그러면 더 나아가서 memo[6]=memo[6]+memo[4] 라는 값을 보자 앞의 memo[6]은 이전까지의 동전들로 6을 만드는 경우이다. 즉, 1 1 1 1 1 1, 그리고 나머지 경우를 보게되면 1 1 1 1 2, 1 1 2 2, 2 2 2 라는 경우가 남아있다. 여기서 맨위 2를 빼면 1 1 1 1, 1 1 2, 2 2라는 경우는 어느 경우인가? 2까지의 동전을 사용해 memo[4]를 만든 경우가 된다. 이런식으로 마지막 동전까지 반복을 하게 된다.

1. 문자열 처리 - 명령 프롬프트(백준 1032번)

2.문제 풀이

이 문제는 간단히 주어진 모든 문자열에서 같은 위치에 같은 문자를 갖는 다면 그 문자를 그대로, 만약 하나의 문자열이라도 그 위치의 문자가 다르다면 '?'를 출력하는 문제이다. 물론 위의 코드보다 더욱 효율적인 코드는 있겠지만 실행이 되는 코드이고 코드를 직관적으로 분석하기 편하다. 모든 문자열의 길이는 같으므로(문제풀기가 수월한 이유이다.) 첫번째 배열의 문자열을 기준으로 하여 그 외의 모든 문자열을 반복문으로 불러와서 각 위치의 문자가 같은지만 비교하면 된다. 만약 같다면 그 문자를 스트링에 넣고 만약 한 글자라도 다르다면 isSame에 false가 들어가 바로 반복문을 벗어나 str에 '?'를 넣게 된다. 이렇게 문자열의 길이만큼 반복문을 실행하면 되는 것이다.

1. 그래프 이론 - 섬의 개수 (백준 4963번)

2. 그래프 이론을 이용한 문제 풀이

문제의 풀이는 배열 안에 섬의 표시가 1로 표시가 되고 가로, 세로 및 대각선이 연결된 섬으로 인식이 되는 것이다. 1행부터 열을 탐색하여 1이 나오는 배열의 인덱스를 찾게 되면 그 배열의 좌표를 기준으로 countIsland 메소드를 호출하게 된다. 메소드 안에 좌표가 전달되면 전역 변수로 선언한 dx,dy 배열을 이용하여 연결된 섬을 찾게 된다. 좌표는 시작으로 부터 왼쪽, 왼쪽대각선위, 위, 오른쪽 대각선위, 오른쪽, 오른쪽 대각선 아래, 아래, 왼쪽대각선 아래를 뜻하게 된다. 그렇게 8방을 반복문으로 하나하나 따져봐서 인접한 1을 찾게 되는 것이다. 이 반복문 안에 첫번째 조건문이 뜻하는 바는 처음에 입력값으로 선언된 높이와 넓이의 직사각형을 벗어나는지를 따져보는 것이다. 만약 직사각형의 범위를 벗어나지 않으면서 팔방의 위치에 1이 존재한다면? 그 좌표를 방문했다는 표시로 모두 2로 배열의 값을 변경해준다.(그러면 더 이상 이섬은 탐색하지 않는다.)그리고 이섬은 연결된 섬으로 간주하고 그 섬의 좌표를 기준으로 countIsland 메소드를 다시 호출하게 된다. 즉, 그래프의 깊이우선 탐색을 실행하여 탐색하다가 더 이상 연결된 섬이 없을 때는 백트랙킹으로 이전의 좌표로 돌아가 이 좌표를 기준으로 다시 깊이 우선탐색을 실행하는 것이다. 그러다가 더 이상 탐색할 곳이 없게되면 함수를 종료하게 된다.(이 과정까지가 처음 발견된 1의 좌표를 기준으로 연결된 섬을 모두 탐색하고 난 후 종료하는 과정이다.) 

1.다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

2.다이나믹 프로그래밍 & 조합을 이용한 문제풀이

1)조합을 이용한 문제풀이

첫번째 풀이는 조합을 이용한 풀이입니다. 예제 입력에서 29개의 다리 중에서 13개의 다리를 겹치지 않고 놓을 경우의 수는 67863913개입니다. 겹치지 않는다? 단순히 그냥 29개의 다리중에 13개의 다리를 뽑는 경우의 수를 구하면 됩니다. 굳이 겹치는 경우를 고려하지 않아도 되는 것입니다. 13C29(13콤비네이션29) 의 값을 구해주는 로직만 짜주면 답은 쉽게 나오게 됩니다.

2)DP를 이용한 풀이

예를 들어 서쪽에는 3개의 사이트 동쪽에는 5개의 사이트가 있다고 가정한다면 bridge(3,5) 메소드를 호출하게 된다. 여기서 반복문이 뜻하는 바는 i==4부터 i==2까지 값을 감소시키며 bridge 함수를 호출시키는 것이다. 이것은? i==4라면 서쪽의 첫번째 사이트가 동쪽의 1번 사이트와 다리가 연결되어 남은 2개의 서쪽사이트와 4개의 동쪽사이트로 연결할 수 있는 다리의 경우를 구하면 되는 것이고, i==3이면 서쪽의 1번 사이트가 동쪽의 2번사이트와 연결되어 남은 2개의 서쪽사이트와 동쪽의 2번 밑의 3,4,5 3개의 사이트와 연결될 경우의 수를 구한다. 이렇게 쭉쭉가다가 서쪽과 동쪽의 남은 사이트 수가 같을 때까지 반복한다. 이런 것이 서쪽 사이트가 하나씩 줄어 가며 반복되는 것이다. 그리고 마지막 서쪽사이트가 함수에 들어 오게 된다면 초기화된 값을 바탕으로 memo[n][m]의 값을 구하게 되는 것이다. 

1.다이나믹 프로그래밍 - 계단 오르기 (백준 2579번)

2.다이나믹 프로그래밍을 이용한 풀이

이 문제 풀이의 핵심은 각 계단을 마지막 계단으로 보는 것입니다. 예를 들어 가장 마지막 계단을 오르는 경우의 수는 이전 계단을 밟는 경우와 전전계단을 밟는 경우 총 2가지입니다. 여기에서 이전 계단을 밟는 경우에서 upStair(n-3) 재귀호출까지 더해주는 이유는 3번 연속된 계단을 밟을 수 없기 때문입니다. 이 두가지 경우 중에서 큰수를 Math 클래스의 max 메소드를 이용해서 구합니다. 그래서 이 두가지의 경우로 재귀호출을 통해 다시 함수에 들어가게 되면 그 계단을 다시 마지막 계단으로 보고 다시 위의 두 가지 경우로 나뉘어서 재귀 호출을 반복하게 됩니다. 이 과정을 반복하다가 초기화된 값까지 다다르게 되면 모든 값이 메모된 값을 이용하여 총합을 구할 수 있게 됩니다. 여기에서 2번째 계단을 밟은 가장 큰 경우의 수는 1번째 계단을 밟는 경우이므로 stairArr[1]+stairArr[2] 를 통해 초기화를 해줍니다.

1. 다이나믹프로그래밍- 2xn타일링(백준 11726번)

2. 다이나믹프로그래밍을 이용한 풀이

다이나믹 프로그래밍으로 풀기 전에 이 문제의 점화식을 먼저 구해보면 간단히 n=2,n=3,n=4 만 비교해보면 n=2는 2가지 n=3일떄는 3가지 n=4 일때는 5가지라는 경우의 수가 나온다. 즉, 이 문제의 점화식은 2x4=2x3 + 2x2 라는 점화식이 나온다. ->memo[n]=( tiling(n-1)+tiling(n-2) )%10007 하지만 문제의 전제에서 값에 10007의 나머지 값을 구하므로 % 10007을 해준다.(마지막에 결과에만 하는 것이 아니라 모든 경우에 % 10007이 적용되어야 한다.) 여기서 n-2 라는 수가 있다는 것을 주목하면 2번째 전까지의 수의 배열을 확인한다. 즉, 0과 1 두가지의 수를 초기화 시켜놔야 한다. 그래야 tiling(2)를 호출할때 tiling(1)+tiling(0) 을 호출했을때 배열의 있는 값을 이용해 이후의 값을 구할 수 있다.

1. 다이나믹프로그래밍(dynamic programming) 초콜릿 자르기(백준 2163번)

2. 다이나믹프로그래밍을 이용한 문제풀이

이 문제의 예를 들면 초콜릿이 (1,N) 모양이라면 이 초콜릿을 자를 수 있는 최소한의 수는 N-1 이라는 경우의 수가 나온다. 즉, 1,N(1<=N<=300) 의 초콜릿의 자를 수 있는 최소한의 수를 초기값으로 memo 배열에 넣어준다. (다이나믹 프로그래밍은 큰 문제를 잘게 쪼개가다가 맨 마지막 가장 작은 문제의 값을 이용하여 인접한 배열에 수를 채워가 마지막 결과값을 구하는 것이다.) 만약 초콜릿이 (3,4) 라면 cutting(3,4) 라는 함수에 들어간다.(이전에 memo배열을 초기화해주는 함수를 실행시켜준다.) 그러면 이 함수는 memo[3][3]=cutting(2,3)+memo[1][3]+1 가 된다. 이 뜻은 (3,3) 초콜렛을 (2,3)과 (1,3) 으로 쪼개주는 것이다. 여기에서 (2,3) 과 (1,3) 을 쪼개는 경우의 수 1을 더해주는 것이다. 그다음 (2,3) 은 앞의 N값이 2 이므로 한번더 쪼개기 위해 재귀호출을 한다. 하지만 (1,3) 은 이미 위의 memo배열에 초기화를 시켜줬으므로 재귀호출이 아니라 바로 값을 리턴해주는 것이다.(초기화 값을 이용해 재귀호출을 하는 것이 아니라 바로 결과값을 구할수 있다. 그러므로 불필요한 계산을 중복으로 하지 않는다.) 이런식으로 N값이 1이 될때까지 재귀호출을 반복하면 결과적으로 memo(3,3)에 결과값이 들어가게 되고 그 값을 리턴하게 된다.