전체 글347

• 

  백준 2579 - 계단 오르기 JAVA 해당 문제를 접근했을 때 머리가 굳어있어서 그런지 점화식을 찾고도 구현을 하지 못했다. 그래도 이 문제 덕에 DP에 좀 더 익숙해진 것 같다. 문제 접근 과정 1. 계단 갯수는 최대 300개, 점수는 10,000 이하 : 최대 3,000,000(연속으로 계단 올라간다는 조건 무시) -> int 선언 2. 한 번에 +1 or +2씩 계단 오를 수 있지만 연속된 세 계단 금지 3. 도착 계단은 반드시 밟기 4. 그렇다면 이미 목적 계단 가기 이전의 특정 계단을 밟는 순간 최댓값을 알 수 있지 않을까? 5. n번 째 계단까지의 max 합 = n번 째 계단의 점수 + max( (n-2번째까지의 max 합), (n-3번째 까지의 max + n-1번째 계단의 점수)) 6. 2번에서 연속된 세 계단을 오를 수 없다고.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 27.

• 

  백준 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.

• 2. 어제와 다른 오늘의 나 대학(大學)에는 구일신 일일신 우일신(苟日新 日日新 又日新), “실로 날마다 새로워지고, 날마다 새로워지되 또 날마다 새로워진다”라는 말이 있다. 중국의 은나라 탕왕은 세수 대야에 새겨 놓고 자아성찰하며 실천코자 하였다. 수십세기 회자되는 대단한 사람들도 하루하루 근기를 갖고 절실하게 사는데, 나라고 하루를 소홀히 대할 수 있겠는가. 아인슈타인 왈 "실수를 해보지 않은 사람은 한번도 새로운 일을 시도해보지 않았던 사람이다." 그리고, "어제와 똑같이 살면서 다른 미래를 기대하는 것은 정신병 초기 증세이다." 어제와 오늘이 달라진다는 것, 그리고 새로워진다는 것은 무엇일까. 단순히 의, 식, 주 등 물질적인 것이 아닌 생각과 행동이 달라져야 한다. 새로워져야 한다. 평소의 생활패턴을 분석하고 불필요한 패턴.. 끄적끄적(Memo)/끄적거림(scribble) 2022. 2. 22.

• 

  (JAVA/자바)compareTo와 Comparator 그리고 정렬 자바에서 primitive type(기본형) 중 OO.Compare이 있는 경우를 제외하고 객체 비교를 할 때 compareTo 또는 Comparator를 이용한다. 그중 Comparator의 경우 (특정 객체).sort(), Collections.sort함수 또는 Arrays.sort함수를 쓸 때 파라미터로 정렬기준(내림차순, 오름차순)으로 많이 활용하므로 "무조건" 익숙해지면 좋은 인터페이스이다. 1. Comparator에 관하여 Comparator 인터페이스의 경우 f3을 누르거나 ctrl + 마우스 좌클릭을 할 경우 아래와 같은 내용을 확인할 수 있다. 인터페이스이므로 결국 해당 compare함수를 재정의해서 쓰라는 뜻이다. 반드시 아래와 같이 Override 하여 사용하여야 한다. 안하면 컴파일.. 프로그래밍공부(Programming Study)/자바(JAVA) 2022. 2. 20.

• 

  (JAVA/자바) 생성자와 초기화 생성자란 객체 생성 과정에서 new라는 키워드를 통해 호출되는 함수이다. 클래스를 작성할 때 멤버변수를 선언하면서 동시에 변수 초기화를 하거나 생성자를 통해 초기화를 해야 한다. 클래스 내부에 명시적인 생성자가 없을 시 컴파일 시에 자동으로 default 생성자를 만들어준다. 하지만 default 생성자를 오버로딩한 다른 생성자가 존재할 경우에는 default 생성자를 자동으로 만들어 주지 않으므로, 오버로딩한 생성자와 함께 default 생성자를 표기해 주어야 한다. 생성자의 첫 번째 줄에서는 this와 super라는 키워드 둘 중 하나만 표기 가능하다. this는 static 영역에 있는 클래스(설계도)를 통해 heap 영역에 객체를 생성할 경우 해당 인스턴스의 주소를 갖고 있으며, 해당 인스턴스의 .. 프로그래밍공부(Programming Study)/자바(JAVA) 2022. 2. 20.

• 

  1. 간결한 코드 때로는 다른 사람의 코드를 보면 너무 짧아서 쉬워보이는 코드가 있다. 정작 코드를 여러번 읽어도 이해하기 힘든 그런 코드. 코드가 짧다는 것은 그 내용이 단순하다는 것이 아니다. 많은 시행착오와 생각들이 정제되어 나타난 것이기 때문이다. 코딩은 결국 컴퓨터 언어로 글을 짓는 것이다. 글을 쓸 때도 한 문장으로 줄이는 것이 힘들듯, 코딩도 글을 쓰는 것과 같이 힘들다고 생각한다. 생각하는 만큼 쓸 수 있고, 생각하는 만큼 행간을 읽을 수 있다. 간결한 코드를 짜기 위해 그들은 얼마나 많은 고뇌를 하고 시간과 노력을 쏟아부은 것일까. 앞서간 그들의 발자취 덕에 나는 양질의 글을, 소스를 읽을 수 있으니 나는 행운아다. 나는 행복하다. 글쓰기가 평생 취미였으면 하는 소망이 있는 나는 지금 컴퓨터 언어로 글을 .. 끄적끄적(Memo)/끄적거림(scribble) 2022. 2. 20.