알고리즘공부(Algorithm Study)78 백준 1932 - 정수 삼각형 JAVA 해당 문제는 DP(다이나믹 프로그래밍) 문제다. 보자마자 대략 어떤 식으로 풀면되겠다라고 생각이 든 문제였다. (해당 문제 접근과정) 1. subset 느낌으로 dfs로 코드를 짜봄 2. 점화식을 도출해서 DP로 바꿔봄 3. Scanner를 써서 시간이 좀 오래걸리는 것을 보고 BufferedReader로 재구현 글 보다 코드를 보는 게 더 편한 우리는 개발자이므로 DFS 소스코드와 DP소스코드 작성해 보았습니다. 1. DFS로 코드를 짠 경우 package boj; import java.util.Scanner; public class Boj_1932 { static int dp[][], N, max; public static void main(String[] args) { Scanner sc = new.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 26. 백준 9251 - LCS JAVA 이 문제는 정말 난감했다. 엄청 간단해 보였는데 결국 구선생님의 도움을 받을 수밖에 없었다. 언제나 조져진 건 나였다...! 접근과정 1. 그냥 브루트포스로 다 확인하면 되지 않을까? 최대 2의 1000승(부분집합 경우의 수) x 1000(나온 결과와 상대 문자열 비교) 만큼의 무지성 곱이 나와버린다. 2. 맵과 리스트를 이용해서 그래도 dictionary화 해볼까? ->딱히 1번과 큰 차이가 없다 3. 답은 dp였다... 4. dp는 항상 손으로 직접 끄적여보면서 패턴(점화식)을 찾아야 한다는 걸 오늘 깨닫고 어제도 깨닫고... 5. 구선생님(구글)의 도움으로 어찌저찌 점화식도 구하고 했으나 결국 코딩까지 반이상 복붙하고 말았다. 문제 풇ㅇ 1. for문 ver import java.util.Array.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 24. 백준 1149 - RGB거리 JAVA 해당 문제 접근과정 1. 집이 3개인 경우로 일단 집 선택하는 경우의 수 나열 -> 실패 2. 각 집 방문할 경우에서 가장 작은 값 선택(그리디, dfs) -> 실패 (시간 터짐) 3. 2번에서 dp로다가 점화식인 f(특정 컬러를 선택하였을 때 N번 째 집의 도색 비용) = 특정 컬러로 N번 째 집의 도색 비용 + min(f(n번째 집에서 선택하지 않은 색을 선택하였을 때 N-1번 째 집의 도색 비용)) 도출 4. 구현에서 애먹음 5. 구선생님의 도움을 받음 아래와 같이 단계별 문제 풀기에서 DP를 풀며 느끼는 것은 점화식을 구하는 것도 구하는 것이지만 그걸 어떻게 구현하지? 가 더 큰 문제로 보인다. 내 머리의 공간지각 능력? 상상력을 키워야 할 때가 온 것 같다... package boj; impor.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 23. 백준 14247 나무자르기 - JAVA 해당 문제를 풀 때 다음과 같이 접근했다. 1. 매일 매일 산에 오를 때마다 가장 큰 것을 자르면 어떨까? -> 테케에 맞지 않는다. 2. 나무가 자라는 게 등차 수열이네 -> 그러면 공차의 오름차순 대로 나무를 잘라볼까? -> 테케 맞음 3. 그러면 오름차순 정렬할 때 Arrays.sort를 쓸까? 4. 어차피 계속 배열을 유지할 필욘 없으니 PriorityQueue를 써볼까? 라는 의식흐름에서 나온게 다음과 같은 코드이다. -> 하지만 함정이 숨어 있었다...흑흑 다름아닌 데이터 타입... 최악의 상황을 가정해 보았다. 나무 100,000개에 등차가 10,000이고 첫항이 전부 100,000 일 경우 99999*100000/2*10000 + 100000 = 49,999,500,100,000 => lo.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 21. 백준 1600 말이 되고픈 원숭이 - JAVA 이 문제를 푸는데 3시간이 걸렸다. 혼자 푼 건 아니고 로직은 맞는데 메모리 초과가 나서 구선생님의 도움을 받았다. 배열로는 메모리 초과가 뜨는데 Monkey 객체로 푸니까 문제가 풀렸다. 마치 int를 long으로 선언해서 맞은 기분이랄까? 6%에서 자꾸 시간 초과, 메모리 초과, 틀렸습니다가 떠가지고 너무 당황스러웠다. 문제 풀이의 핵심은 다음과 같다. 1. 최소한의 동작으로 목적지 도달 -> BFS(너비 우선 탐색) 2. 벽이 있는 곳은 가지 못함 3. 쓸모없는 탐색, 함수 호출 제거 4. 배열이 아닌 객체 선언 및 생성을 통한 메모리 초과 해결 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 20. 그래프(Graph), 그리고 DFS와 BFS - 1. 그래프에 관하여 DFS와 BFS는 탐색 알고리즘의 한 종류이다. 이 알고리즘은 그래프를 알고 있어야 이해할 수 있는 알고리즘이다. 그래서 그래프부터 다루고자 한다. 그래프란 점(정점)과 선(간선)으로 이루어진 자료구조를 의미한다. 별개 아니다. 그냥 숫자(인덱스)가 붙은 점들과 그 점들 간의 관계를 선으로 표시한 것 뿐이다. 단순한 점과 선들의 조합인 그래프를 활용해 마크주커버그가 페이스북을 만들었다. 이 페이스북을 사례로 그래프를 설명할 것이다. 자고로 본인은 페이스북 안한지 100만년된 듯 싶다. 각 점을 사람으로 간주하고 각 선을 팔로우하여 관계를 표시하면 그것이 그래프다. 눈치 챈 사람도 있겠지만 A가 B를 팔로우하였다. B가 A를 맞팔로우하였다와 같이 (간)선들은 일종의 방향성을 가질 수 있다. 이와 같은 방향.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2022. 2. 22. 이전 1 ··· 4 5 6 7 다음 728x90