Java

    [백준,BOJ 14888] 연산자 끼워넣기(JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

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

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

    [백준,BOJ 2580] 스도쿠 (JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

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

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

    [백준,BOJ 9663] N-Queen (JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

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

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

    [백준,BOJ 15652] N과 M(4) (JAVA 구현,추가풀이)
    코테/백준 온라인 저지(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[]; ..

    [백준,BOJ 15649] N과 M(2) (JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

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

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

    [백준,BOJ 7576] 토마토(JAVA 구현, 추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 7576] 토마토(JAVA 구현, 추가풀이)

    -내 생각 알고리즘 문제를 계속해서 풀다 보니까 이제 언제 DFS를 쓰고 언제 BFS를 써야 하는지 감이 좀 잡히는 듯하다. 이번 문제의 경우에는 토마토가 인접한 토마토를 1일이 지날 때마다 익게 한다는 것이 포인트라고 생각했다. 즉 초기에 주어지는 익은 토마토를 기준으로 인접한 토마토를 모두 익게 만들면 되는 것인데, 인접한 노드를 모두 탐색하는 것은 BFS이므로 BFS를 사용하면 될 것 같다고 생각했다. 하지만 이번 문제 역시 막힌 부분이 있었는데, 입력으로 익은 토마토가 1개 주어질 경우는 구현이 됐지만, 익은 토마토가 2개 이상 주어지면 답이 이상해졌다. 역시 다른 블로그 분들의 글을 보고 힌트를 얻을 수 있었다. -해법 위에서 언급한 문제점이 발생된 이유는 초기 인자를 넘겨줄 때 모든 칸을 탐색..

    [백준,BOJ 2178] 미로 탐색(JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2178] 미로 탐색(JAVA 구현,추가풀이)

    -내 생각 알고리즘 공부를 시작하고 코딩 테스트에서 자주 나온다는 최단경로 문제를 처음으로 풀어보았는데.. 이전에 여러 글들을 보면서 최단거리 문제의 경우에는 BFS만을 이용해서 풀 수 있다고 알고 있었기 때문에 BFS를 사용하려고 했지만, 어떻게 구현해야 할지 감이 잡히지 않았다. 기본적인 흐름은 앞선 DFS문제들과 마찬가지로 인접한 좌표를 탐색하는 것부터 시작해야 한다고 생각했고, 각 경로마다 이동할 때마다 카운트해주어서 분기점에서 갈라진 경로마다의 카운트 변수를 비교해 최솟값을 찾으려고 했는데, 이것도 생각만 했지 구현도 완벽하게 하지 못했다. 2시간 정도 고민해보고 도저히 안될 것 같아 다른 여러 블로그들을 참고했는데, 하단의 Idgeao99님 블로그에서 힌트를 얻을 수 있었다. 혹시라도 막히는 ..

    [백준,BOJ 11004] k번째 수( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11004] k번째 수( JAVA 구현)

    -내 생각 우선 이 문제를 보면, 단순하게 자바에서 제공하는 Arrays.sort()를 이용하여 정렬 후 k번 째 수를 출력하면 되는 간단한 문제라고 생각했다. 그러나 결과는 시간 초과가 발생하였고, 입력 값의 수가 많기 때문에 BuffredReader 클래스를 사용하여서 StringTokenizer을 통해 공백을 구분하여 입력받아 제출해보았지만, 역시 시간 초과가 발생하였다. 그래서 검색을 통해 찾아보았더니 이러한 N개의 수에서 K번 째 수를 반환하는 경우에 사용되는 특정한 알고리즘인 Quick Selection이라는 알고리즘이 존재한다는 사실을 알 수 있었고, 해당 알고리즘은 Quick sort방식을 응용한 방식이라는 점을 알게 되어서, 우선 Quick sort문제를 풀면서 공부하기로 한 이후 미루어..

    [백준,BOJ 2751] 수 정렬하기 2( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2751] 수 정렬하기 2( JAVA 구현)

    -내 생각 우선 이 문제를 풀게 된 계기는 11004번 문제인 k번째 수 문제를 풀려고 했는데, 이러한 방식은 Quick Selection이라는 별도의 알고리즘을 사용한다고 해서 찾아보니, 해당 알고리즘은 기존의 퀵 정렬 알고리즘을 활용한 방식이라고 하여서 퀵 정렬 알고리즘을 우선적으로 공부해보고자 해서 풀게 되었다. 이전에 동영상 강의를 보면서 병합 정렬을 사용해서 풀었던 문제였는데, 한 달이라는 시간이 지나서 기억이 나지 않아서 우선 퀵 정렬을 이용해 풀어보기로 했다. 그러나 혼자 힘으로 구현해보려 했지만 잘 되지 않아서 마이구미님의 블로그를 참고하게 되었다. 아래에 설명이 자세히 나와있다. https://mygumi.tistory.com/308 퀵소트 알고리즘 :: 마이구미 이 글은 정렬 중 퀵소트..

    [백준,BOJ 11652] 카드( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11652] 카드( JAVA 구현)

    -내 생각 이 문제의 경우 처음 봤을 때, 주어질 수 있는 정수의 범위만큼 별도의 배열을 생성하여서 해당 정수 값을 인덱스로 하여서 해당 정수를 만날 때마다 해당 인덱스 값을 증가시키는 방법을 생각했었는데, 문제를 보면 데이터의 범위가 +-2^62로 굉장히 크기 때문에 이러한 방식을 사용하면 메모리 낭비가 심하고 데이터의 탐색 역시 오래 걸릴 것 같아 사용하지 않았다. -해법 위에서 언급한 문제점을 해결하기 위해서 우선 값을 입력받는 배열을 생성해 값을 입력받은 후 오름차순 또는 내림차순 정렬을 통해 같은 숫자를 연속하게 놓이게 만들었다. 이후 n-2까지 탐색을 통해 다음 원소와 비교하여 값이 달라질 경우 카운트 변수를 초기화하여 최대 카운트 수를 가지는 정수를 찾은 후 출력하려고 했다. 그러나 문제 제..

티스토리툴바