본문 바로가기
반응형

전체 글147

메모이제이션을 통한 동적 프로그래밍 동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다. 메모이제이션(memoization)은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다. 본질적으로 메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다. * 메모이제이션 구현 int fib(int n, int[] memo) { if (n == 0 || n == 1) return n; // memo 테이블을 확인해 fib(n)이 이미 계산된 건지 본다. if (memo[n] == 0) { // 값이 없으면 재귀호출 실행 memo[n] = fib(n-2, memo) + fib(n-1, memo); } return memo[n]; // 이미 계산된 값이 .. 2022. 9. 20.
재귀함수 - 재귀적으로 작성하는 법 1. 재귀 카테고리 : 반복 실행 - 반복적으로 한 작업을 실행하는 알고리즘이다. - 파라미터를 전달해 반복 계산한다. - 재귀에는 항상 종료 조건이 있어야 한다.(!) - 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임한다. 2. 재귀 카테고리 : 계산 - 하위 문제의 계산 결과에 기반해 계산할 수 있다. - 하위 문제는 입력값을 더 작게 한 똑같은 문제이다. - Factorial 함수가 대표적이다. - 계산 방식은 "상향식"과 "하향식"이 있는데, 상향식은 루프와 재귀의 방식이 같다. - 하향식이야 말로 재귀를 사용하는 주된 이유이다. 3. 하향식 재귀 : 새로운 사고방식 3-1. 하향식 사고 절차 a. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자. b. 문제의 하위 .. 2022. 9. 19.
[백준] 1436 - 영화감독 숌 (Java) https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 1. 부르트포스 알고리즘을 이용해서 한자리씩 수를 증가시키면서 "666"이 포함되었으면 count++한다. 2. if (count == N)이면 그 때의 수를 리턴한다. 3. 문자열 체크는 정수를 String으로 바꾼다면 contains(문자)로 검색하면 된다. import java.util.*; import java.io.*; /* [백준] 1436 - 영화감독 숌 (Java) */ publi.. 2022. 9. 19.
[백준] 10872번 - 팩토리얼 (Java) https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼은 그 수 보다 작은 모든 정수의 곱이다. 5! = 5 x 4 x 3 x 2 x1이다. 즉, n! = n x (n-1)!과 동일하다. 이를 재귀함수로 구성하자. import java.util.*; import java.io.*; /* [백준] 10872번 - 팩토리얼 (Java) */ public class Main { static int N; void InputData() { Scanner in = new Scanner(System.in); N = in.nextInt(); } // 재귀함수로.. 2022. 9. 19.
코딩테스트 대비를 위한 백준 문제 추천 (코딩테스트 준비 관련해서 좋은 글이 있어서 출처를 남기고 퍼왔습니다.) 준비운동 PART1. 튼튼한 기본기 알고리즘 공부를 시작하면 만나게되는 약수, N진수, GCD, LCM, 소수 등의 문제는 변형하여 출제 혹은 어려운 문제를 풀이의 중간 단계에 들어가기도 합니다. 화이트보드 면접을 준비한다면 다양한 정렬 주제와 함께 준비해야할 1순위이기도 합니다. 파이썬으로 코테를 준비하는 분들이라면 내장함수를 사용하지말고 직접 구현해보세요. 약수 구하기 (🥉 브론즈 3티어) 이진수 (🥉 브론즈 3티어) 최소, 최대 (🥉 브론즈 3티어) 지능형 기차 2 (🥉 브론즈 3티어) 피보나치 수 5 (🥉 브론즈 2티어) 일곱 난쟁이 (🥉 브론즈 2티어) 최대공약수와 최소공배수 (🥈실버 5티어) N번째 큰 수 (🥈실버 5티어.. 2022. 9. 19.
문자열 입력 처리 방법 1. 문자열에서 (-) 기호를 기준으로 분리하고, 그 토큰은 (+)를 기준으로 다시 분리할 때 a. 입력받은 문자열은 - 기준으로 분리한다. b. 자른 토큰들을 + 기준으로 다시 분리한다. c. 자른 토큰들을 정구형으로 캐스팅해서 합친다. str = in.next(); String[] sub = str.split("-"); // -로 문자열을 자른다. for (int i=0; i 2022. 9. 19.
[백준] 1541번 - 잃어버린 괄호 (Java) 1. 첫번째 수는 무조건 양수가 온다고 했으니 그 수에서 뺀값이 가장 작으려면 뒤에 -가 붙는 수가 가장 큰수여야 한다. 2. - 기호가 나오면 그 뒤로 나오는 수들을 모두 더해서 음수로 된 최대값을 만들어야 한다. 3. - 기호가 나오기 전까지의 숫자는 계속 더해주다가 - 기호가 나오면 거기서 괄호를 쳐서 모두 더해서 빼면 된다. ex) 55-50+40 = 55 - (50 + 40) = 55 - 90 = -35 10+55-50+40 = 10+55 - (50+40) = 65 - 90 = -25 1. 3개의 구현이 필요하다. 1-1. 입력 받은 문자열을 -를 기준으로 잘라서 문자열 배열에 담는 작업 1-2. 자른 문자열을 +를 기준으로 수를 뽑아내어서 더하는 작업 1-3. 각 취합된 수를 빼는 작업 2. .. 2022. 9. 19.
온라인 코딩 테스트의 사전준비 1. 연습장과 필기 도구 재귀 구조를 구현할 때 머릿속으로만 구조를 그려내면 실수하기가 쉽다. 처음부터 연습장에 값의 변화나 최종 결과를 기록하고 머릿속에 떠올린 구조와 비교하면서 풀이해나가자. 2. 자신만의 코드 스니펫 준비 코딩테스트 시 자주 쓰이는 동작들에 대해 코드 스니펫을 미리 만들어 두면 도움이 된다. 예를 들어 연결리스트를 뒤집거나 삭제하는 등의 작업들은 갑자기 구현하려면 헷갈리기도 하고 시간이 걸리는데, 이런 작업에 대한 코드를 미리 만들어두면 좋다. 3. 모든 테스트 케이스를 통과하도록 풀어야 코딩 테스트 시에는 충분히 생각하고 문제가 없는지 코드를 다시 한번 더 꼼꼼히 확인 후에 제출하는 편이 유리하다. 실무에서처럼 일단 돌아가는 코드를 제출하고 테스트를 지속적으로 돌려보면서 오류를 수.. 2022. 9. 17.
[백준] 1753번 - 최단경로 (Java) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 다익스트라 알고리즘을 사용 2. 정점은 인접행렬로 구성하고, 방향이 있는 그래프이니 s -> e만 배열에 저장할 것. import java.util.*; /* [백준] 1753번 - 최단경로 (Java) */ public class Main { static int V, E, K; static int[][] map; static int[] visited; .. 2022. 9. 14.
반응형

티스토리툴바