백준 바로가기 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택을 활용해 정해진 수열을 만드는 문제입니다. 바로 이해가 되지 않았던 문제인데, 숫자 n이 주어지면 1~n까지 숫자들을 오름차순으로 정렬된 스택에 저장하면서 push와 pop으로 주어진 수열을 반환해주면 됩니다. 저는 for문으로 접근했다가 중첩 시 조건에 맞추기가 어려워 못풀었습니다. 풀이를 보니 반복 조건을 넣을 수 있는 while문을 사용해야 되더군요. 또한..

백준 바로가기 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 거스름돈 최소 동전 개수로 구하는 문제를 이전에 풀어봤기 때문에 어렵진 않았다. 하지만 혼자 틀린 반례를 상상하느라 이상한 조건을 넣어줘 한 번 틀렸다. 주어지는 동전 가치는 i번째 동전이 i-1번째 동전의 배수이기 때문에 만일 target 동전 값이 700일 때 500과 300이 동시에 존재할 수는 없다. 만일 300이 있다면 500보다 300을 넣고 나머지를 1로 채워줘야 한다. 음..

백준 바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net DP 알고리즘 내 LIS(Longest Increasing Subsequence) 최장 증가 수열 문제입니다. 이해하는데 하루 꼬박걸렸으며 이해까지 도달하는데 효과적인 매체는 아래 유튜브 강의였습니다. 설명이 영어라도 그림만 봐도 이해되는 강의라 보심을 추천드립니다. 링크 출처: https://www.youtube.com/watch?v=CE2b_-XfVDk&list=LL&index=8&t=311s 풀이의 골자는 주어진 수열을 중첩 반복문으로 돌면서 각 index 값을 ..

백준 바로가기 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 알고리즘 이어서 푸는 중입니다. 문제 난이도는 solved.ac 기준 풀었던 것중 최상이었고 Gold5 였습니다. 난이도 체감은 알고리즘 개념보다 수학적 사고능력에 따라 높낮이가 결정되는 것 같습니다. DP를 알고있지만 위 문제는 어떻게 적용해야 할지 감이 오지 않았습니다. DP 알고리즘 문제의 특징인듯 합니다. 따라서 많이 풀어보고 다양한 형태의 문제를 접할수록 유리합니다. 제가 참고한 블로그 입..

백준 바로가기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 알고리즘 문제를 풀고 있는데요, DP로 안풀고 저만의 방식으로 풀다가 계속 틀리는 바람에 다른 분들 블로그 보고 DP 방식으로 풀었더니 됩니다. 두 가지 방법으로 풀 수 있는데 반복문 사용은 Bottom-up, 재귀 메서드를 이용한 방법은 Top-down으로 불립니다. 재귀의 경우 DP 배열을 써도 느리니 반복문 사용한 Bottom-up 방법을 추천합니다. 일단 두 가지 방법 모두 다루겠습니다. 문제 들어가기에 앞서 사고의 전환이 필요했습니다. 저는 주어진 N으로부터 3을 최대한 많이 사용해 1로 만드는 로직을 만든 다..

백준링크 : 바로가기 #수학 수학적 사고를 요구하는 문제들의 향연입니다. 스터디에서 [백준 문제 - 단계별로 풀어보기]를 순서대로 부수고 있는데 다다음주까지 수학과 재귀에 고통받을 것 같습니다. 벌집 문제의 난이도는 solved.at 기준 브론즈 2여서 수학적 규칙을 찾는 건 나름 괜찮습니다. 다만 로직으로 구현해내기가 생각보다 쉽지 않습니다. 외국에서 한국어로는 알겠는데 그 나라 말로 어떻게 표현해야 할지 모르는 상황과 유사합니다. 벌집 문제 규칙의 핵심은 벌집의 규모가 어떤 규칙을 가지고 커지는가 입니다. 저는 규칙을 찾을 때 손으로 종이에 쓰는 편입니다. 벌집이 커질 때마다 시작 숫자와 끝 숫자를 찾아 둘레의 크기(끝 숫자 - 시작 숫자 + 1)를 구하다보면 6의 배수로 증가함을 알 수 있습니다. ..