구빙그르르르

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 한줄 이해 - 그래프에 공기청정기와 미세먼지들이 있을때 1초동안 하는 일련의 과정이 진행되고 총 미세먼지 양을 구하기 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 1초동안 어떤 과정들이 이루어지는지 파악 1-2. 각 미세먼지들이 상하좌우로 퍼진다. -> 먼지들이 있는곳을 큐에 담아 상하좌우 탐색하기 1-3. 그런다음 공기청정기에 의해 미세먼지들이 이동한다. -> 그래프..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 한줄 이해 - 주어진 노드들 사이의 최소 거리를 구하고 제시된 거리보다 낮은 곳을 방문해 최대한 많은 양의 아이템을 구하는 경우를 출력하기 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 각 노드들 사이의 최소거리 구하기 why? 문제에서 예은이는 정해진 범위 m만큼만 이동 할 수 있다고 한다. 2. 각 노들드의 아이템 수를 담을 리스트를 따로 만들어 놓기 3. 어떤 노드에 예은..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 한줄 이해 - 나와 동생의 위치가 주어지고 1초 뒤에 +1, -1 ,*2의 위치로 이동 할 수 있을 때 동생의 위치로 가는 빠른 시간과 빠른 시간의 경우의 수 구하기 생각난 풀이 1번째 방법: 현재 위치에서 1초뒤에 3가지 경우로 뻗어 나간다. 또한 뻗어 나간 그 위치에서도 각각 3가지 경우로 뻗어 나가는 상황을 생각하면 그래프 탐색이 떠올랐다!! 그래서..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 한줄 이해 - 주어진 수열에서 가장 긴 바이토닉 수열 찾기 생각난 풀이 1번째 방법: 이전에 풀이한 가장 긴 증가하는 부분 수열문제가 떠올랐고 이를 활용해보도록 했다. 바이토닉 수열은 계속 증가하거나 계속 감소하거나 계속 증가하다가 작아지는 순간에 계속 작아지는 수열이다. 그래서 디피를 활용해 0인덱스 에서부터 계속 증가하는 가장 긴 부분수열을 찾고 거꾸로 맨 뒤 인덱스에서부터 계속 증가하는 가장 긴 부분수열을..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 한줄 이해 - 문자열이 있을 때 이 안에 폭발문자열이 들어 있으면 폭발해 해당 폭발 문자열이 삭제 되고 사라진다. 이때 최종 문자열 출력하기 생각난 풀이 1번째 방법: 먼저 문자열에서 폭발 문자열을 기준으로 split함수를 사용해 while 반복문을 통해 폭발문자열이 들어있지 않을때까지 연산하려고 했다. import sys senten = sys.stdin.readline()...

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 - N*N 격자판에서 퀸 N개가 서로 공격할 수 없도록 놓는 경우의 수 구하기 생각난 풀이 1번째 방법: 싸피 코딩테스트 준비하면서 swea사이트에서 풀었던 문제와 비슷하다고 생각이 났다. 우선 이전 줄에 퀸을 놓았을때 다음 줄에 어떤 칸에 퀸을 놓을수 있는지 판단하면 된다. 어떤 칸에 놓을 수 있는지 판단 아이디어는 다음과 같다. 퀸의 특성을 보면 대각선과 상하좌우로 이동이 가능한 특징을 가지고..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 한줄 이해 - 별이 출력된 예제를 보고 규칙을 유추하기 생각난 풀이 1번째 방법: 어떤 규칙들이 있는지 생각했다. 1. 크게 일정 모양의 틀이 반복된다 -> 재귀다! 2. 입력되는 n이 무엇을 의미할까 -> 처음에는 일정하게 나타나는 삼각형 수인가? 삐이이이 ! -> 총 몇줄인지 인가? 그럴싸했다. 그렇다면 n의 따라 그래프가 그려지는건가? 라는 생각이 들었다. -> 출력예제의 가로 길이도 확인하니 세로의 2배를 차지한다. -> 그렇다면 그래프..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 한줄 이해 - 1행 1열에서 시작해서 그래프를 탐색할 때 이미 지나온 알파벳이 없는 곳으로 이동하면서 최대 몇번 가능한지 구하기 생각난 풀이 1번째 방법: 첫번째로 현재위치에서 상하좌우 이동하기 두번째로 상하좌우 이동하기 전 이미 지나왔던 알파벳인지 판단하기 import sys r,c = map(int,sys.stdin.readline().split()) graph = [] for i..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 한줄 이해 - 트리가 있을 때 어떤 두 노드를 잡고 댕겼을때 가장 긴 지름 구하기 생각난 풀이 1번째 방법: 처음에는 가중치를 더해가면서 다익스트라를 응용하면 될거라 생각했다. 이유는 다익스트라 개념은 결국 최장거리 구하기 등의 이론이 들어가는데 여기서 낮은 값이 아닌 큰값을 더해가면서 거리를 계산하면 된다고 생각했다. import sys import heapq n = i..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 한줄 이해 - N*N인 도시가 있을때 0 은 빈칸 1은 집 2 는 치킨집으로 이루어져 있을 때 m개의 치킨집을 골라 모든 집에서의 치킨 거리가 가장 짧은 경우를 구하기 생각난 풀이 1번째 방법: 백트래킹이 떠올랐다. 주어진 치킨집 중에서 m개를 골라야하기 때문이다. 이때 거리라는 것은 (x1,y1), (x2,y2)가 있을 때 가장 가깝다는 것은 |x1-x2| + |y1-..