본문 바로가기
반응형

알고리즘 PS113

[백준] 2206번 - 벽 부수고 이동하기 (Java)(△) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 최단거리 구하기 문제이므로 BFS 탐색을 사용하면 된다. 2. 벽을 한개까지 부술 수 있다. 탐색 시에 벽을 만나도 한번 더 나갈 수 있다는 뜻. 2-1. 최대 한개까지 1 -> 0으로 바꿀 수 있다. 2-2. 벽 공사 여부를 변수로 넣고 dist 배열을 dist[N][M][2]개로 만들어서 관리 2-3. 벽을 한번도 안 뚫은 경우는 dist[][][0]으로 거리 저.. 2022. 9. 20.
DFS 알고리즘(깊이 우선 탐색) 그래프 탐색은 어떤 정점을 찾거나 아니면 단순히 그래프를 순회하는 데 쓰인다. 어떤 그래프 탐색 이론이든 핵심은 지금까지 어떤 정점을 방문했는지 기록하는 것이다. 이렇게 하지 않으면 무한 사이클에 빠지고 만다. 사이클이 없는 트리에서는 발생하지 않지만, 그래프에서는 사이클이 있을 수 있으므로 이 문제를 해결해야 한다. 방문 배열을 사용하면 해결 할 수 있다. * 깊이 우선 탐색 알고리즘의 동작 1. 그래프 내 임의의 정점에서 시작한다. 2. 현재 정점을 방문 배열에 표시한다. 3. 현재 정점의 인접 정점을 순회한다. 4. 방문했던 인점 정점이면 무시한다. 5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 깊이 우선 탐색을 수행한다. * 코드 구현 void DFS(int v) { // 정점을 .. 2022. 9. 20.
메모이제이션을 통한 동적 프로그래밍 동적 프로그래밍(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.
반응형

티스토리툴바