문제 설명 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(..
문제 설명 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 문제 풀이 처음에는 2차원 배열로 풀라고 했는데... 배열 인덱스들이 너무 헷갈려서 끙끙대고 있을 때 같이 푸는 친구에게 아이디어를 듣고 풀어보았다 2차원 배열로 생각하지 말고, 사각형을 일자로 쭉- 펴서 풀어보라는 것 그렇게 1차원 배열로 생각해서 풀었더니 쉽게 풀렸다! w, h = list(map(int, input().split())) n = int(input()) store = [li..
문제 설명 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 시간초과 때문에 힘들었던 문제.. 이게 파이썬의 한계인가 처음에는 count가 n일 때 route 배열에 있는 순서대로 cost를 더해주면서 값을 구하고, 총 비용과 minCost를 비교하는 방법으로 코드를 짰었는데 시간초과가 걸렸다 파라미터로 cost를 더하면서 넘겨주고 minCost와 파라미터로 넘어온 cost를 비교해서 더 낮..
문제 설명 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 풀이 turn 메소드를 통해 반시계 방향과 시계 방향으로 돌려주는 작업을 해주었다. 인덱스로 확인하기 때문에 회전하는 톱니를 받고 -1를 해주었고(n -= 1) d 배열로 톱니마다 방향을 저장해주었다. 처음에는 if문으로 1번 톱니일 때, 2번 톱니일 때,,, 하나씩 처리해주려고 했는데 if문 중첩이 너무 많아져서 어지럽길래 다른 방법을 생각해보았다. 왼쪽으로 확인해야 될 톱니..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1차원 배열 bfs 문제 target이 없으면 return 0을 해주어 변환할 수 없는 경우에 시간을 줄여주었다 한 번에 한 알파벳만 바꿀 수 있다는 규칙이 있어 알파벳이 다른 개수를 구해주는 cnt 함수를 만들어주었고 달라진 알파벳이 1개이면 True를 리턴해주었다 큐를 돌아가면서 cnt 함수 return 값이 True면 현재 visited값과 이전 visited에서 1을 ..
문제 설명 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 1로 만들기와 똑같은 문제인데 여기서는 과정을 출력해야 한다 (경로 추적) 처음에는 i마다 i를 1로 만드는 과정들을 2차원 배열로 저장하고, 이전 단계의 배열을 복사해와서 거기에 append를 통해 모든 i의 과정을 저장하는 방법을 사용하였다 n까지 다 구해지면 n을 1로 만드는 과정이 담긴 배열을 reverse 한 후 len과 함께 출력했는데 시간초과... 아마 배열을 복사하는 과정에서 시간초과가 났던 것 같다 시간 초과가 나와서 다른 방법을 생각했다 어디서 왔는지 경로를 추적..
문제 설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 테이블을 생각할 때 최소비용을 저장하는 1차원 배열로 정의해서 점화식을 생각해봤는데 아무리 생각해도 점화식 구하기 너무 힘들 것 같아서 2차원 배열로 정의했다 점화식 d[i][0] = min(d[i - 1][1], d[i - 1][2]) + cost[i][0] d[i][1] = min(d[i - 1][0], d[i - 1][2]) + cost[i]..
