구현

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2

    Problem : https://www.acmicpc.net/problem/18809 Approach 조합을 이용한 BruteForce 와 BFS + 구현 이 필요한 문제이다. 천천히 생각하고 필요한 부분을 캡슐화하여 메소드를 작성하면 된다. 코드에 사용된 변수 설명은 다음과 같다. availableLands: 배양액을 뿌릴 수 있는 Land를 저장한 리스트 selectedAvailableLands: availableLands에서 g + r개의 Land 를 뽑는 조합에 이용할 boolean 배열 selectedLands: 배양액을 뿌릴 곳으로 선택된 g + r 크기의 배열 selectedGreen: selectedLands 중 초록색 배양액을 뿌릴 곳으로 선택한 boolean 배열 time: 해당 영역에..

    [Java] 백준 3197 (백조의 호수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3197 (백조의 호수) Gold 1

    Problem : https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net Approach BinarySearch 를 이용한 BFS + 구현 문제였다. 먼저, 얼음이 며칠 뒤에 녹는지에 대한 전처리가 필요하다. (코드에서는 iceberg라고 표현했다.) 얼음에 대한 전처리는 다음 과정으로 처리하였다. findIcebergNearWater(): 물과 인접한 얼음들을 구하였다. icebergsNearWater 큐 : 이 변수는 ..

    [Java] 백준 16920 (확장 게임) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16920 (확장 게임) Gold 2

    Problem : https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net Approach BFS + 구현이 필요한 문제이다. 먼저 사용된 변수 설명을 하겠다. starts[i] : 플레이어 i 의 BFS 시작점들. s[i] : 플레이어 i 가 한번에 이동할 수 있는 거리. visited[i][j] : (i, j) 위치를 방문했는지를 표시. cnt[i] : 플레이어 i 의 땅 개수. 위 변수들을 사용한 문제 풀이 주요 로직은 다음과 같다. 플레이어의 ..

    [Java] 백준 2573 (빙산) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2573 (빙산) Gold 4

    Problem : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net Approach BFS를 이용한 구현이 필요한 문제였다. 나의 문제 풀이 주요 로직은 다음과 같다. 빙산을 Grouping 하여 빙산 그룹의 개수를 찾는다. 이 때, 빙산 그룹의 개수가 0이거나 2이상 이면 그만둔다. 모든 지점 (x, y)에 대하여 바다와 얼마나 접하는지를 oceanCnt배열에 저장한다. oceanCnt배열을 참고하여 빙산의 높이를 줄인다. 위의 과정을 종..

    [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] 백준 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] 백준 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] 백준 15683 (감시) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 15683 (감시) Gold 5

    Problem : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net Approach BruteForce(완전탐색) + 구현 문제이다. 1 ~ 5번 연산을 구현해야 하고, 연산에 필요한 CCTV가 감시하고 있는 영역을 구현해야 한다. 먼저 1 ~ 5번 연산에 필요한 공통적인 부분을 구현해야 한다. (fiilLeft(), fillRight(), fillUp(), fillDown()) 위 4개 메소드는 현재 위치 (x, y)에서 XXX 방향..

    [Java] 백준 21775 (가희와 자원 놀이) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21775 (가희와 자원 놀이) Gold 5

    Problem : https://www.acmicpc.net/problem/21775 21775번: 가희와 자원 놀이 T턴에 걸쳐서, 각 턴에 수행된 연산 카드의 id를 한 줄에 하나씩 출력해 주세요. www.acmicpc.net Approach 간단한 구현 문제이다. (본인은 간단하지 않았다.) 먼저 사용할 자료구조들을 생각해 보았다. 구현 문제에선 어떤 자료구조를 사용할 것인가가 중요한 포인트같다. 턴을 수행하는 사람의 번호 -> sequence 배열 주어진 연산카드 -> 배열 or 큐 개인공간 -> 사람마다 공간 할당(메모리 초과) -> Map 사용 (key, value) == (자원카드 번호, 소지한 사람 번호) 공용공간 -> 불필요 (Map에 없으면 다 공용공간에 있는 것) 번호가 n인 사람이 ..

티스토리툴바