본문 바로가기

파이썬127

[Python] 백준 7576번 : 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💡 문제 풀이 BFS 문제이다. BFS를 돌면서 가장 경우를 따져서 찾아내면 된다. 다 돌았는데 0이 있다면 -1을 출력하고 종료하면 되고 아니라면 가장 큰 값을 찾아서 출력하는데 1로 시작했으니 1을 빼줘야 한다. ✔️ 느낀 점 이번에 BFS/DFS를 구현하면서 많이 익숙해진 것 같다. 큰 틀 자체는 어렵지 않고 이제 어떤 방식으로 도출해 나갈지에 대해서만 생각을 하면될 것 같다.. 2022. 7. 17.
[Python] 백준 1927번 : 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 💡 문제 풀이 최소 힙 문제이다. 라이브러리를 불러와서 사용하면 된다. ✔️ 느낀 점 💻 코드 import heapq, sys input = sys.stdin.readline n = int(input()) q = [] for _ in range(n): tmp = int(input()) if not tmp: if not q: print(0) else: print(heapq.hea.. 2022. 7. 16.
[Python] 백준 12100번 : 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 💡 문제 풀이 백트래킹 문제이다. 백트래킹 자체를 구현하는 것은 하나도 어렵지 않다. 5번까지 이동 가능하므로 5번 이동했을 때 (= cnt가 5일 때) 최대 크기의 블록을 찾아서 최신화만 해주면 된다. 이 문제가 어려운 점은 이동이다. 이동에서 주의할 점이 2가지가 있다. 1. 앞의 모든 칸이 비어있다면 끝까지 이동한다는 점 2. 합치는 것은 연속적으로 일어나지 않아.. 2022. 7. 16.
[Python] 백준 1068번 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 DFS 문제이다! 우선 입력받은 값들을 딕셔너리를 이용해서 그래프화 시킨다. 이미 값들은 그래프화 시켰기 때문에 지우는 것만 따지면 된다. 스택을 이용해서 DFS를 구현한다. 지울 노드를 스택에 넣고 그 자식들을 스택에 넣으면서 차근차근 지워주면 된다. 다 지웠다면 목표 노드의 부모 노드를 for문으로 찾아 리스트에서 지워주고 (N의 범위가 50까지라서 가능하다..!) 남아있는 딕.. 2022. 7. 15.
[Python] 백준 1987번 : 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 DFS 문제이다. 재귀적으로 DFS를 구현하는데 재귀를 끝내고 나오면 이전에 포함시킨 알파벳을 지움으로 약간 백트래킹과 같은 모습을 가지게 된다. 2차원 배열로 여러 가지 경우가 생길 수 있으므로 최댓값 global 변수로 지정해 계속 최신화해준다. 느낀 점 시간 초과로 한번 수정, 또 수정 계속 수정하다가 어이가 없어서 다른 분의 코드를 보고 아스키코드로 접근해서 풀어보려고 했.. 2022. 7. 14.
[Python] 백준 10026번 : 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 BFS 문제이다. 이런 류의 문제는 항상 고민해야 하는 것이 BFS/DFS를 돌려서 어떻게 결과를 낼 것인지 이다. 우선 색약이 있는 사람과 없는 사람을 따로 구분해서 2차원 배열을 구현해줬다. 2차원 배열을 돌면서 방문하지 않은 곳을 기준으로 더 이상 이동할 수 없을 때 하나의 구역으로 인지한다. 느낀 점 DFS 문제를 풀어보려고 골랐는데 또 BFS 였다. 어떻게 탐색을 해서 .. 2022. 7. 14.

티스토리툴바