[백준,BOJ 11399] ATM(JAVA 구현)

-풀이 그리디 알고리즘을 사용하기 적합한 문제의 조건은 1. 각 경우가 독립적인 경우 2. 각 경우의 선택으로 다른 경우에 영향을 미치지 않는 경우를 만족하면 된다고 알고 있다. 이 문제의 경우 각 사람들의 대기시간이 상호 영향을 받지 않는 독릭접인 상태이다. 그리디 알고리즘을 이용해 손님들의 소요시간을 최소로 만들기 위해서는 먼저 끝나는 사람을 우선으로 처리하면 최솟값이 나오게 된다. 이는 이전의 회의실 배정 문제와 비슷한 유형이라고 생각된다. 그렇기에 문제에서 알려주고 있는 최솟값을 구하는 방법을 코딩으로 옮기기만 하면 된다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(Str..

→2020.11.27

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

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

-내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제의 경우 knapsack 알고리즘이라고 별도로 존재한다는 사실을 알 수 있었다. -해법 knapsack알고리즘의 경우에 dp 배열을 1차원 또는 2차원으로 해결할 수 있다고 하는데, 많은 사람들이 2차원 배열을 사용하는 것 같다. 나의 경우는 알고리즘 대회를 준비하는 것이 아닌, 취업을 위한 공부이기 때문에 합격선만 만족하면 더 쉬운 것을 사용하는 것이 맞는 것 같다. dp배열을 사용할 때 각 인덱스가 의미하는 바는 dp [i번 째 아이템][무게]를 의미한다고 한다. 이를 표로 그려보면 아래와 같이 나타낼 수 있다. 0번..

→2020.11.26

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

[백준,BOJ 1912] 연속합(JAVA 구현,추가풀이)

-내 생각 문제를 제대로 읽어보지 않아서 점화식을 세울 수가 없었다. 이 문제에서 중요하게 보아야 할 내용은 수를 선택할 때 한 개 이상의 수를 연속되게 선택해야 한다는 제약조건이 있다. 즉 1번 숫자를 선택한 후 2번 숫자를 선택하지 않으면 더 이상 선택할 수 가없는 것이다. -해법 그렇다면 이 문제는 어떻게 해결해야 할까? 별도의 dp배열을 생성하여 누적된 값과 현재부터 다시 선택을 시작한 값을 비교해주면 간단하다. 우선 기본적인 점화식은 dp [n] = dp [n-1] + cost [n]이 되는데(기본 누적 점화식), 연속해서 선택해야 한다는 제약조건이 존재하기 때문에 예를 들어, 2번까지 누적해서 선택한 결과와 2번이 첫 번째로 선택된 결과 중 큰 값을 취해야 한다는 것인데, 1번, 2번을 누적하..

→2020.11.26

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

[백준,BOJ 9251] LCS(JAVA 구현,추가풀이)

-내 생각 LIS알고리즘에 이은 LCS알고리즘이다. 전혀 처음 보는 유형의 문제였기 때문에 혼자 힘으로 풀지는 못했다. -해법 LCS의 경우 주의해야 할 경우가 Longest Common Subsequence인 최장 공통부분 순열이 있고, Logest Common Substring인 최장 공통부분 문자열인 경우가 있다고 한다. 순열의 경우는 현재 문제처럼 연속되는 문자는 고려하지 않고 단순히 두 문자열을 비교해서 겹치는 경우의 수를 구하는 것이다. 예를 들어 ACAYKP는 CAPCAK와 비교했을 때, A, C, P, K가 순서에 고려되지 않고 겹치게 된다. 그러나 문자열의 경우는 CA만이 순서와 내용이 일치한다는 차이점이 있다. LCS의 경우에는 2차원 배열을 이용해서 구하게 되는데 https://you..

→2020.11.26

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

[백준,BOJ 11054] 가장 긴 바이토닉 부분 수열(JAVA 구현,추가풀이)

-내 생각 이 문제를 이해할 때 주의해야 할 점이 하나 있는데, 바이 토닉 부분 수열과 바이 토닉 수열의 구분을 확실히 해야 한다. 이 문제에서 묻는 대상은 바이 토닉 부분 수열이기 때문에 문제에서 예로 든 {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이 토닉 수열이 아니라는 것이다. 처음 구현하기에 앞서 바이 토닉 부분 수열의 경우 가장 큰 값을 기준으로 왼쪽으로는 작은 값을 갖고, 오른쪽으로는 큰 값을 가지는 것을 보고 우선 가장 큰 값을 찾은 후 왼쪽부터 증가하다가 큰 값을 만나면 그 이후부터는 작은 값을 처리해 주려고 했지만, 구현에 실패해서 다른 분들의 글을 통해 도움을 받았다. -해법 우선 이 문제를 풀기 위해서는 LIS라는 개념이 완벽..

→2020.11.26

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

[백준,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

티스토리툴바