본문 바로가기

Algorithm

백트래킹 코드 정리 정말 재귀함수를 이용한 탐색은 너무도 어려운 것 같다.이해는 해도 코드를 짜기가 정말 어려운 것 같아서 이번엔 백트래킹을 확실히 익히고자 포스팅을 진행하겠다. 백트래킹 : 탐색을 진행할 때 가지치기를 하는데, 단말노드까지 가기 전에, 확 꺾어버려서 다음 단말 노드로 이동하는 것. (진행하고 있던 방향이 틀어지는 것임) 이 말을 잘 기억해야한다. "진행하고 있던 방향이 틀어지는 것" 처음에는 단순히 "뒤로만 가면 되지 뭐.. " 라는 생각이었으나, 하나의 노드가 쭉쭉 내려오다가 중간에서 꺾이게 되면 이 전에 쭉쭉 내려오던 과정이 사라지기 때문에 , 단순히 뒤로만 가는 것이 아니라,한 과정 전체가 뒤로간다고 생각해야 한다. [코드] public class BackTracking_예제 { private sta.. 더보기
카카오 예비 코딩테스트 2번 2018년 8월 4일 카카오 코딩테스트 예선에 앞서서 예비 문제를 풀어보도록 하겠습니다. 이번에 풀어 볼 문제는 2번 단체사진 찍기 문제로 아래와 같습니다. 푸는 방식은 간단하면서도 살짝 어렵습니다.기본적으로 8명의 카카오 프렌즈 친구들을 나열하는 문제이기 때문에 순열 문제로 접근할 수 있습니다.예제 입력을 확인하자면 N~F=0은 N과 F가 나란히 (이웃하는) 서서 나열되는 경우입니다.또한 R~T>2라는 것은 R과 T가 3이상 떨어져 있다는 것입니다.이 두 조건을 만족하면서 8개의 알파벳을 나열하면 본 문제는 해결되는 것입니다. 따라서 알고리즘 회로를 생각해보면 아래와 같습니다. 1. 8개의 알파벳이 모두 나열될 때까지 Permutation 함수를 재귀로 돌립니다.2. 8개의 알파벳이 모두 나열되어 하나.. 더보기
BOJ_11066_파일합치기 파일 합치기 문제를 이번엔 풀어 볼 예정입니다.Bottom up 방식으로 풀어보려고 노력했으나 실력이 부족한 탓에..ㅠㅠ Top Down 방식으로 풀어보겠습니다. 문제는 다음과 같습니다. 파일을 겹쳐서 하나의 파일로 만들고 거기서 소비되는 비용을 계산하여 최소 값일 경우로 체크하는 문제 입니다. 이를 해결하기 위해서 점화식을 세우면 D[i][j]라고 할 경우,i 번째에서의 파일부터 j 번째 파일까지의 비용 계산 시 반환 되는 최소값이라고 할 수 있습니다. 점화식을 구체화시키기 위해서 아래와 같이 표현할 수 있습니다. 이렇게 k라는 변수를 두어서 i번째 파일부터 k번째 파일까지의 합 중 나오는 필요한 최소 비용 한 그룹과K+1번째 파일부터 j번째 파일까지의 합 중 나오는 필요 최소 비용의 다른 한 그룹과의.. 더보기
팰린드롬 만들기 앞서 팰린드롬 여부를 파악했던 DP문제를 풀었다면, 이번에는 팰린드롬을 만드는 알고리즘을구현해보겠습니다. 만약 입력한 내용이 이미 팰린드롬 형태라면 해당 입력된 문자열의 길이가출력될 것이며, 팰린드롬이 아닌 경우에는, 입력한 내용이 팰린드롬이 될 경우 얼마 만큼의 문자열의 길이가 정의되는지 출력될 것입니다. 코드는 상당히 짧기 때문에 먼저 전체 코드를 보여주고 설명하도록 하겠습니다. package algorithm; import java.util.Scanner; public class ThePalindrome { private static Scanner scanner;private static String s;public static void main(String[] args) {// TODO Auto-.. 더보기
BOJ_10942_팰린드롬? 이번 문제는 팰린드롬에 대해서 풀어보겠습니다. 팰린드롬은 데칼코마니 형태의 숫자나 문자를 나타내는 문제로 유형은 크게 입력된 내용이 팰린드롬인지 여부와 입력된 내용을 팰린드롬으로 만드는 방법 이렇게 두 가지입니다. 이번 포스팅에서는 팰린드롬인지 여부를 파악하는 방법으로 DP 방식을 활용하여 풀겠습니다. 푸는 방식은 Bottom-Up 방식을 사용해서 풀겠습니다. 사실 Top-Down 방식이 더 간단하고 쉽긴 하지만, 개인적으로 이번 문제는 Bottom-Up 방식이 더 어렵고Bottom-Up 방식을 안다면 Top-Down 도 쉽게 풀 수 있을 것이라 생각하여 결정하였습니다. 우선 점화식부터 세워보면 D[i][j]는 i부터 시작해서 j까지의 숫자 중 팰린드롬이 맞는지 여부를 파악한다고정의할 수 있습니다.점화식.. 더보기
BOJ_2294_동전2 이번에 풀어 볼 문제는 동전2 문제입니다. 문제부터 확인하겠습니다. 여기서 중요한 것은 다양한 종류의 동전으로 금액을 만들 때, 다양한 동전을 기준으로 금액을 만들어 내야 한다는 것입니다.동전을 기준으로 진행될 경우 발생할 수 있는 경우의 수가 중복되지 않는다는 점입니다. 가령 4라는 숫자를 1,2,3 이 세 가지 수로 만든다고 할 때,4를 기준으로 1,2,3을 만든다면 1+1+1+11+1+21+2+12+1+12+21+33+1 다음과 같이 총 7가지의 경우가 나오게 됩니다. 하지만 1,2,3 즉, 4를 만들어 내야할 요소들의 갯수(3가지)를 기준으로 4를 만들게 된다면, 1+1+1+11+1+21+32+2 다음과 같이 4가지 경우가 나오게 됩니다.방법에 대한 경우의 수가 중복되지 않아서 생기는 특징이라고 .. 더보기
BOJ_1로만들기_1463 이번 포스팅에서는 1로만들기 1463번 문제를 풀어보려 합니다. Dynamic Programming의 기본 문제라고 보시면 됩니다.문제는 아래와 같습니다. DP문제는 조건을 먼저 확인해야 합니다.이유는 조건에 따라서 점화식이 세워지기 때문입니다. 조건 1. 3으로 나누어 떨어지면 3으로 나눈다.2. 2로 나누어 떨어지면 2로 나눈다.3. 1을 뺀다. D[n] 은 n이라는 수에서 나올 수 있는 경우의 수라고 한다면,3으로 나누어 떨어지면 3으로 나눈다는 것은 n/3이 될 것이고2로 나누어 떨어지면 2로 나눈다는 것은 n/2가 될 것입니다.마찬가지로 1을 빼는 것은 n-1이 됩니다. 따라서 n이 3으로 나누어 떨어질 경우 D[n] = D[n/3] + 1 이 됩니다. (경우의 수)마찬가지로 n이 2로 나누어 .. 더보기
포도주 시식 BOJ_2156 앞서 포스팅에 이어서 2차원 DP 방식으로 여러 케이스를 나누어 푸는 방법을 소개하겠습니다.문제는 다음과 같습니다. 조건은 반드시 확인해서 코드로 정리해야하며 DP 문제는 점화식을 세워야 한다는 것을 잊어선 안됩니다. ※ 조건1. 포도주 잔 선택 후 마신 다음에는 제자리에 두기 --> 포도주 잔이 자리 위치가 없음 (고정됨)2. 포도주 잔 선택시 다 마셔야하며 연속 3잔 원샷 X ※ 점화식 D[n] : n번째 순서에서 포도주를 마시는 것 조건에 따라서 연속 3잔을 마실 수 없으므로 총 3가지 케이스가 나오게 됩니다. [0] --> 술을 마시지 않은 경우[1] --> 술을 연속 한 잔 마신 경우[2] --> 술을 연속 두 잔 마신 경우// 최대로 마실 수 있는 포도주의 양 체크 1. 연속 0잔 마실 경우D.. 더보기
반응형

티스토리툴바