Algorithm/Baekjoon Online Judge

    [Java] 백준 4179 (불!) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 4179 (불!) Gold 4

    Problem : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net Approach BFS를 이욯하는 문제이다. 먼저, 입력을 받으면서 # 과 F인 부분은 visited배열에 true를 표시한다. 어차피 지훈이가 방문할 수 없는 곳이기 때문이다. 또한 지훈이가 방문한 곳을 불이 방문할 필요도 없다. 불보다 지훈이가 먼저 도착한 것이 되기 때문이다. 주의할 점은, BFS 를 시작할 때 불이 지훈이보다 먼저 시작해야 한다는 것이다. 점..

    [Java] 백준 6198 (옥상 정원 꾸미기) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6198 (옥상 정원 꾸미기) Gold 5

    Problem : https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net Approach 스택Stack 자료구조를 잘 이용해야 하는 문제이다. 스택을 빌딩의 높이 기준 내림차순 상태를 유지시키도록 구성하는 것이 문제 풀이의 포인트이다. 주요 문제 풀이 로직은 빌딩을 순차적으로 접근함을 전제로 다음과 같다. 스택이 비어있지 않고 스택의 top이 현재 빌딩의 높이 이하면 pop을 진행하며, ans에 (현재 빌딩 idx) - (스택 top의 빌딩 i..

    [Java] 백준 16986 (인싸들의 가위바위보) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16986 (인싸들의 가위바위보) Gold 3

    Problem : https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net Approach 순열을 이용한 완전탐색과 구현이 필요한 문제였다. 먼저 문제에서 주의할 점을 짚고 가자. 입력으로 주어지는 경희와 민호의 패는 라운드 별 패가 아니다. 경희와 민호가 참여하는 게임에서 내는 패의 순서일 뿐이다. 지우가 질 경우에도 사용한 적이 없는 패를 내야한다. (서로 다른 패로 이기는 경우만을 찾는 것이 아니다.) 문제 풀이의 주요 로직은 다음과 같다..

    [Java] 백준 16985 (Maaaaaaaaaze) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16985 (Maaaaaaaaaze) Gold 3

    Problem : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net Approach BruteForce(완전탐색) 순열 + BFS + 구현 개념이 사용된 문제였다. 문제 풀이에 사용된 주요 로직은 다음과 같다. 주어진 판들의 순서를 순열로 구하여 쌓는다. 쌓인 판들을 0도, 90도, 180도, 270도를 돌려서 나오는 모든 경우를 찾는다. 2번 과정에서 찾아진 각 경우에 대해 (0, 0, 0) ~ (4, 4, 4) 로 가는 ..

    [Java] 백준 16957 (체스판 위의 공) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16957 (체스판 위의 공) Gold 4

    Problem : https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙 www.acmicpc.net Approach Union-Find 성격의 개념과 DFS를 혼용하여 풀이한 문제이다. 처음엔 모든 위치를 기준으로 DFS를 수행하여 정답을 구하였다. 이 방법은 TLE(Time Limit Error)가 발생한다. 그러므로 다른 방법을 사용해야 한다. 시간초과를 받은 코드와 정답처리를 받은 코드를 함께 게시하겠다. DFS는 불가피하다. 그러므로 DFS의 횟수를 줄이면서 알고..

    [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 열까지의 누적합을 저장한다. 문제에서는 정삼각형을 나타내지만 배열에 저장할 때는 아래 그림처럼 직각삼각형처럼 저장된다. 이제 파란 삼각형과 빨간 삼각형처럼 모든 만들 수 있는 삼각형의 합을 구하여 그 중 최댓값을 구해야 한다. 파란 삼각..

    [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개 놓는 모든 경우를 만든다. 그 상태에서 상대 돌을 ..

티스토리툴바