본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 14595 동방 프로젝트 (Large) 문제 출처 : www.acmicpc.net/problem/14595 14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net 동아리방을 합치는 연산이 여러번 주어졌을때, 이 연산이 모두 끝난후, 남아있는 방의 수를 출력하는 문제다. 풀이 시간초과를 피하기위해 유니온파인드를 이용해서 풀어야한다. 방이 총 5개있을때, 각 방은 이런식으로 떨어져있을것이다. (예제 1) 이때, 1번방과 2번방을 합치는 연산을하면 1번방과 2번방은 같은방이되는데, 그걸 이렇게 연결..
[백준 / BOJ] 14699 관악산 등반 - Swift 문제 출처 : www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net N개의 쉼터가 있고, 쉼터둘을 연결하는 M개의 도로가 있다. 각 쉼터에는 높이가 있으며, 항상 현재쉼터보다 높은위치로만 갈수있다고할때, 각 쉼터에서 최대한으로 방문할수있는 쉼터의 갯수를 구하는 문제다. 풀이 전에 풀었던 Dp+DFS문제인 욕심쟁이 판다 : www.acmicpc.net/problem/1937 와 비슷한 유형?의 문제라고 생각했다 *항상 현재 쉼터 보다 높은 쉼터로만 ..
[백준 / BOJ] 2872 우리집엔 도서관이 있어 문제 출처 : www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 상근이가 책을 정리할려고한다. 책은 1 2 3 4 5 ... N 순서대로 정리해야한다. 책을 정리하는 방법은 임의의 책 한권을 뽑아서 가장 앞에 놓는다. 최소 몇번의 이동으로 책을 정리할수있는지 출력하는 문제다. 풀이 i번째 책이 i+1번째 책보다 낮은위치에 존재하는지 확인해주며 풀면 되는 문제다. 예를들어, 9 1 2 3 4 5 7 6 8 9 의 책이 있다고 하자. (9번은 움직이지 않아도..
[백준 / BOJ] 2174 로봇 시뮬레이션 문제 출처 : www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 로봇의 위치와 각 명령이 주어졌을때, 시뮬레이션을 안전하게 돌릴수 있는지 확인하는 문제다. 명령은 다음 3개가 있다. L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다. R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다. F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다. 로봇이 명령을 수행하다가 다른로봇 혹은 벽과 충돌할경우..
[백준 / BOJ] 19942 다이어트 문제 출처 : www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 식재료 N개중 몇개를 선택해서 이들의 영양분(단백질 탄수화물 지방 비타민)이 일정이상이 되어야한다. 각 식재료에는 가격이있다. 이때, 가격을 최소로하는 식재료 조합을 찾는 문제였다. 풀이 완전탐색으로 풀은 문제다. 탐색마다 영양소를 선택하는 경우, 선택하지 않는경우로 총 2가지 선택지가 있으므로, 최대 반복횟수는 2^15가 된다. 풀이는 간단한데, 단백질 탄수화물 지방 비타민 이 있을때, 각각의..
[백준/BOJ] 11560 다항식 게임 문제 출처 : www.acmicpc.net/problem/11560 11560번: 다항식 게임 매 테스트 케이스마다 한 줄에 걸쳐 다항식 \(p(x) = (1+x)(1+x+x^2)(1+x+x^2+x^3)\dots(1+x+\dots+x^{k-1}+x^k)\)의 \(x^N\)항의 계수를 출력한다. www.acmicpc.net k에 따라 다항식이 연결된다. k = 0 (1) k = 1 (1)(1+x) k = 2 (1)(1+x)(1+x+x^2) k = 3 (1)(1+x)(1+x+x^2)(1+x+x^2+x^3) . . . k = ? 일때의 다항식을 계산한 결과에서 N차항의 계수를 출력하는 문제다. 풀이 k = 20 , N = 210까지 간다. k가 늘어남에따라, 곱해야하는 항의 차수 또한 매우 늘어나므로, 완탐으..
[백준 / BOJ] 15906 변신 이동 게임 문제 출처 : www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 성호는 새로운 모바일 게임을 다운로드 했다. 성호의 캐릭터는 N*N의 위치에서 상,하,좌,우로 1칸 움직일수있는데, 이때, 캐릭터가 변신모드라면, 상,하,좌,우중 가장 가까운 워프지점으로만 갈수있다. (변신모드로 전환하는데는 t만큼의 턴이 소요된다.) 성호의 캐릭터가 목표지점까지 도달하는데 걸리는 최소한의 턴을 구하는문제다. 풀이 다익스트라로..
[백준 / BOJ] 9663 N-Queen 문제 출처 : www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N*N의 체스판에 N개의 퀸을 서로 공격할수없도록 배치해야한다. 이때, 퀸을 놓는 경우의 수를 구하는 문제다. 풀이 N의 최댓값이 15이다. 따라서, 최악의경우 15 * 15의 판에 15개의 퀸을 놓는 경우이므로, 15! * 15^3 만큼 반복하게된다. 따라서, 모든경우를 봐줄려하면 시간초과가 나게된다. 시간초과를 피하기 위해서 체크배열을 이용해서 해당 위치에 퀸을 놓을수있는지 없는지 봐줘야한다. 퀸은 가로 세로..

티스토리툴바