전체 글

문제 설명 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 성능 요약 메모리: 46628 KB, 시간: 4280 ms 분류 그리디 알고리즘, 정렬 제출 일자 2024년 3월 24일 03:36:32 문제 설명 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. ..

문제 설명 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 성능 요약 메모리: 34096 KB, 시간: 524 ms 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션 제출 일자 2024년 3월 22일 02:51:49 문제 설명 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내..

문제 설명 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 288 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 3월 22일 02:24:34 문제 설명 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 입력 첫째 줄에 ..

문제 설명 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 6464 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2024년 3월 19일 02:14:35 문제 설명 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱..

그리디 알고리즘 (탐욕 알고리즘) : 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 : 관찰을 통해 탐색 범위를 줄이는 알고리즘 그리디 알고리즘이 최적의 답을 보장해주는 문제 1. 최적 부분 구조 - 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것 2. 탐욕적 선택 속성 - 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택

문제 설명 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 풀이 처음에는 치즈의 구멍을 고려하지 않고 문제를 풀었더니 당연히 실패 ... 공기가 있는 부분을 탐색하는 BFS랑, 치즈 조각을 탐색하는 BFS로 두 개의 함수를 사용하였다. 치즈 조각을 탐색하면서 근처에 공기가 한 칸이라도 있으면, set에 넣은 후 치즈가 녹는 부분들을 공기로(0으로) 만들어주었다. 그 후 공기 탐색 BFS 때 음수로 처리해주었던 공기 칸들을 다시 0으로 만들어주었다...

문제 설명 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 높이까지 있는 BFS문제다. dx, dy, dh로 각각 이동하는 범위를 설정하고 queue를 돌면서 확인해줬다-! from collections import deque M, N, H = list(map(int, input().split())) tomato = [[list(map(int, input().split())) for _ in range(N)] ..

문제 설명 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 1592 ms 분류 백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 3월 8일 01:32:29 문제 설명 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 ..

문제 설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 성능 요약 메모리: 40628 KB, 시간: 148 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 3월 6일 01:34:27 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽..

문제 설명 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 풀이 사실 문제에서 나온 대로 구현만 하면 되는데 좌표가 자꾸 헷갈려서 오래 걸렸던 문제.. 그래도 이 문제를 풀고 나니 좌표에 대한 감이 어느정도 잡혔다 n, m = list(map(int, input().split())) r, c, d = list(map(int, input().split())) board = [list(map(..