분류 전체보기
-
[백준] 3184번 양문제 풀이 2020. 3. 28. 14:21
3184 양 문제미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.아침이 도달했을 ..
-
[백준] 2251번 물통문제 풀이 2020. 3. 27. 19:45
2251 물통 문제각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오. 입력첫째 줄에 세 정수 A, B, C가 주어진다. 출력첫째 줄에 공백으로 구분하여 답을 출력한다..
-
[백준] 1026번 보물문제 풀이 2020. 3. 27. 17:00
1026 보물 문제옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.S = A[0]*B[0] + ... + A[N-1]*B[N-1]S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.S의 최솟값을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다. 출력첫째 줄에 S의 최솟값을 출력한다. 풀이)처음..
-
복잡도 표기법잡다한 지식 2020. 3. 27. 13:41
알고리즘을 분석하는 방법은 시간 복잡도와 공간 복잡도로 나뉜다.- 시간 복잡도 (time complexity) : 알고리즘이 완료되는데까지 소요되는 시간- 공간 복잡도 (space complexity) : 알고리즘이 완료되는데까지 필요한 메모리 공간 이러한 복잡도의 표기방법으로는 총 3가지가 존재한다.1. 빅오메가(Big-Omega)2. 빅세타(Big-Theta)3. 빅오(Big-O)이 표기법들을 점근적 표기법 즉 대략적인 표기법이라고 한다.n을 알고리즘의 input의 크기라고 할 때.알고리즘의 복잡한 함수를 일일이 나타내지 않고, 알고리즘의 basic operation을 선택해 basic operation의 수를 n에 대한 비례식으로 세우는 것이다. (중요하지 않은 항과 상수 계수를 제거) 각 표기방법..
-
brute force알고리즘 2020. 3. 26. 21:39
Brute Force 브루트 포스 - 개념 : brute "난폭한, 무식한"이라는 뜻이고, brute-force는 "무식한 힘, 폭력" 이라 해석할 수 있다. 영어 뜻처럼 단순무식한 알고리즘 방식이다. 완전 탐색 알고리즘(Exhaustive Search) 이라고도 한다. 가능한 모든 경우의 수를 탐색하면서 문제를 해결하는 방법이다. - 사용 : 선형 구조에서는 순차 탐색, 비선형 구조에서는 깊이우선탐색(dfs), 너비우선탐색(bfs)가 있다. - 장&단점 장점 : 만들기가 쉽고, 다른 알고리즘을 구현하기 전 기본이 되어 주는 알고리즘이다. 단점 : 시간면에서 비효율적이다. - 무식한 방법이지만, 공간과 시간이 충분하다면 당연히 정확도 100%를 보장한다. - 예시문제로 백준 15683 & 15684 같은..
-
[백준] 15684 사다리 조작문제 풀이 2020. 3. 26. 21:15
15684 사다리조작 문제사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.사다리 게임은 각각의 세로선마..
-
[백준] 15683번 감시문제 풀이 2020. 3. 26. 20:08
15683 감시 문제스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.1번2번3번4번5번1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.CCTV는 회전시킬 수 있는데,..
-
[백준] 14499 주사위 굴리기문제 풀이 2020. 3. 26. 01:34
14499 주사위 굴리기 문제크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다.지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의..