알고리즘 저장소 (일반방식과 나만의 풀이)

[백준] no9465: 스티커

문제 int[2][N] 의 배열에 서로 다른 숫자가 주어진다. 1. 조건: 특정 칸의 숫자를 선택하면, 해당 칸의 상하좌우의 숫자는 선택할 수 없는 값이 된다. 2. 조건: 배열 안에서 합산이 가장 높게 나올 수 있는 숫자들을 선택해야한다. Input 테스트_케이스_수 T 배열의_길이 N 배열의_0번째_행에_들어갈_숫자들 배열의_1번째_행에_들어갈_숫자들 Output 합산 문제 링크 : https://www.acmicpc.net/problem/9465 원리 DP로 푸는 문제이며, 아래의 점화식을 이해해야 한다. 1. 점화식 : 문제에 주어진 행은 2줄로 고정되므로, 2줄에 대해서 각각 DP를 실행. : 이 때, 행렬의 [0][0], [1][0]에는 비교를 위해 각각 합산에 영향을 주지않을 0을 대입 후,..

[백준] no1043: 거짓말 - 그래프 탐색

문제 * 1. 총 인원 수 만큼 boolean형 배열을 만듦 (전부 false) * 2. 그 중 진실을아는사람은 true로 변경 * 3. 모든 파티를 돌면서, 해당 파티에 true인 인원이 있으면, 해당 파티의 모든 인원을 true로 변경 * 4. 모든 파티를 돌면서, 해당 파티에 true인 인원이 없으면, count++ * 5. count 출력 문제 링크 : https://www.acmicpc.net/problem/1043 원리 그래프 탐색 또는 DP 풀이방법 1. 필자의 경우 브루트포스(?) 방식으로 풀어보려했다. 2. Chat GPT는 전형적인 DP로 풀이했다. 3. 레퍼런스 코드의 경우 그래프 탐색을 이용했다. 나의 코드 [실패] 풀이 자체엔 문제가 없다. Chat GPT 상으로도 문제가 없는 코..

[백준] no11053: 가장 긴 증가하는 부분 수열 - 최장 증가 부분 수열 (LIS)

문제 * 수열 A의 길이와, A에 들어갈 숫자가 차례로 주어진다. * 원래 수열에서 순차적으로 증가만 하는 부분수열 중, 가장 긴 수열의 길이를 구하시오 문제 링크 : https://www.acmicpc.net/problem/11053 원리 최장 증가 부분 수열(LIS)로서, DP를 이용해 해결한다. 풀이방법 1. 나의 코드 : 모든 부분수열을 구해가며 그중 가장 긴 부분배열의 길이로 업데이트 2. Chat GPT : DP를 이용해 각 숫자별로 도달할 수 있는 최대 개수를 카운트 나의 코드 [실패코드] 원인 : 중간에 선택을 안하고 다음번 숫자를 선택했을 경우에 더 많은 숫자를 선택할 수 있는 방법을 구할수가 없다. 가령, 10 50 20 30 40일 경우, 10 20 30 40이 가장 긴 수열이지만, ..

[백준] no15666: N과 M (12) - 비내림차순 구하기(중복허용/visited 제거)

문제 * N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. * * N개의 자연수 중에서 M개를 고른 수열 * 같은 수를 여러 번 골라도 됨 = 중복허용 * 고른 수열은 비내림차순 = 선택된 수열은 오름차순인 경우만 허용 문제 링크 : https://www.acmicpc.net/problem/15666 원리 1. 재귀 (필자의 코드) 2. DFS (Chat GPT 코드) 풀이방법 코드 주석 참고 나의 코드 private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static BufferedWriter bw = new Buf..

[백준] no15663: N과 M (9) - (중복 미허용/visited 사용한 방법)

문제 * N개의 숫자 중 M개를 구하는 방법 * 단, N개의 숫자 중 중복이 있을 수 있고, * 같은 차례에 있는 숫자는 중복선택이 불가함 원리 1. 백트래킹 (DFS) 2. 재귀 풀이방법 재귀를 이용한 풀이 * 1. 입력받은 수들을 ArrayList에 담고, 오름차순 정렬 * 2. Combination(재귀 메소드)를 이용해 0번째부터 카운트하며 재귀 시작 * 3. 뽑아야 하는 개수 M이 되기 전까지 재귀를 통한 반복문을 진행 * 4. 중복을 제거하기위해 방문 체크를 시행(visited) -> 방문 후 재귀를 시행 * 5. 방문한 곳에대한 재귀로 해당 경우의 수를 모두 구한 뒤, 다시 방문을 해제하여 다른 경우에서 방문할 수 있도록 허용해줌 * 6. 모든 경우의 수를 구한 뒤, 같은 경우에 대해 중복 ..