똥그래미 코딩공장

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제는 수월하게 가다가 "예제 입력 3" 조건에서 막혔다. 1이 2개가 있어서 이거를 차례대로 번갈아가면서 수행을 해줘야 하는데 어떻게 해야하지 고민을 오래했다. 그러다 bfs의 특징인 deque의 특징이 생각났다. 큐의 특징은 FIFO(first-in-first-out)이다. 즉, 내가 원하는 차례대로 번갈아가면서 수행이 가능하단 것이다. 지금까지는 bfs문제에서 큐 삽입을 ..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 어렵지 않게 풀어 낼 수 있던 bfs 문제였다. 문제에 특이사항이 있지않아 별다른 코멘트는 하지 않겠다. 전형적인 bfs 문제의 유형이다. 설명은 아래 주석에 남겼다. import sys from collections import deque T=int(input()) dx = [1,-1,0,0] #상하 dy = [0,0,1,-1] #좌우 def bfs(graph,a,b): q=deque() q.append((..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 지금까지 풀었던 bfs 문제와 유형이 달랐다. 지금까지는 좌표를 상하좌우로 이동하여 푸는 문제들이였는데 이 문제는 상하좌우가 아닌 -1,+1,*2 이 3가지의 방향으로 이동한다. 좌표도 필요가 없는 문제였다. 문제를 보고 그래프가 머리에 그려지긴 했지만 지금까지 풀던 문제와 달라 조금 당황했다. 그리고 시간초과가 나는 이유도 몰랐다가 다른 분들의 풀이를 참고해 이유를 알..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 하아... 다시 또 벽을 느낀 문제였다. 이젠 거의 다 안다고 생각했는데 그러지 못했다. 문제의 접근 방식이 틀렸었다. 결국 다른사람의 코드를 참고했다. 아직 갈길에 먼거같다... import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline N = int(input()) a,b = map(int,input().split..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 내가... 내가..... 드디어... 그래프탐색 문제를 25분만에 풀었다. 캬 기분이 좋았다. 문제 체감 난이도도 이제 크게 느껴지지 않는다. 한 5분정도 삽푼거 빼곤 스무스 하게 풀었다. 난 이 문제의 접근을 그림과 똑같이 가져가진 않았다. 그림에선 왼쪽 아래 부터 (0,0)으로 시작하였다. 그러나 우리는 평소에 왼쪽 위부터 시작하기 때문에 난 내 방식대로 그래프를 그렸다. ..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 오우 부모찾기라니... 상당히 어려웠다. 체감상 골드였다. 도저히 생각이 나지않아 다른사람의 코드를 보았다. 보면 이해가 갔지만 생각해내진 못했을거 같다. 오늘도 DFS에게 맞고 간다.. 다음은 때리는 내가 되길....ㅠ import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) #재귀제한을 늘려준다 N = int(input()) graph = [[]*(N+1) for _ in range(N+1)] ..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 후.... 메모리 초과만 6번이 뜬 문제였다. 상당히 까다로웠지만 역시나 별거 아닌것이 문제였다. 이번 문제를 통해서 코드 순서의 중요성에 대해 다시 한번 더 깨닫게 되었다. 설명은 아래 코드의 주석을 참고하겠다. import sys from collections import deque input = sys.stdin.readline N = int(input()) graph = [] dx=[1,-1,0,..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이번 문제는 이동방향이 상하좌우가 아닌 대각선방향으로 되어있다. 즉 기존의 4개의 방향에서 8개의 방향으로 늘어난거다. 그렇기 때문에 이동방향또한 8개로 선언해서 풀어준다. 그외의 요소들은 기존 bfs 문제들과 동일하게 풀었다. 설명은 아래 코드의 주석을 달아놓았다. import sys from collections import deque input = sys.stdin.readline T = in..