[백준,BOJ 2446] 별 찍기-9( JAVA 구현)

-해법 별 찍기 문제-9이다. 솔직히 별 찍기 문제는 무언가 특별한 기술이 필요한 것이 아니라, 예제 출력의 모양을 본 후 규칙성을 찾아 구현해야 하는 것 같다. 이번 문제의 경우에는 눈에 딱 봐도 앞 뒤로 한 개씩 빈칸이 증가하는 것을 알 수 있다. 1번째 줄에서 앞 뒤로 0개의 빈칸, 2번째 줄에서 앞 뒤로 1개의 빈칸.... 식으로 가는 규칙성을 찾았으면 이제 이를 토대로 구현해보면 된다. 필자는 보통 중앙을 포함해 윗부분을 구현하고 아랫부분을 별도로 구현한다. //윗부분 구현 for(int i=0;i

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2440] 별 찍기-3(JAVA 구현)

-내 생각 정보처리기사를 준비하면서 많이 봤던 별 찍기 문제였다. 2차원 배열을 구현해도 되지만, 메모리 낭비이므로 그냥 출력하는 방식으로 구현하려 했다. 문제의 특징으로는 예제 출력에서 볼 수 있듯이, 각 행마다 N-행의 값의 개수만큼 별을 찍는다. 예를들어 N이 5일 경우, 첫 번째 행은 0번 부터 시작하여, 5-0번 열을 반복한다. 행이 1일 경우는 5-1인 열을 4번만큼 반복한다... 이런식으로 구현해도 되고 반대로 행을 5부터 시작하여 행은 감소시키고 열은 행까지 반복하는 등 여러가지 구현 방법이 가능하다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(..

→2019.11.29

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1924] 2007년(JAVA 구현)

-내 생각 특정 일수가 주어지고 해당 일자의 요일을 구하는 문제이다. 이런 유형의 문제는 처음 풀어봐서 어떻게 풀어야 할지 감을 잡지 못했는데, 잘 생각해보면 1주일이 지날 때마다 7씩 증가하므로, 1/1이 월요이라면, 8일도 월요일, 15일도 월요일.... 식으로 가게 된다. 그러므로 특정 일자 % 7로 어느 요일에 속하는지 알 수 있게 된다. 그렇다면 특정 월과 일이 총 며칠인지 어떻게 구해야 할지 고민해보았는데, 생각해보면 간단하다. 예를 들어 3월 6일이라고 가정한다면 1월과 2월의 총일수를 6일과 더해주면 된다. 각 월의 총일수는 문제에서 주어지므로 구현이 가능해진다. -해법 import java.util.*; public class Main { static int month_Day[] = {0..

→2019.11.29

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11729] 하노이 탑 이동 순서(JAVA 구현)

-내 생각 하노이 탑의 경우 개념은 알겠는데, 재귀 호출의 늪에 빠져버려서 도저히 머릿속으로 상상이 어렵다.. 그래서 그냥 공식처럼 외우기로 했다.. -해법 하노이 탑을 해결하기 위해서 1번 타워에서 3번 타워로 옮기는 것이 기본으로 수행 알고리즘은, n-1개의 원판을 1->3->2 순으로 타워 롤 옮기고, 2->1->3 순으로 3번에 다시 쌓으면 된다고 한다. 그렇기 때문에 재귀 호출을 통해 인자만 변경하면서 전달해주면 된다. import java.util.*; public class Main { static int n,cnt=0; static StringBuilder sb = new StringBuilder(); static void hanoi(int n,int from,int by,int to) {..

→2019.11.29

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2565] 전깃줄(JAVA 구현)

-내 생각 이 문제를 풀다가 약간 소름이 돋았다. 이전에 비슷한 문제를 풀었었던 것 같은데(블로그에 글은 올리지 않았다.) 그 당시에는 이러한 문제를 풀 때 2번부터 기준으로 할 때 1번이 가지는 값은 2번이 가지는 값보다 작은 경우만 카운트해서 풀었던 것 같은데, 그것이 LIS를 학습하고 나서 LIS인 줄 알 수 있었다.. 최대한 LIS로 풀어보기 위해 글을 검색해 보았는데 정확한 풀이법을 알 수 있었다. -해법 우선 A 또는 B 전봇대를 기준으로 오름차순 정렬을 수행한다. 이후 i번을 기준으로 i번 보다 작은 경우 값이 i번 보다 작게 가져야 한다. 즉 전깃줄을 제거하는 것이 아닌, 설치하는 개념으로 생각해보면, 2-2 일 때 1-8이므로 2

→2019.11.28

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11722] 가장 긴 감소하는 부분 수열(JAVA 구현)

-내 생각 이전 글에서 작성했던 가장 긴 증가하는 부분 수열 문제와 동일한 문제라고 생각했다. 원래 이 문제는 단계별 풀어보기 동적 계획법 1에 존재하지 않는 문제인데, 풀게 된 계기는 11054번 문제인 가장 긴 바이 토닉 부분 수열 문제를 해결하기 위해서 먼저 풀어보면 좋다고 하여 풀어보게 되었다. -해법 이 문제는 가장 긴 증가하는 부분 수열 문제와 알고리즘은 완전히 동일하며 반복문 부분만 수정해주면 된다. 즉 시작 인덱스를 1이 아닌, n부터 시작하면 되는 것이다. 자세한 것은 코드를 보자. import java.util.*; public class Main { static int n; static int dp[], cost[]; public static void main(String[] args..

→2019.11.28

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10844] 쉬운 계단 (JAVA 구현)

-내 생각 문제 이름은 쉬운 계단 수있은데 쉽지가 않다 ㅋㅋㅋㅋㅋㅋ 당연히 못 풀었고 다른 분들의 글을 참고했다. -해법 이 문제의 경우 dp[N][10]의 2차원 배열을 사용해야 한다. N은 숫자의 자릿수를 의미하며 10은 0~9의 끝자리를 의미한다. 다른 분들의 경우 0~9를 끝자리로 두지 않고 푼 경우도 봤는데, 끝자리로 두고 푼 분들이 더 많았다. 우선 초기 dp배열은 N이 1일 경우이다. 0~9까지 이지만, 0으로 시작하는 경우는 존재하지 않는다고 언급했기 때문에 0을 제외한 1~9는 1자리 수이므로 모두 1로 채워준다. (값들은 각 숫자가 끝자리에 오는 경우의 수를 의미한다.) 이후 N이 2일 경우, 0이 끝자리에 오는 경우는 앞자리가 될 수 있는 수들은 0 -1 , 0 +1이 된다. 그러나 ..

→2019.11.27

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1463] 1로 만들기(JAVA 구현,추가풀이)

-내 생각 이번 문제의 경우는 쉽게 풀 수 있었던 것 같다. 처음에는 예제 입력 2의 경우 10이 1이 될 수 있는 경우를 직접 써봤고, dp배열을 만들어 각 인덱스를 숫자로 하여서 해당 숫자에 도달하기 위한 연산의 수를 저장하고자 했다. 예를 들어 n이 10인 경우 dp [10] = 0부터 시작하여서 10에서 가능한 경우의 수는 -1을 하거나, 2로 나누어 떨어지기 때문에 /2를 하는 경우가 존재한다. 그렇기 때문에 -1을 하게 된다면, dp [10] +1의 값을 dp [9]에 저장하는데 이때 값이 0인 상태라면 그냥 저장하고 0이 아니라면 저장되어 있던 값과 dp [10]+1의 값을 비교해 최솟값을 저장한다. 또 /2의 경우는 dp [5]에 앞선 과정을 반복한다. 이렇게 모든 반복을 1번까지 수행하면..

→2019.11.27

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2579] 계단 오르기(JAVA 구현)

-내 생각 이전까지 풀어봤던 dp문제들과는 조금 차이점이 있다. 점화식을 세워야 하는데, 어떻게 세워야 할지 몰라서 다른 분들의 글을 참고했다.. 나 스스로 푸는 게 없다 무슨 ㅋㅋㅋㅋ 어찌 됐든 풀 수 없다면 풀이를 분석하고 외우는 수밖에 없을 거다.... -해법 우선 점화식을 세우기 위해서는 문제에서 주어진 조건을 활용해야 하는 것 같다. 문제에서 주어진 조건은 1. 계단은 한 칸 또는 두 칸을 오를 수 있다. 2. 계단을 3개 연속 밟을 수는 없다. 3. 마지막 계단은 무조건 밟아야 한다.인데, 점화식을 세우는 방법은 계단이 존재할 때 한 개의 칸을 기준으로 가능한 경우의 수를 찾는 것이다. 계단을 밟을 수 있는 경우의 수는 아래의 표와 같다. n-3 n-2 n-1 n번 째 칸 O X O O O 또..

→2019.11.27

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1149] RGB 거리(JAVA 구현)

-내 생각 동적 프로그래밍을 풀기 전까지 백 트래킹 문제들을 풀어서 그런지 이 문제를 보자마자 백 트래킹 방식으로 풀 생각을 해버렸다.. 도저히 어떻게 풀어야 될지 모르겠어서 다른 분들의 글을 참고했다. -해법 우선 이 문제 역시 점화식을 세워주어야 한다. https://m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료) 문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문제 중 ... blog.naver.com 이 분의 블로그에 잘 정리가 되어 있기 때문에 자세한 설명은 생략하겠다. import java.util.*; public class Mai..

→2019.11.26

티스토리툴바