bruteforce

    [Java] 백준 17089 (세 친구) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17089 (세 친구) Gold 5

    Problem : https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net Approach BruteForce(완전탐색) 문제이다. 먼저 입력을 받으면서 관계 배열 relations 을 구성한다. 또한, 특정 사람의 친구의 수를 기록한다. 세 친구 A, B, C 를 A = 0, B = 1, C = 2부터 시작하여 세 친구 ABC가 모두 친구인 경우를 찾고, 그 때의 최대 친구 수를 찾으면 된다. ABC의 친구를..

    [Java] 백준 14502 (연구소) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14502 (연구소) Gold 5

    Problem : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Approach 완전탐색(BruteForce)과 BFS를 함께 사용하는 문제이다. 문제 풀이 주요 로직은 다음과 같다. 0인 곳들 중 3군데를 골라서 벽을 세운다. 벽을 3개 세웠으면 그 상태에서 BFS를 수행하여 바이러스를 전파시킨다. 전파 시킨 뒤에 0의 개수를 찾는다. 모든 경우를 다 탐색하여, 안전한 구역의 최대 개수를 구한다. Code import java.io.*; import j..

    [Java] 백준 1062 (가르침) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1062 (가르침) Gold 4

    Problem : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net Approach 조합(Combination)을 이용한 완전탐색(BruteForce)문제이다. 처음에는 조합을 list로 구현하였으나, 시간초과를 받았다. 그래서 총 알파벳의 개수인 26 크기의 배열을 가지고 사용 여부를 체크하며 조합을 구성하였다. 조합을 구현하기 전에 입력에 따라 간단히 처리할 수 있는 부분들을 짚어보자. N은 주어진 단어의 개수, K개 만큼 문자를 배울..

    [Java] 백준 16198 (두 동전) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16198 (두 동전) Gold 4

    Problem : https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net Approach 백트랙킹(Backtracking)을 이용한 완전탐색(BruteForce)문제 이다. BFS로도 풀이가 가능할 것 같다. 먼저 두개 동전의 위치를 찾는다. (입력으로 map을 구성하면서 찾을 수 있다.) 그리고 다음 작업을 반복한다. 두 동전을 상하좌우 방향으로 굴려본다. 굴렸을 때 3가지 상황이 발생한다. 두 동전이 모두 떨어지면 더 이상 굴려보지 않는다. (돌..

    [Java] 벡준 1248 (맞춰봐) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 1248 (맞춰봐) Gold 3

    Problem : https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net Approach Backtracking을 이용하여 완전탐색(BruteForce)를 수행하는 문제이다. 이 문제에서 주의할 점을 좀 적어보겠다. 중복된 수로 수열을 만들 수 있다. 숫자 0 과 문자 '0'은 다르다. 수열을 완전히 만들고 검사하는 것이 아니라, 만드는 과정에서 검사가 이루어져야 한다. 먼저 주어진 문자열로 i ~ j까지의 합의 상태를 나타낸 s[i][j..

    [Java] 백준 17281 (⚾) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17281 (⚾) Gold 4

    Problem : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net Approach BruteForce 문제이다. 순열(Permutation)을 활용하여 생길 수 있는 모든 경우의 수를 생각한다. 순열의 크기가 8이라서 가능한 일이다. 1번 타자 ~ 9번 타자까지 순서를 정해야한다. 하지만 4번 타자의 경우 이미 정해져있기 때문에 8명만 줄을 세우면 된다. 전체적인 로직은 다음과 같다. 1번타자 ~ 9번타자를 정한다. 야구게임을 시작한다. 주어진 이닝..

    [Java] 백준 17136 (색종이 붙이기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17136 (색종이 붙이기) Gold 2

    Problem : https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Approach BruteForce + DFS + Backtracking 문제이다. DP로도 풀 수 있을까 고민했지만, 색종이의 개수 제한도 있고 개수를 어떻게 세야할 지 감이 안와서 다른 방법을 생각했다. 색종이를 붙일 수 있는 모든 곳에 대해서 색종이 사이즈가 5, 4, 3, 2, 1인 색종이를 붙일 수 있는지 각각 검사한다. 현재 사용한 색종이의 개수가 최솟값보다 ..

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

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

    Problem : https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net Approach 입력값이 크지 않아, DFS + BruteForce로 풀이가 가능한 문제이다. 중첩된 괄호는 허용하지 않으므로, 주어진 식의 앞에서부터 괄호를 씌운 경우와 씌우지 않은 경우 두가지 경우를 모두 고려한다. 그렇게 가지를 치며 모든 경우를 조사한다.(BruteForce) 그중 가장 큰 결과값을 내는 값들을 ans에 갱신한다. Code import ja..

    [Java] 백준 1107 (리모컨) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1107 (리모컨) Gold 5

    Problem : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net Approach BruteForce 문제이다. 우선 0부터 목표 채널 * 2 까지 만들 수 있는 숫자인지를 판단하고, 만들 수 있는 숫자라면, 숫자를 만들 때의 클릭 수와 만든 숫자와 목표 채널과의 차이(+-클릭 수)를 더한 것들 중 최솟값을 찾으면 된다. 주의할 점은, 시작 채널이 100이기 때문에 최소 100까지는 숫자를 만들 수 있는지 판단해야 한다. isP..

    [java] 백준 17472 (다리 만들기 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 17472 (다리 만들기 2) Gold 3

    Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..

티스토리툴바