본문 바로가기

전체 글236

[백준 *Java] - 2*n 타일링 (11726) 이번 문제는 2*n 타일링 백준 문제입니다. 역시나 DP 문제에 익숙하지 않아 문제를 이해하는데 오래걸렸습니다. 역시 DP 문제는 문제와 테스트케이스를 꼼꼼히 읽으며 하나씩 그려보거나? 쓰면서 하는 게 이해가 잘되는 거 같습니다. DP 에 대해서 잘 모르신다면? 아래 링크를 타고가서 블로그 글을 읽고 오시면 좋을 거 같습니다 😊 다이나믹 프로그래밍 점화식 👆 위 그림과 같이 그려보면, 갯수가 피보나치 수열로 증가하는 게 보입니다. 피보나치 수열은 1, 1, 2, 3, 5, 8 이런 식으로 증가합니다. 그런데 지금 보이는 수는 1 2 3 5 8 로 증가를 하니 인덱스를 맞춰서 코드를 구현하면 됩니다. 아래 코드는 주석을 달아 코드 설명을 해놓았습니다. 👇 Top-down 방식으로 구현하였고, 주석에는 Bo.. 2022. 3. 18.
[백준 *Java] - 1로만들기(1463) DP 문제를 처음 접했을 때 풀었던 문제입니다. 일단 DP에 대해서 잘 모르신다면, 아래 링크를 타고 가서 한 번 읽고 오셔도 좋을 거 같습니다. 다이나믹 프로그래밍 점화식 1로 만들기 문제는 Top-down, Bottom-up, dfs 방식으로 각기 다르게 문제를 풀어보았습니다. 아래코드 기준으로 메모리,시간 효율이 좋은 순서는 dfs > Bottom-up > Top-down 입니다. 하지만 dfs 와 Bottom-up은 큰 차이는 보이지 않았습니다. 각 코드마다 주석으로 코드 설명을 해놓았습니다. 혹시 코드개선할 점과, 모르는 부분이 있으시면 댓글 남겨주시면 감사합니다 : ) DP 문제는 종이와 펜을 가지고 일일이 확인을 해보면서 점화식을 찾으며 문제를 풀고 그 능력을 키우면 실력에 도움이 많이 될거.. 2022. 3. 18.
[백준 *Java] - 스택(9012) / 단어뒤집기(9093) / 괄호(10828) 스택 백준 10828 ⬇ [접근방식] Stack API 를 사용하기보단, 직접 구현을 해서 문제를 풀었습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; // 스택 10828문제 public class Boj_10828 { private int max; private int ptr; private int [] stk; public Boj_10828(int capacity) { ptr = 0; max = capacity; stk = new int[max]; } public void push (int input) { stk[p.. 2022. 3. 16.
점화식 이란? 알고리즘을 공부하다가 점화식이라는 키워드가 나와서 알아본 정보입니다. 점화식이란 ? 수열의 각 항 간에 관계를 (단순 나열이 아닌 규칙으로) 표현한 관계식을 의미합니다. 좀 더 쉽게 이야기하면? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것입니다. 다시 말해 재귀함수의 구조를 갖는 알고리즘만 점화식으로 표현할 수 있습니다. - 수열의 N 번째 항(일반항) 을, - 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식을 말합니다. 어떤 점화식 표현이있을까 ? 점화식 특징은 ? 등식 또는 관계식 형태를 갖고있습니다. (단, 문제 제시 때는 초기값 또는 경계값이 반드시 필요합니다) 점화식 자체는, 간접적이고 부분적인 정보만 주어, 따라서 일반항을 구할 필요 있습니다. 점화식의 점근.. 2022. 3. 16.
다이나믹 프로그래밍(Dynamic Programming) 이란? 동적계획법 (Dynamic Programming) 이란? 최적화 문제를 위해 고안된 기법으로 복잡한 문제보다 간단한 여러 개의 부분 문제로 나누어 해결합니다. 중요한 점은 한 번 계산된 부분 문제의 답을 저장해 두어 나중에 같은 부분 문제의 답을 원할 시, 반복되는 연산 없이 바로 저장해 둔 걸 꺼내 쓸 수 있도록 하는 것이 핵심입니다. 주로 중복되는 부분 문제(Overlapping Subproblem)와 최적 부분 구조 (Optimal Substructure)를 가지고 문제들을 풀 때 사용됩니다. 또한, 동적 계획법을 설계할 때는 가장 중요한 것이 현재 문제의 상태와 문제와 부분 문제 간의 관계 또는 전이를 파악하는 것입니다. 문제들 간의 관계 또는 전이를 정확하게 파악한다면 알고리즘의 정당성을 얻을 .. 2022. 3. 16.
정렬 알고리즘 비교 In-Place ? 입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. Stable ? Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 버블 정렬 선택 정렬 삽입 정렬 셸 정렬 합병 정렬 퀵 정렬 힙 정렬 2022. 3. 13.

티스토리툴바