본문 바로가기

Algorithm

백준 2193 이친수 Java 2019. 4. 10. dp문제인 이친수이다. 나 뿐만 아닌 누구든 문제 제목을 보고 이천수 선수를 떠올렸다는 것에 약 천원을 걸겠다. 이 문제 역시 혼자 정답인 점화식을 생각해내는 것엔 실패 했다. 갈 길이 멀다. 마지막 자리에 올 수 있는 경우의 수가 0과 1이기 때문에 dp[n-1]+2를 하고 마지막이 1인 경우엔 1이 못오기에 -1을 해서 dp[n-1]+2-1을 하면 되지 않을까? 생각했다. 확신은 없었고 당연히 틀린 답이였다.. 마지막 자리인 n자리에 0과 1이 올 수 있다는 것은 알겠고.. 마지막에서 한칸 앞인 n-1의 자리에 1이 온다면 0밖에 올 수 없다는 것은 알았다. 하지만 n-1의 자리에 1이 오는 경우의 수를 생각해내지 못했다. 온라인 강의였지만 최백준님은 이런 나를 비웃기라도 하듯 명쾌한 해법을 보여주셨..
백준 9095 1, 2, 3 더하기 Java 2019. 4. 9. dp문제는 문제를 잘 읽어보고 푸는 방식을 빨리 캐치하는 것이 중요한 것 같다.. 나에게는 아직 너무나도 미숙한 능력이다. 이 문제는 마지막에 어떤 수가 올 수 있는지가 중요한 문제 였다. 합을 나타낼 때는 수를 1개 이상 사용해야 하고 어떠한 정수n을 1, 2, 3의 합으로만 나타내는 방법의 수를 구하는 문제이다. 난 합으로만 나타낸다 길래 n=2 {1+1} 이 끝인 줄 알았다. 하지만 n=2 {1+1, 2}이였다. 내가 멍청한 건가...........맞는듯하다. 아무튼 숫자는 1또는 2또는 3밖에 못쓰기 때문에 마지막에 올 수 있는 숫자는 당연 1, 2, 3 이다. 이를 통해 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]이라는 점화식을 세울 수 있다. 물론 내가 생각해내진 못했다. 정답률 ..
백준 11726 2xn 타일링 Java 2019. 4. 9. 문제를 잘 읽고 푸는 방법을 생각하는 연습을 좀 해야겠다. 마지막에 어떤 수가 올 수 있는지 생각하는 것이 중요하다는 걸 깨달았다. 이문제 같은 경우에는 마지막이 항상 세로 타일 1개 또는 가로 타일 2개가 올 수 있다. 세로 타일이 왔을 경우는 세로 타일의 길이를 제외하면 n-1, 가로 타일이 왔을 경우는 가로 타일의 길이를 제외하면 n-2 이다. 마지막에 올 수 있는 타일의 형태에 따라 앞의 n-1 또는 n-2의 타일의 경우의 수는 앞에 구해놓은 dp에서 가져오면 된다. 따라서 점화식을 dp[n] = dp[n-1] + dp[n-2] 로 만들 수 있다. 참 이해하기 힘든 것 같다. 출력은 10,007을 나머지 한 값을 출력하면 되는데 dp를 구해놓고 마지막 출력할때 %연산을 해주면 어김없이 '틀렸습니다..
백준 1463 1로만들기 Java 2019. 4. 9. 내가 제일 어려워하는 dp 문제들 중 쉬운 편에 속하는 문제이다. 나는 이것도 못풀었지만 최백준 님의 강의를 통해 dp 문제를 해결하는데 대충은 감을 잡은 것 같다. dp문제는 작은문제들로 큰문제를 해결하는 것이라고 한다. 1로 만들기 문제를 통해 다시 한번 정리해 볼 것이다. n을 1로 만들때의 최소값을 구하기 위해 1, 2, 3 ,4 ... n까지의 최소값을 전부 구해야한다. 원래 나는 처음부터 n의 최소값을 구하는 알고리즘을 짜곤 했었는데 그건 dp에대한 이해가 부족한 것이었다. 문제에서는 1로만들 수 있는 세가지 방법을 알려준다. 1. 3으로 나누어떨어질 때는 나누기 3 2. 2로 나누어떨어질 때는 나누기 2 3. 빼기 1 3으로 나누어떨어진다고 해서 무조건 3부터 나눠버리는게 1로 만드는 최소값..
백준 1406 에디터 Java 2019. 4. 8. 언뜻 봤을 땐 쉬워 보였던 문제이다. 하지만 한 번 틀리고 정답률을 보았을 때 쉽지 않은 문제라는 걸 알게되었다. 문제는 간단하다. 문자열이 주어지면 처음엔 커서가 문자열 맨 끝에 있고 L : 커서를 한칸 왼쪽으로 D : 커서를 한칸 오른쪽으로 B : 커서 왼쪽에 있는 문자 삭제 P : 다음에 주어지는 문자를 커서 왼쪽에 삽입 물론 L이나D의 경우에 커서가 더 이상 갈 곳이 없을 땐 처리해줘야 한다. 나는 당연히 문제를 보고 StringBuilder를 이용해서 풀 생각을 했다. 처음 틀렸을 당시 내 코드는 이렇다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public static ..
백준 10799 쇠막대기 Java 2019. 4. 8. 최백준님의 강의를 듣던 도중 접한 스택문제이다. 고민해 보지 않고 풀이법을 바로 보았던 터라 다시한번 정리하고자 한다. 문제내용을 정리해보면 어떠한 쇠막대기가 다른 쇠막대기 위에 있다면 아래에있는 쇠막대기 길이에 위에있는 쇠막대기가 포함되어야한다. 레이저로 잘린 쇠막대기의 개수를 구해라. "( )" -> 레이저 " ( " -> 쇠막대기 시작점 " ) " -> 쇠막대기 끝점 분명 내가 스스로의 힘으로 풀었다면 Stack에 " ( "를 만나면 " ( "를 넣고 " ) "를 만나면 입력받은 문자열의 subString(i-1, i)로 " ( " 인지 확인하여 레이저로 취급했을 것이다. 아무튼 최백준님의 풀이를 보면 Stack로 문자열에서 " ( "를 만나면 인덱스를 스택에 넣는다. 그리고 " ) " 를 만나면 ..
백준 10951 A+B - 4 Java 2019. 4. 8. 입출력 스타일에 관한 예제에 포함되어 있던 문제이다. 대부분의 문제와는 다른 점이 있어 글을 작성해본다. 다른 +연산 문제와 이 문제가 다른 점은 테스트 케이스가 주어지지 않는다는 점이다. 입력 케이스가 몇개이든 상관없다는 얘기다. C언어에서는 EOF를 사용하면 된다는데.. EOF가 없는 자바에서는 어떻게 할까. 정답은 Scanner 클래스의 hasNextInt()를 사용하는 것이었다. while(hasNextInt())를 사용해도 while(true)처럼 하염없이 다음 입력을 기다리는 것은 똑같은데 전자는 정답처리가 되고 후자는 런타임에러가 박힌다. 정답처리의 이유는 검색을 통해 알아본 결과 EOF를 직접 입력했을 때 멈추기 때문..? 이라고 한다. 1 2 3 4 5 6 public static voi..

티스토리툴바