전체 글

전체 글

    [Java] 백준 12931 (두 배 더하기) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 12931 (두 배 더하기) Gold 4

    Problem : https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net Approach Greedy 한 방법으로 숫자의 2진수 비트를 활용하여 문제를 풀이하였다. 먼저 문제 풀이에 사용한 자바 메소드를 살펴보자. Integer.toBinaryString(int n): 숫자 n을 받아서 문자열 이진수로 바꾼 뒤 리턴한다. Integer.bintCount(int n): 숫자 n의 이진수에서 1의 개수를 리턴한다. 숫자를 만드는 데에 +1..

    [Java] 백준 16639 (괄호 추가하기 3) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16639 (괄호 추가하기 3) Gold 1

    Problem : https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net Approach 괄호 추가하기 2와 같은 BruteForce 문제가 아닌 DP 문제로, 아예 다른 유형의 문제였다. 중첩된 괄호가 있을 수도 있고, 괄호 안에 여러 연산자가 존재할 수도 있기에, 연산자들의 우선순위는 고려할 사항이 아니다. 따라서 수식의 i ~ j까지의 결과는 i ~ k의 결과 + k ~ j의 결과 임을 이용하면 된다. 주의할 점은 (음수) * (..

    [Java] 백준 16638 (괄호 추가하기 2) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16638 (괄호 추가하기 2) Gold 1

    Problem : https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net Approach Backtracking 기법과 중위표기 -> 후위표기 를 위한 Priority, Stack 등을 사용해야 했던 문제이다. 중첩된 괄호는 사용할 수 없고, 괄호 안에는 하나의 연산자만 존재할 수 있다는 점을 활용하면, 연산자를 기준으로 괄호를 씌울 것인지 말 것인지를 결정하면 된다는 걸 알 수 있다. 따라서 brackets 배열을 두어 해당 연산자가..

    [Java] 백준 4902 (삼각형의 값) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 4902 (삼각형의 값) Gold 2

    Problem : https://www.acmicpc.net/problem/4902 4902번: 삼각형의 값 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 줄의 수를 나타내고, 다음 숫자는 단위 삼각형에 적혀있는 값이 위에서 아래, 왼 www.acmicpc.net Approach 누적 합 개념과 구현이 합쳐진 문제였다. 먼저 누적 합 배열 preSum을 구성한다. preSum[i][j] 는 i행의 0 ~ j 열까지의 누적합을 저장한다. 문제에서는 정삼각형을 나타내지만 배열에 저장할 때는 아래 그림처럼 직각삼각형처럼 저장된다. 이제 파란 삼각형과 빨간 삼각형처럼 모든 만들 수 있는 삼각형의 합을 구하여 그 중 최댓값을 구해야 한다. 파란 삼각..

    [IntelliJ] Can't build maven jhipster project with lombok
    TroubleShooting

    [IntelliJ] Can't build maven jhipster project with lombok

    Can't build maven jhipster project with lombok 해당 문제는 프로젝트 내에서는 lombok이 문제없이 동작하였으나, build 단계에서 getter/setter 메소드를 찾을 수 없다거나 (Cannot find symbol), Constructor 생성자가 생성이 안되어 에러를 내뱉으며 발생하였다. 해당 프로젝트에 lombok plugin을 설치하고, pom.xml 에 dependency를 주입하고, enable annotation proccessor 를 체크하면 프로젝트에서 lombok을 사용할 수 있다. lombok 설치와 annotation에 대해서는 아래 포스팅을 참고하길 바란다. https://gre-eny.tistory.com/303 [IntelliJ] Lo..

    [Java] 백준 16988 (Baaaaaaaaaduk2 (Easy)) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16988 (Baaaaaaaaaduk2 (Easy)) Gold 3

    Problem : https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Approach BruteForce 완전탐색과 BFS의 개념을 같이 사용한 문제였다. 일단 문제 풀이의 주요 로직은 다음과 같다. 먼저 BFS를 이용하여 상대편 돌을 Grouping한다. 그리고 그룹핑한 결과를 groups에 저장한다. 그리고 Backtracking을 사용하여 돌을 2개 놓는 모든 경우를 만든다. 그 상태에서 상대 돌을 ..

    [Java] 백준 15684 (사다리 조작) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 15684 (사다리 조작) Gold 4

    Problem : https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net Approach 백트랙킹 Backtracking을 활용하여 BruteForce 완전탐색으로 풀이하였다. 가로선을 놓을 수 있는 개수는 0, 1, 2, 3개 이다. 이를 이용하여 문제를 푸는 주요 로직은 다음과 같다. 가로선을 놓을 수 있는 개수만큼 가로선을 놓아본다. 이 때, A 번째 사다리가 A 에 도착하는지를 검사한다. 모든 경우의 수에 대하여 위 과정을 수행한다. 생각하기..

    [Java] 백준 17069 (파이프 옮기기 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17069 (파이프 옮기기 2) Gold 5

    Problem : https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP 로 문제를 풀이했다. 백준 17070 (파이프 옮기기 1)와 똑같은 문제지만, 문제의 입력 부분에 차이가 있다. [java] 백준 17070 (파이프 옮기기 1) Gold 5 문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 ..

    [Java] 백준 9944 (NxM 보드 완주하기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 9944 (NxM 보드 완주하기) Gold 3

    Problem : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net Approach BruteForce완전탐색 + 구현으로 문제를 풀이하였다. 문제풀이에 앞서 해당 문제는 입력의 끝이 정해져 있지 않다. 해당 내용에 관한 부분은 아래 포스팅을 참고하면 좋을 것이다. https://gre-eny.tistory.com/307 [Java] EOF(End Of File) 처리하기 EOF(End Of File) EOF(End Of File) 은..

    [Java] 백준 17088 (등차수열 변환) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17088 (등차수열 변환) Gold 4

    Problem : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1] www.acmicpc.net Approach 등차수열의 공차 개념을 이용한 BruteForce(완전탐색)로 문제를 풀이하였다. 수열의 각 요소들에 -1, +1연산을 최대 1번 수행할 수 있다고 한다. 주의할 점은 0번 수행해도 된다는 것이다. 수열에서 연속된 두 요소의 차를 공차 라고 한다. 직전 숫..

티스토리툴바