개발바닥

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 방법 다이나믹 프로그래밍으로 문제를 해결해야 된다. 범위가 1000이기 때문에 2중 포문을 통해서 가장 긴 값을 갱신해주면 된다. DP[현재 인덱스] = Date[기존인덱스] DP[현재인덱스] 인 경우에는 DP[현재 인덱스] 값을 갱신해준다..

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 방법 다이나믹 프로그래밍으로 문제를 해결해야 된다. 숫자를 하나 제거할 수 있기 때문에 제거 한경우와 안한경우로 나누어서 최대값을 갱신해야된다. DP [제거플래그][ 숫자인덱스] 제거 플래그가 0이면 한번도 제거를 안한 경우이고 1이면 한번 제거를 한 경우이다. DP[0][i] = max( 이전 제거안한 dp값에 + 현재 숫자, 현재 숫자) DP[1][i] = max( 이전 제거안한 ..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해결 방법 다이나믹 프로그래밍으로 문제를 해결해야 된다. 첫번째 물건부터 시작해서 현재 물건을 넣었을 때와 넣지 않았을 때 가치 중 큰 값을 갱신해주면 된다. 물건을 넣었을 때와 넣지 않았을 때를 어떤식으로 코드를 구현해야 될까요? 통과한 코드를 분석해보면 다음과 같다. for i in 물건개수 : for j in 1부터..

문제 https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 문제 해결 방법 DP를 활용해서 문제를 해결할 수 있다. 먼저 초기값으로 i번째 인덱스에는 A를 i번 누른 횟수로 초기화를 하고 버퍼에 있는 값을 복사하기 까지 총 3번에 커맨드 횟수가 필요하므로 컨트롤 v를 한번 두번 세번 누른 최대값을 비교 후 갱신해주면..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 방법 효율적으로 풀기 위해서는 DP 알고리즘 사용해야 된다. 2차원 배열 변수 DP를 선언 후 Bottom - up 방식으로 문제를 해결하면 된다. 시작과 끝에 해당되는 인덱스에 값이 같으면 안에가 팰린드롬인지 아닌지만 알고 있으면 된다. if( arr[시작] 과 arr[끝]이 같고 dp[시작+1][끝-1]이 팰린드롬이라면) DP[시작][끝] = 팰린드롬이다. 소스 코드 보기 https://github.com/joker..

문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 해결 방법 이동하면서 벽을 얼만큼 부수고 이동했는지 방문 변수를 통해서 확인을 한다. 방문 변수를 3차원으로 선언 후 visited[벽 부순 횟수][y좌표][x좌표] 를 이용해서 접근하고 bfs로 문제를 풀면 쉽게 해결할 수 있다. 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/BFS/..

문제 https://www.acmicpc.net/problem/2864 2864번: 5와 6의 차이 문제 상근이는 2863번에서 표를 너무 열심히 돌린 나머지 5와 6을 헷갈리기 시작했다. 상근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5� www.acmicpc.net 문제 해결 방법 내장함수 replace를 사용해서 최소값을 구할때는 6을 5로 최대값을 구할때는 5를 6으로 변경 후 더해서 출력하면 된다. 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_2864.py jokerKwu/BOJ_Algorithm Contribute to jokerKw..

문제 https://www.acmicpc.net/problem/12761 12761번: 돌다리 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대�� www.acmicpc.net 문제 해결 방법 bfs로 문제 해결 방법을 접근했습니다. 총 이동 가능한 경우 8가지를 현재 위치에서 다음 위치를 계산해서 범위를 벗어나지 않았고 처음 방문했다면 큐에 넣으면 된다. 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_12761.py jokerKwu/BOJ_Algorithm ..