다이나믹 프로그래밍은 시간 단축을 위한 알고리즘이다. 탑다운 방식과 바텀업 방식이 존재하며, 결국 핵심은 계산한 값을 저장하고 재활용한다는 것이다.동적 계획법(DP)를 구현해 보자. 탑다운: 메모이제이션▶ 이름에서 알 수 있듯 큰 문제부터 작은 문제로 해결하는 방식이다.장] 재귀구조가 직관적이고 구현이 간단하다.단] 재귀호출이 깊어질수록 스택 오버플로우 가능성이 있다.public class Fibonacci { static int[] dp; public static int fibonacci(int n) { if (n 바텀업: 터뷸레이션▶ 이름에서 알 수 있듯 작은 문제부터 큰 문제로 해결하는 방식이다.장] 스택 오버플로우 위험이 없으며 모든 값에 쉽게 접근할 수 있다.단] 반복문을..

모두들 안녕하신가요.  저는 어느덧 알고리즘을 건든 지 140일 지났답니다. 기쁜 소식이 있어 전해드리자면, 최근에 BFS 문제들을 풀며 골드 구간에 진입했어요. 목표는 골랜디 마스터고요. 이번에 문제를 풀며 스스로 아쉬웠던 부분들이 있어서 지금의 생각과 감정을 기록하려고 글을 적습니다.BFS인데 그래프가 2개?package bfs;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Problem10026 { static final int[] dx = {0, 0, -1, 1}; ..

개인 학습 목적 포스트입니다.GeeCon AngelikaLanger.com - Conference Video - GeeCon 2015 - The Performance Model of Streams in Java 8 - Angelika Langer - Angelika LaConference Video - GeeCon 2015 - The Performance Model of Streams in Java 8 - Angelika Langer   This presentation was recorded at the GeeCON 2015 conference in Kraków, Poland on May 13-15, 2015.  angelikalanger.com

문제수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.이해하기좌표 압축을 적용한 값 X'i가  Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같다. 중복되는 원소가 같은 순위를 가진다는 점이 마치 SQL Server에서의 DENSE_RANK 느낌인데, 이 문제에서 추가로 고려할 점은 값이 작을수록 순위가 높다는 것과 가장 높은 순위는 0순위라는 점이다. 중복되는 원소를 같은 순위로 둔다는 점을 고려할 때, 일단 Set이나 Map을 활용..

문제정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 큐에 들어있는 정수의 개수를 출력한다.empty: 큐가 비어있으면 1, 아니면 0을 출력한다.front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. BOJ에서 제공하는 큐 문제다. LinkedList와 ArrayDeque 모두 큐 자료구조를 구현할 ..

보호되어 있는 글입니다.

BufferedReader를 쓰면서 문자열을 숫자 값으로 전환하는 일이 많았다. 그래서 Integer.parseInt()가 자연히 몸에 배어있었는데, 이게 특정 진법으로 해석해 숫자 값을 뱉는 친구라는 건 오늘에서야 알았다. (지능 이슈) 변명이지만 지금까지 진법 자체를 다룰 일이 딱히 없었기도 하고, 아무튼 단순히 Int로 파싱 하는 거라 생각했는데, 아래와 같이 기수를 입력하면 해당 진법으로 해석해 값을 뱉어낸다.Integer.parseInt(Stirng, base)// 2진법Integer.parseInt("1010", 2); // -> 10 반환// 8진법Integer.parseInt("12", 8); // -> 10 반환// 16진법Integer.parseInt("A", 16); // -> 10 ..

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;public class Problem12789 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringTokenizer st = new ..

요즘 변수명을 의미 있게 작성하려고 노력하는 중이다. 물론 알고리즘을 풀 때는 편의상 내가 알 수 있을 정도로만 작명한다. 동시에 메서드는 최대한 빼서 구현하는 편인데, 특별한 이유는 없고 메서드를 만드는 것에 익숙해지고 싶어서다.창문 닫기 문제는 9단계에 위치했지만 앞선 단계들보다 쉽다. 그래서 크게 생각할 점 없이 코드를 짤 수 있었다.// https://www.acmicpc.net/problem/13909import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Problem13909 { public static void main(String[] args) throws ..

백엔드 개발자를 희망한다면서 지금까지 잘못된 방법으로 공부하고 있었던 것 같다. 알고리즘이나 조금 건드리고, 인프런 강의를 챙겨 들으며 문법을 배우는 것만으로도 충분히 잘하고 있다고 생각했다.  현실은 JONNA 부족하다. 한 블록에 모든 내용을 담다가, 메서드로 분리하는 것을 적용해 보기까지도 엄청 오랜 기간이 걸렸다. 일부러 메서드로 빼는 연습을 계속하고 있다만 솔직히 지금도 잘 모르겠고 어렵다.  자바의 메모리 영역이라던가 객체 지향이라던가, 아무튼 자세히 파고들면 머리 아픈 개념들이 참 많은데, 지금 당장 필요한 건 디자인 패턴이다. 진작에 스프링까지 공부했으면 조금 더 나았을까 싶기도 한데, 이제 와서 어쩌겠나. 나는 지금까지 패키지 구조조차 명확하게 나누고 시작한 적이 없었다. 그런데 최근 느..