백준

https://www.acmicpc.net/problem/1012문제분석이전에 푼 문제중 이와 비슷한 문제가 있었다.배추가 묶인 덩어리들의 갯수가 몇개인지 구하는 것이다.해결과정DFS를 이용하였다. 현재로써 나에겐 DFS를 직접 의도해서 구현 후 해결한 몇 안되는 문제이다. 처음에는, 해당하는 배추 좌 우에 다른 배추가 있으면 숫자를 조절하는 방식으로 진행하려 했다.그러나 이 방식에는, (기존 배추) - 배추 - (기존 배추)로 연결이 되는걸 커버하지 못한다.따라서 dfs를 활용해서, 덩어리의 갯수를 직접적으로 세기로 했다.arr에 저장한 후, 이 arr에서 첫번째 배추를 기준으로 재귀 dfs를 실행한다.이는 while을 통해서 arr이 0이 될 때까지 반복된다. 문제에서, 좌표(배추농장)의 가로세로 길..

https://www.acmicpc.net/problem/1182문제분석부분수열의 합이 제시한 값과 일치한 경우가 몇번?!해결과정백트래킹에 대해 배우고, 구현해보았다.부분수열은 곧 부분집합이라고 볼 수 있으니, 문제를 "부분집합의 합"이라고 생각해도 될 듯 하다.결국, 모든 부분집합 각각의 합을 계산하고 주어진 값과 비교하는 것 이다.더보기주어진 집합이 7,3,-1 이라면7 / 3 / 1 / 7,3 / 3,-1 / 7,-1 / 7,3,-1 을 구하고, 이 부분집합들의 합을 구해야 함.모든 부분집합을 구하는 방법을 생각해보니어떠한 값+그 뒤에 값들(여기는 1개~가능한 최대까지)을 전부 세면 된다.그 뒤에 값이 2개이상이면...?이를 해결하기 위해 재귀와 백트래킹을 활용한다.이 모든 경우를 다 따지기 위해...

https://www.acmicpc.net/problem/1018문제분석W와 B로 주어진 판에서, 최소한으로 뒤집어서 체스판을 만들 수 있을 때 그 최소값을 구하는 문제이다.해결과정8*8 체스판을 구하는 것 이므로, N*M판에서 우리가 봐야 할 첫번째 칸의 위치는 (N-8)*(M-8)에 위치한다.첫번째 체스칸의 색을 기준으로 나머지 모든 칸의 색이 정해지므로, 첫번째 색과 같은지 다른지 확인하면 될 것이라고 생각했다.구현이 은근 어렵다. 구현해놓고 나서, 시간 초과 뜨면 접으려고 했는데 다행이 정답 떠줬다...ㅠㅠfrom sys import stdindef input(): return stdin.readline().rstrip()N,M=map(int,input().split())arr=[] # W는..

https://www.acmicpc.net/problem/18111 문제분석블럭이 지형을 이루고 있을때, 최단 시간 내에 평탄화하는 방법. 그때의 최대 높이를 구하시오.해결과정처음에는 높이별로 블럭을 누적시키려고 하였다(예를들어, 높이 3 블럭은 리스트[1]=1 리스트[2]=1 리스트[3]=1로 저장함으로써, 리스트[n]에는 n에 존재하는 블럭 수 를 저장하려고 하였다.from sys import stdindef input(): return stdin.readline().rstrip()N,M,B=map(int,input().split())ground_extent=N*M# height[n]은, 높이 n에 존재하는 블럭 height=[0]*256ground_block_sum=0max_height=0 #..

https://www.acmicpc.net/problem/18870 문제분석너무 너무 단순한 문제라고 생각했다. 그냥 정렬하고 인덱스 출력하면 되는게 아닌가?그런데...자꾸 시간초과가 났다.처음엔, 논리적으로 시간 복잡도를 줄일 수 있는 방법이 있는줄 알고 많은 시도를 했다...그러나 생각보다 예상치 못한 곳에서 시간 복잡도를 줄일 수 있다는걸 배웠다. 파이썬에서 딕셔너리(dictionary)에서 삽입, 갱신, 탐색 평균 시간 복잡도는 O(1)  +set 자료형도 중요했다.해결과정from sys import stdindef input(): return stdin.readline().rstrip()N=int(input())nums = list(map(int,input().split()))# nums정..

https://www.acmicpc.net/problem/7570문제분석제목 그대로 순서대로 줄을 세우는 것이다. 단, 맨 앞이나 맨 뒤로만 보낼 수 있다는 조건을 지켜야 한다.예를들어, 5 4 2 3 1로 서있는 경우, 1을 맨 앞으로,  4를 맨 뒤로, 5를 맨 뒤로 보내야 1 2 3 4 5로 정렬이 된다.최소한으로 움직여서 정렬이 완료되는 경우, 그 최소한으로 움직인 값은?해결과정"덩어리" 를 만들기로 했다. 여기서 "덩어리" 의 정의는 다음과  같다.1. 연속적인 수(3, 4, 5, 6...)2. 이 수들은 붙어있을 필요는 없다(3, 5, 2, 6, 1, 7, 4...)->덩어리 5,6,73. 최소한으로 움직이는 경우는, 이 덩어리들 중  가장 큰 덩어리가 움직이지 않는 경우.이 덩어리가 가장 클..

https://www.acmicpc.net/problem/1034문제분석가로로 111111...와 같이 모든 수가 1로 바뀌어야 켜졌다 라고 한다고 한다. 버튼을 누르면 해당 열 의 모든 숫자가 바뀐다(1과 0 서로 치환).역시 간단한 방법인 모든 경우를 탐색하려고  하니, 신경써야 할 반례가 너무 많았다. 다른 방법이 있나 찾다가, 이전 문제에서 사용했던, 순차적으로 탐색하면서 최대값을 저장하고, 최댓값보다 큰 경우에 최댓값을 갱신하는 방법을 사용하기로 하였다. 램프가 켜지고 꺼지면서 완성되는 열의 수를 각각 파악해야 한다(실제로 숫자를 변경하면, 시간복잡도에서 탈락).해결과정중복이 가능하므로, K의 갯수와 한 행의 0의 갯수의 홀수 짝수 여부가 같아야 한다(다른 경우, 무조건 한번 더 눌러야 하므로 ..

https://www.acmicpc.net/problem/2528 2528번: 사다리 첫 번째 줄에 층 수 N (1 ≤ N ≤ 3,000)과 층의 길이 L (1 ≤ L ≤ 3,000, L은 짝수)이 주어진다. 가장 아래층은 1층이고 가장 위층은 N층이다. 다음 N개의 줄 중 i번째 줄에는 i층의 막대기의 길이 l (1 ≤ l www.acmicpc.net 문제분석 문제 요약: 게임을 연상하면 편하다. n개의 층이 있고 층의 가로길이도 주어준다. 막대기는 좌우로 움직인다(게임처럼 반대편끝에 부딛히면 반대방향으로 감). 막대는 1시간단위마다 1칸씩 움직인다. 철수는 맨 아래층 막대에서 위로 올라가려고 하는중이다. 철수는 좌우이동하는데 시간을 소모하지 않는다. 막대기 좌표가 위아래 겹치는 경우에 철수는 위아래 ..