백준

    [백준,BOJ 10773] 제로(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10773] 제로(JAVA 구현)

    - 풀이 문제의 분류 자체가 스택이기 때문에 스택을 사용해야 한다는 생각이 들기도 하지만, 문제를 잘 읽어보면 정수가 계속 입력될 때 '0'이 입력되면 0이 입력되기 이전의 정수 하나를 지우기 때문에 최근에 입력된 데이터가 가장 먼저 출력되는 LIFO 구조의 스택을 사용해야 한다는 사실을 알 수 있다. 필자는 처음에 모든 정수를 입력받아 스택에 PUSH해준 뒤, POP 해가면서 0이 나오면 한 번 더 POP을 하는 식으로 접근하였지만, 예제 입력 2와 같이 0이 연속으로 입력되는 경우, 최근의 정수를 제대로 지우지 못하기 때문에 입력받을 때 0이면 바로 지워주게끔 풀이하였다. import java.io.BufferedReader; import java.io.BufferedWriter; import jav..

    [백준,BOJ 10828] 스택(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10828] 스택(JAVA 구현)

    -풀이 자료구조 중 LIFO구조인 스택의 기본적인 동작들을 구현하는 문제로, 자바의 경우 배열과 연결 리스트를 활용하여 직접 구현이 가능하며, 별도의 Stack 라이브러리가 제공되어 해당 메서드를 이용해도 된다. 필자는 배열과 라이브러리를 이용해 구현해 보았다. 또, 이 문제에서 주의해야 할 점은 제한시간이 0.5초로 상당히 짧기 때문에, BufferedReader와 BufferedWriter 객체를 사용하는 것이 좋을 것 같다. - 배열을 이용해 직접 Stack 클래스 구현 방법. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; i..

    [백준,BOJ 1541] 잃어버린 괄호(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1541] 잃어버린 괄호(JAVA 구현)

    - 풀이 이 문제의 경우 예제로 주어진 55-50+40이 55-(50+40)의 형태로 괄호를 씌워야 최솟값을 만들 수 있다는 사실을 알고, -를 기준으로 입력받은 문자열을 하나씩 탐색하며 다음 -를 만날 때까지 숫자들을 더하는 방식을 생각해 시도하였다. 그러나 문제에서 주어진 첫 문자와 마지막 문자는 숫자라는 조건을 보지 못하고 첫 문자에 음수가 입력되는 경우까지 생각하다 너무 복잡해져서 포기했다. 그런데 저 조건을 확인하고 나니 할 수 있을 것 같기도 하다. 결국 이 문제를 풀기 위해서는 -를 기준으로 문자열을 파싱해주면 된다는 것이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..

    [백준,BOJ 1931] 회의실 배정(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1931] 회의실 배정(JAVA 구현)

    -풀이 처음 이 문제를 풀 때는 각 회의 정보를 시작시간을 기준으로 정렬하여 회의별 소요되는 시간이 가장 짧은 순서대로 조건을 걸어 카운팅을 하려 했지만, 조건이 애매해져 다른 분의 글을 참고하였다. 다른 분의 글에서는 정렬을 종료시간을 기준으로 하여, 가장 일찍 끝나는 회의 순서대로 카운팅 하는 방법을 사용했다. 맞다. 회의실을 가장 많이 돌리려면, 빨리 끝나는 순서대로 집어넣는 것이 그리디라고 할 수 있다. import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(..

    [백준,BOJ 11047] 동전 0(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11047] 동전 0(JAVA 구현)

    - 풀이 이전에 풀었던 문제였지만, 블로그에 글을 게시하지 않았던 문제이다. 단계별 풀어보기의 그리디 알고리즘으로 분류되어 있는 첫 번째 문제이다. 그리디 알고리즘이란, 한 상황에서 취할 수 있는 최대 이득을 취하는 알고리즘이라 한다. 이러한 방식은 이전 분류인 동적 프로그래밍의 과정이 너무 많은 연산이 이루어지기 때문에 이를 보완하기 위해 고안된 알고리즘이라 한다. 한 상황에서 최선의 것을 선택하다 보니 최적의 해를 보장하지 않는다는 특징이 있다고 한다. 그리디 알고리즘으로 분류되어 있는 특징처럼 문제에서 주어진 값 k를 최소한의 동전 개수로 이루기 위해서는 가장 높은 단위의 화폐부터 사용하면 최소한의 동전 개수를 사용하게 된다. 최소한의 동전 개수를 이루기 위해 가장 높은 단위의 화폐부터 사용한다는 ..

    [백준,BOJ 1436] 영화감독 숌(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1436] 영화감독 숌(JAVA 구현)

    -내 생각 반복문을 통해서 증가시키면서 확인하려고 했으며, 증가 값이 n%10 = 6인 경우, 예를 들어 6일 때는 66을 뒤에 붙이고 마지막 자리는 0~9를 채우는 식으로 하려고 했었는데, 너무 복잡한 방식이었다.... -해법 결국 문제에 답이 있었다. 666이라는 숫자는 무조건 연속해야 하기 때문에 단순히 숫자를 증가시키면서 666이 포함되어있는 경우에 입력받은 n을 감소시키면 되는 거였다... import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n= sc.nextInt(); int num=0; // 증가 숫자 while(n>0) { /..

    [백준,BOJ 1018] 체스판 다시 칠하기(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1018] 체스판 다시 칠하기(JAVA 구현)

    -내 생각 이 문제 역시 브루트 포스로 분류되어있는 문제로, 문제 자체의 이해는 완벽하다고 생각했다. 요약하자면, m*n 크기의 보드판이 있을 때, 8*8 크기의 체스판으로 뜯어 냈을 때 규칙에 맞추기 위해 칸의 색을 최소한으로 수정해야 한다는 소린데, 이 과정에서 개인적으로 간과한 부분이 바로 체스판의 (0,0)은 하얀색 또는 검은색으로 시작할 때 시작이 하얀색인 과정에서의 횟수와 검은색일 때 횟수 중 최솟값을 찾는 것이었다. 처음에 나는 보드에서 떼어낸 체스판의 시작만을 보고 규칙과 비교하여 횟수를 반환했는데, 그것이 아니라 체스판의 시작이 무엇이든 두 가지 규칙과 비교해봤어야 했다는 소리다. 말로 설명하기 굉장히 힘든데 예를들어 예제 입력 2에서 8x8의 크기로 체스판을 (0,0) ~ (10 - 8..

    [백준,BOJ 7568] 덩치(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 7568] 덩치(JAVA 구현)

    -내 생각 브루트 포스 분류로 된 문제로 간단하게 요약해보자면, n명의 사람에게 몸무게와 키를 입력받고 다른 사람과 비교하여 자신보다 몸무게와 키가 큰 사람의 수 +1 이 자신의 등수가 되며 이를 공백을 기준으로 출력하는 문제이다. 배열에 저장해 정렬 라이브러리를 사용하면 쉬울 수 있지만, 브루트 포스 방식으로 모든 경우의 수를 따지기 위해 모든 비교를 수행하고자 했다. -해법 모든 사람과 비교하기 위해 반복문 2개를 중첩하였고, 각 경우의 수를 비교하여 자신보다 덩치가 큰 사람이 나올 때 마다 카운트하여 비교가 끝났을 때 +1 하여 자신의 등수를 결정한다. 코드를 보자. import java.util.*; public class Main { public static void main(String[] a..

    [백준,BOJ 1080] 행렬 (JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1080] 행렬 (JAVA 구현)

    -내 생각 알고리즘 초보자로서 그리디 알고리즘에 진입하고 나서부터 무언가 굉장히 헷갈리고 자신감이 사라졌다.. 문제를 이해하는데 많은 시간이 걸리지 않았지만, 어떻게 해결해야 할지 너무 막막해서 곧장 다른 분들의 블로그를 통해 문제를 정확하게 이해할 수 있었다. 똑같은 크기의 2차원 배열 A, B가 일치할 때까지의 변환 연산의 횟수를 구하는 것이 핵심인데 변환 연산은 3X3의 고정된 크기로만 변환이 가능하다. 처음에 다른 블로거 분들의 설명을 봤을 때는 '왜 (0,0)부터 뒤집기 시작하지?' 생각했는데, 생각해보면 3X3으로 고정되어있기 때문에 뒤집은 똑같은 3X3의 공간을 다시 뒤집는 바보 같은 짓(정말 똑같은 공간, 걸치는 공간은 몇 번이든 뒤집어질 수 있다.)을 제외하면 결국에는 각 원소가 뒤집어 ..

티스토리툴바