본문 바로가기

백준

 (16)
[백준 2309] 일곱 난쟁이 (c++) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 아홉 난쟁이들 중 7명을 뽑아(조합)하여 키의 합이 100인 경우를 찾는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include using namespace..
[백준 21609] 상어중학교 (C++ 풀이) https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 이 문제는 골드2 레벨의 구현 문제입니다. 문제 풀이에 주의할 사항은 다음과 같습니다. 1. 크기가 가장 큰 블록을 찾을 때 bfs 알고리즘을 이용하는데, 이 때 무지개 블록은 중복으로 사용해야 합니다. 2. 중력이 작용하는 경우 검정 블록(-1)을 만나면 거기서 블록이 멈춰야합니다 풀이 알고리즘 풀이 순서는 다음과 같습니다. 1. 가장 큰 블록 그룹 탐색 - find_largest_block..
[백준 21610] 마법사 상어와 비바라기(Python 풀이) https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 이 문제는 골드 5 난이도의 구현 문제입니다. 문제에서 제시한 방향대로 코드를 구현한다면 쉽게 풀릴 내용이지만 다음 내용만 조심하면 될 것 같습니다. 이어진 격자 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에..
[백준 23288] 주사위 굴리기 2 (Python 풀이) https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 이 문제는 '주사위 방향에 따른 이동'을 풀어내는 것과 BFS 알고리즘을 활용하면 풀 수 있습니다. 풀이 주사위 이동 주사위 이동에 대한 함수는 따로 알고리즘으로 풀어내기 보다는 케이스가 4개뿐이기 때문에 규칙을 찾아 하드코딩으로 구현하였습니다. 주사위의 이동은 좌우로 움직이는 경우와 상하로 움직이는 경우로 나눌 수 있습니다. 그림으로 표현하면 다음과 같습니다. 따라서 주사위와 ..
[백준 23290] 마법사 상어와 복제(Python 풀이) https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 이 문제는 구현 문제로 문제에서 요구한 순서에 맞게 구현하는 것이 중요합니다. 주의할 점은 다음과 같습니다. 배열의 index가 0이 아닌 1번 부터 시작하도록 되어 있습니다. 물고기의 방향 정보 또한 1~8번 까지의 정보를 가지기 때문에 헷갈리지 않도록 조심해야합니다. 물고기의 냄새가 있는 곳은 '이동'을 못하는 것입니다. 따라서 물고기가 잡아 먹혀서 물고기 냄..
[백준 8972] 미친 아두이노(Python 풀이) https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 풀이 문제 조건만 잘 확인해서 구현하면 쉽게 풀리는 문제였습니다. 입력 1 2 3 R, C = map(int, input().split(' ')) board = [list(map(str, input())) for _ in range(R)] moves = list(map(int, input())) cs 연속된 문자열 형태로 입력되기 때문에 위와 같이 map을 이용하여 list 형태로 입력받습니다...
[백준 20058] 마법사 상어와 파이어스톰(Python 풀이) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 이번 문제는 배열의 회전, BFS를 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다. 우선 다음과 같이 입력을 받습니다. N, Q = map(int, input().split(' ')) # N, Q len_board = 2 ** N # 얼음을 저장할 보드의 길이 board = [list(map(int, input().split(' '))) for _ in range(le..
[백준 16985] Maaaaaaaaaze(Python 풀이) 풀이 이 문제는 브루트포스, 순열, BFS를 이용하여 풀어야한다.(이외에도 배열 회전 알고리즘 등 복잡한 문제이다.) import sys from collections import deque from itertools import permutations board = [[list(map(int, input().split(' '))) for _ in range(5)] for _ in range(5)] b = [[[0] * 5 for _ in range(5)] for _ in range(5)] result = sys.maxsize dh = (0, 0, 0, 0, 1, -1) dy = (0, 0, 1, -1, 0, 0) dx = (1, -1, 0, 0, 0, 0) 다음과 같이 입력을 받고, result, dh..
[백준 1202] 보석 도둑(C++ 풀이) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다. 우선 보석의 정보와 가방의 정보를 담을 배열 그리고 우선순위 큐를 다음과 같이 정의한다. pair v_jewerly[MAX]; int v_bag[MAX]; priority_queue pq; 원래는 vector 자료형을 사용했었는데, 배열 최대크기(MAX = 300001)가 너..
[백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 더보기 우선 NxN 형태의 2차원 벡터를 이용하여 어항의 배치를 표현하였으며, 어항이 존재하지 않는 좌표는 -1로 표현하였다. 그리고 문제에서는 어항이 위로 쌓이게 되지만 편의상 배열의 아래로 쌓이도록 표현하였다. 따라서 위 그림을 배열로 표현하면 다음과 같다. 코드 상에서는 board라는 변수를 사용한다. 1 2 3 4 5 6 7 8 -1 -1 3 14 9 3 11 8 -1 -1 3 5 -..

티스토리툴바