구빙그르르르

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-..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 한줄 이해 - N*M 크기의 연구소에 바이러스(2), 벽(1), 빈칸(0)이 있을때 벽 3개를 새로 세워 바이러스가 퍼져나간뒤 안전한 칸이 제일 많은 경우를 구하기! 생각난 풀이 1번째 방법: 먼저 백트래킹이 떠올랐다. 현재 그래프 상태에서 벽을 새로 3개를 세우는 경우를 판단하기 위해서이다. 그런 다음 백트래킹의 종료 조건절에서 BFS 탐색을 통해 바이러스가 퍼지게 한 후 안전한 칸을 카운팅했다!!! ..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 한줄 이해 - 전휘 순회로 출력된 결과를 가지고 후위 순회한 결과 뽑기 생각난 풀이 1번째 방법: 먼저 전회 순회를 통해 루트를 기준으로 루트보다 큰 값을 만나는 순간 왼쪽 오른쪽으로 나눠진다는 것은 알아냈지만 이를 어떻게 활용해야할까 고민을하다가 계속 파고드네????? 재귀를 써야하나??? 접근해봤다. 예제를 보면 50 30 24 5 28 45 98 52 60 이렇게 전회 순회..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 한줄 이해 - N줄에 3개의 숫자가 쓰여져 있을 때 첫줄 부터 숫자를 선택해 더해나가면서 최소와 최대인 경우 구하기 생각난 풀이 1번째 방법: 며칠전에 RGB거리 문제랑 비슷한 느낌인데 라는 생각에 다이나믹프로그래밍을 떠올렸다. 이때 그때의 아이디어랑 똑같이 풀면 되겠는데? 라는 생각했다. 먼저 수를 고를때 이전에 더해진 값들이 저장된 dp 값중에서 최대와 최소를 구해가자라고 생각했다. 이때 각자리를 선택..