[백준,BOJ 11053] 가장 긴 증가하는 부분 수열(JAVA 구현,추가풀이)

-내 생각 우선 이 문제는 LIS알고리즘이라고 하여서 무언가 알고리즘에 대한 기본적인 개념 같은 것이 있을 줄 알고 검색해봤는데, 그렇지 않고 그냥 알고리즘 문제들 중 대표적인 문제의 유형 중 하나인 것 같다. 그래서 의도치 않게 문제 해설을 봐버리게 되어서 분석해보았는데, 크게 어려운 부분은 없었다. 그러나 여기서 사용한 2중 for문의 경우는 수열의 길이가 10 이상이 돼버리면 1초에 완료할 수가 없다고 한다. 왜냐하면 2중 for문은 O(N^2)의 시간 복잡도를 가지기 때문이라고 한다. LIS를 푸는 O(NlogN) 방법이 있다고 하는데, 여기엔 이진 탐색을 사용한다고 하니 후에 글로 남겨야겠다. -해법 우선 가장 긴 증가하는 부분 수열이라는 문제에서 핵심은 일정한 숫자들이 주어질 때 첫 번째 숫자..

→2020.11.25

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

[백준,BOJ 2156] 포도주 시식(JAVA 구현,추가풀이)

-내 생각 포도주 시식 문제의 경우 계단 오르기 문제와 유사한 점이 많다고 생각한다. 계단 오르기와의 공통점은 3개의 원소를 연속해서 선택할 수 없다는 점이며, 큰 차이점은 마지막 잔을 반드시 마실 필요가 없다는 것이다. 계단 오르기를 분석하고 이러한 유형의 문제를 풀 때 약간의 요령이 생기긴 했던 건지, 점화식을 첫 번째것은 잘 세웠는데, 두 번째 점화식을 고려하지 못해 오답처리를 받았다가 다른 분들의 도움으로 해결할 수 있었다. -해법 우선 점화식을 세우기 위해서 적당히 4개 정도의 포도주 잔이 있다고 가정하고 생각해 보았다. 아래가 그 표이다. 우선 특정 포도주를 먹기 위한 경우의 수를 생각해보면, N번 째 포도주를 먹거나 먹지 않거나 이므로 2가지 경우가 발생한다. 이후 만약 먹었을 경우 이전 포..

→2020.11.25

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

[백준,BOJ 1932] 정수 삼각형(JAVA 구현,추가풀이)

-내 생각 이번 문제 이전에 풀었던 RGB거리 문제 덕에 이러한 비용 문제, 또는 숫자의 누적 문제는 문제에서 주어진 입력과 동일하게 배열을 하나 만들어 해당하는 지점까지의 결과를 저장해 나가면서 풀면 된다는 것을 알 수 있었다. 이 문제에서 약간 혼동될 수 있는 부분이 있다고 생각하는데, 문제 부분의 글과 그림을 보면 정삼각형의 형태로 입력이 주어지는 것처럼 보이지만, 예제 입력 1을 보면 알 수 있듯이 열이 +1씩 되면서 입력이 되는 것을 알 수 있다. 그렇기 때문에 문제에서 말하는 왼쪽 대각선과 오른쪽 대각선의 의미는 사실상 배열의 개념에서 생각해 볼 때, 자신이 속한 열과 그다음 열을 의미한다는 것이다. 예를 들어, 삼각형의 2층에서 8이 선택할 수 있는 숫자는 자신이 속한 행인 1과, 그다음 열..

→2020.11.25

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

[백준,BOJ 2748] 피보나치 수 2(JAVA 구현,추가풀이)

-내 생각 우선 피보나치수열의 개념의 이해는 쉽다. 처음에는 동적 프로그래밍 알고리즘을 사용하는 과정에서 각 결괏값을 저장하는 배열을 int형으로 선언했는데, 수 들이 기하급수적으로 커지기 때문에 long타입으로 다시 선언해 주었다. -해법 코드는 간결하다. import java.util.*; public class Main { static int n; static long check[] = new long[91]; // long형 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n= sc.nextInt(); check[0]= 0; // 0번, 1번 숫자는 미리 저장해둔다. check[1] =1; for(in..

→2020.11.19

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

[백준,BOJ 14889] 스타트와 링크(JAVA 구현,추가풀이)

-내 생각 단계별 풀어보기 백트래킹 분류에 있는 마지막 문제로 이 문제 역시 삼성 기출문제라고 한다. 문제 자체의 이해는 어렵지 않지만, 주의해야 할 부분이 하나 있는데, 예제 입력 2번의 경우 사람의 수는 6명이므로 3:3으로 나누어 게임을 진행한다. 이때 예를 들어 3명으로 이루어진 팀 중 한 팀의 구성원을 1번, 2번 3번을 선택했을 때 팀의 능력치는 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)의 합이 된다는 점이다. 처음에 풀 때는 예제 입력 1을 기준으로 생각하여서 고려하지 못했던 부분이다. 또한 이 문제를 풀기 위해서 어떻게 풀어야 할지 고민하는 과정에서 DFS를 어떤 방식으로 수행해야 할 지 고민이었는데, 처음 시도한 방법은 2중 반복문으로 한 명의 사람을 고정 ..

→2020.11.19

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

[백준,BOJ 14888] 연산자 끼워넣기(JAVA 구현,추가풀이)

-내 생각 단계별로 풀어보기를 통해서 접한 첫 번째 기출문제였다. 스도쿠와 N-Queen 문제 때문인지 문제의 난이도는 그렇게 높다고 느껴지지 않았다. 그러나 문제를 푸는 동안 시행착오가 한 번 있었는데, 최댓값과 최솟값을 비교하기 위해서는 모든 연산자를 경우의 수에 따라 전부 대입해보아야 했는데, 처음에는 하나의 연산자를 넣어 비교하는 방식을 이용해보려 했다. 예를 들어 예제 입력 3번의 경우에서 1과 2를 각 연산자로 한 번만 계산 후 대소 비교를 생각했었는데, 힌트를 보고 틀린 생각이란 것을 알 수 있었다. 최댓값의 경우가 1과 2 사이의 연산자가 -인데, 앞선 방식으로 풀면 x일 때가 최댓값의 경우라고 가정하게 되는 것이다. 즉, 결과적으로는 모든 연산자를 각 경우의 수에 따라 대입해 최종 값을 ..

→2020.11.19

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

[백준,BOJ 2580] 스도쿠 (JAVA 구현,추가풀이)

-내 생각 여태 푼 백 트래킹 알고리즘을 이용하는 문제들 중 N-QUEEN문제만큼 고민 한 문제이다. 그래도 N-Queen문제를 한 번 풀어봤던 탓인지, 어떻게 풀어야 할지 감을 잡는데 오랜 시간이 걸리지는 않았다. 이 문제까지 풀어보고 느낀 건 백 트래킹 알고리즘의 경우 별도의 체크 메서드가 반드시 필요하다는 점이다. 글에서만 봤지만 무슨 소리인지 몰랐던 '유망한 노드'를 식별하는데 필요하다고 생각한다. 즉, 조건에 해당하는 사항만 DFS로 재귀호출을 해주면 된다. 우선 스도쿠 문제의 경우 대다수의 사람들이 조건을 알 거라고 생각한다. 물론 문제에도 쓰여있다. 즉 가로, 세로, 3X3크기의 박스에 1부터 9까지의 숫자가 겹치지 않고 들어가야 한다. 여기까지만 읽으면 백 트래킹을 위한 조건을 어떻게 세워..

→2020.11.19

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

[백준,BOJ 9663] N-Queen (JAVA 구현,추가풀이)

글을 쓰기에 앞서 블로그 개설 후 방문자 수가 늘었다. ㅎㅎㅎ 그냥 개인 기록용 블로그로 쓰고 있는 거여서 방문자 수는 별로 신경 안 쓰고 있는데, 사람들이 찾아와 준다는 게 신기했다. 물론 글이 유익했는지는 모르겠지만.. 그래도 그중에는 도움을 받아가는 분이 있다고 믿고 싶다. ㅎㅎ 문제를 보자! -내 생각 백 트래킹 알고리즘 중 가장 유명한 문제라는데 확실히 검색해보면 다른 많은 분들이 관련해서 글들을 많이 올리신 것 같다. 하지만 문제 자체는 쉽지 않다고 생각한다.. 실제로 이 문제를 풀기 위해서 3일을 소요했으니..(여러 개인 사정으로 자세히 고민해보지는 못했지만 ㅎㅎ) 우선 문제 자체는 어렵지 않다. 체스의 퀸을 활용한 문제인데, 체스의 룰에 대해서는 이전부터 알고 있었기 때문에 퀸이 상하 대각..

→2020.11.17

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

[백준,BOJ 15652] N과 M(4) (JAVA 구현,추가풀이)

-내 생각 백준 온라인 저지에서 단계별 풀어보기 탭의 백트래킹 카테고리에 있는 마지막 N과 M문제이다. 이번 문제가 가지는 앞선 문제들과의 차이점은 우선 중복을 허용하며, 각 자리의 숫자들은 자신보다 앞에 있는(먼저 오는) 숫자보다 크거나 같아야 한다는 조건이 있다. 그렇기 때문에 처음 봤을 때 N과 M(3) 문제에서 조건만 추가해주면 될 것 같다고 생각했으며, 시간제한이 1초이기 때문에 마찬가지로 BufferedWriter클래스와 BufferedReader클래스를 사용해주었다. -해법 추가된 한 줄의 조건문은 코드를 보면서 이해해 보자. import java.io.*; import java.util.*; public class Main { static int m,n; static int list[]; ..

→2020.11.17

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

[백준,BOJ 15649] N과 M(2) (JAVA 구현,추가풀이)

-내 생각 백준 15649번 문제인 N과 M(1)이 순열을 출력하는 문제였다면, 이번 문제는 조합을 출력하는 문제였다. 어떤 블로그에서 봤던 글에 의하면 순열과 조합 문제는 DFS를 이용해 구현하면서, 순열의 경우에는 순열의 끝을 기준으로 재귀 호출을 종료하며, 조합의 경우에도 재귀 호출을 종료하는 조건은 같지만, 중간 처리 부분에서 하나의 인자가 더 필요하다는 것을 알 수 있었다. 하지만 글을 자세히 보지 않아 어떤 인자가 들어가야 할지 고민해보다 순열은 매 순간마다 1부터 끝 숫자까지 탐색해야 하고 조합은 (1,2)나 (2,1)을 같은 경우로 보기 때문에 매 순간마다 1부터 볼 필요가 없다는 사실을 떠올리고 반복문의 시작 부분을 변경해주면 될 것 같다는 큰 틀을 잡고 구현해보았다. -해법 이전에 N과..

→2020.11.17

티스토리툴바