코딩테스트 대비 백준 문제 뽀개기 : 기초 백준 문제 추천

1. 수들의 합 (그리디)

- 문제: 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값?

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

- 해결 과정: 1,2,3,...부터 연속된 합이 최소인 줄 알고 구간합 구하는 방식으로 투포인터 썼는데, 생각해보니 항상 연속인 값이 나올 순 없다.!!!! 1,2,3,...부터 누적합을 구하다가 1+2+3+ ...M = num > S를 처음으로 만족하게 되면, (S - num)인 숫자만 쏙 빼면 되므로 M-1을 출력한다.

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

2. 사탕 뽑기 (브루트 포스)

- 문제 : 인접한 사탕 2개의 위치를 바꾼 후,  같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 선택해서 먹는다. 먹을 수 있는 가장 많은 사탕 개수는?

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

- 해결 과정:  arr[i][j]과 인접한 사탕과 자리 바꾼 후, 자리 바꾼 배열기준으로 인접한 사탕이 몇개인지 셈

- python 문법

  * ch = collections.Counter( arr) #리스트의 각 원소의 빈출 횟수를 세서 tuple 리스트로 만들어주는 라이브러리

 (ch = [ ('a',3) , ('b',2),.. ] )

  * max_ch = ch.most_common(i) #가장 많이 나온 상위 i개의 리스트 출력

리스트에서 각 원소의 빈출 횟수를 리스트로 만들어주는 라이브러리: Counter(), most_common(i) #가장 많이 나온 상위 i개의 리스트를 출력
   * str은 수정/삭제가 안되므로 입력받을 때 split()으로 나눠서 배열로 저장하자 -- 수정할 것 같으면

   * str을 철자 하나씩 끊어 list로 저장하는 법 : list(S)

( 코드 )

# 3085 사탕 게임a
# 인접한 두 사탕의 자리를 1번 바구고. 그 때 같은 색으로 이루어지는 가장 긴 연속부분을 고른 다음 사탕을 먹을 때 먹을 수 있는 사탕의 최대 개수
#리스트에서 각 원소의 빈출 횟수를 리스트로 만들어주는 라이브러리: Counter(), most_common(i) #가장 많이 나온 상위 i개의 리스트를 출력
# ch = collections.Counter(arr[i]).most_common(1)[0]
# swap : a,b = b,a 로 바꾸면 swap됨. arr[a],arr[b] = arr[b],arr[a]
# str은 수정/삭제가 안되므로 입력받을 때 split()으로 나눠서 저장하기
# str을 철자 하나씩 끊어 list로 저장하는 법 : list(S)로 하기!!!

import collections

def search(i,j):
	#상하좌우로 해당 색의 사탕이 연속으로 몇 개 있는지 탐색
	candy = arr[i][j]
	cnt_1 = 1
	cnt_2 = 1

	#위 방향으로 연속으로 몇 개 있는지 확인
	idx = j-1
	while idx >= 0 and arr[i][idx] == candy:
		cnt_1 += 1
		idx -= 1

	#아래 방향으로 연속 몇 개 있는지 확인
	idx = j+1
	while idx < N and arr[i][idx] == candy:
		cnt_1 += 1
		idx += 1

	#왼쪽 방향으로 연속 몇 개 있는지 확인
	idx = i - 1
	while idx >= 0 and arr[idx][j] == candy:
		cnt_2 += 1
		idx -= 1
	
	#오른쪽 방향으로 연속 몇 개 있는지 확인
	idx = i + 1
	while idx < N and arr[idx][j] == candy:
		cnt_2 += 1
		idx += 1
	return max(cnt_1,cnt_2) 

if __name__ == "__main__":

	N = int(input())
	arr = [ list(input()) for _ in range(N) ]
	answer = 0

	dx = [-1,0,1,0]
	dy = [0,1,0,-1]

	for i in range(N):
		for j in range(N):
			for k in range(4):
				nx = i + dx[k]
				ny = j + dy[k]
			
				if nx < 0 or nx >= N or ny < 0 or ny >= N:
					continue
				
				#swap한 값으로 개수 탐색 
				arr[i][j], arr[nx][ny] = arr[nx][ny],arr[i][j]	
				answer = max(answer,search(i,j))
				arr[i][j], arr[nx][ny] = arr[nx][ny],arr[i][j]
			
	print(answer)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

3. 동전 1 ( dp)

- 문제 : N개의 동전을 이용해서 합을 K로 만들 수 있는 경우의 수를 출력하라(각 동전은 무한대로 있다고 가정)

https://www.acmicpc.net/problem/2293

2293번: 동전 1

- 해결 방법:  그새 까먹어서 https://land-turtler.tistory.com/9 참고함..ㅎ

    - 1원으로 만들 수 있는 경우의 수 구하고,2원으로 만들수있는 경우의 수 더하고,...
    - dp[j] = dp [j](이전 동전 종류를 이용해 j를 만들었던 경우의 수 ) + dp[j-coins[i]]( 새 동전을 사용하는 경우 추가)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

4. 동전 2 (dp)

- 문제 : N개의 동전을 이용해서 합을 K로 만들 수 있는 경우들 중, 최소로 동전을 사용할 수 있는 경우의 동전 개수는? (동전 종류 별 개수는 무한대로 가정)

https://www.acmicpc.net/problem/2294

2294번: 동전 2

- 해결 방법 : dp[K]가 합을 K로 만들 수 있는 경우 수 중, 최소한의 동전개수라 하자.

dp[K]가 최소가 되려면 dp[K - coin]값이 최소가 되어야 한다. dp[K-coin] + 1(coin 1개를 더함)이 dp[K]가 됨

- 주의 사항: 배열 만들 땐 N,K중 큰 값 사이즈로 하기(index error)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

5. 파이프 옮기기1 (dp,dfs)

- 문제 : 길이가 2인 파이프를 가로,세로,대각선으로 옮길 수 잇을 때 (0,0)(0,1) 에서 (N-1,N-1)로 옮길 수 있는 경우의 수 https://www.acmicpc.net/problem/17070

1) dfs로 풀기 : (0,0) -> (N-1,N-1)로 가는 "경우의 수"를 구하는 법으론 dfs도 있지만, vistied배열을 쓸 수 없기 때문에 시간초과 가능. PyPy3로 풀기 

1-2) 주의 사항: 2차원 리스트 입력받을 때!!! list( list(map(int,input().split())) for_in range(N)) -- list 2번 써야 함

( dfs 코드)

#(0,0) -> (N-1,N-1)로 가는 법. dfs로 가도 되는데 visited를 쓸 수 없음. dp로도 풀 수 있음
#대각선 아래 오른쪽 
# 2차원 리스트 입력받을 때!!! list( list(map(int,input().split())) for_in range(N)) -- list 2번 써야 함/ 안그러면 2차원 배열에 제대로안들어감..! 

import sys
input = sys.stdin.readline

arr = []
N = 0
cnt = 0

def dfs(x,y,d):
	global arr,N,cnt
	if x == N-1 and y == N-1:
		cnt += 1
		return

	#대각선 
	if d == 0:
		if x+1 < N and y+1 < N and arr[x+1][y+1] == 0 and arr[x][y+1] == 0 and arr[x+1][y] == 0:
			dfs(x+1,y+1,0)
		if x+1 < N and y < N and arr[x+1][y] == 0:
			dfs(x+1,y,1)
		if x < N and y+1 < N and arr[x][y+1] == 0:
			dfs(x,y+1,2)
	
	elif d == 1:
		if x+1 < N and y+1 < N and arr[x+1][y+1] == 0 and arr[x][y+1] == 0 and arr[x+1][y] == 0:
			dfs(x+1,y+1,0)
		if x+1 < N and y< N and arr[x+1][y] == 0:
			dfs(x+1,y,1)

	elif d == 2:
		if x+1 < N and y+1 < N and arr[x+1][y+1] == 0 and arr[x][y+1] == 0 and arr[x+1][y] == 0:
			dfs(x+1,y+1,0)
		if x < N and y+1 < N and arr[x][y+1] == 0:
			dfs(x,y+1,2)


def solution(tmp):
	global arr
	
	arr = tmp.copy()
	dfs(0,1,2) #0,1을 1번으로 가기 
	
	return(cnt)

if __name__ == "__main__":
	
	N = int(input())
	
	tmp = list( list(map(int,input().split())) for _ in range(N))

	answer = solution(tmp)
	print(answer)

 

2) dp로 풀기

- 포도주 시식처럼 dp[x][y][d] : (x,y)에 d방향으로 올 수 있는 경우의 수를 저장하기!!!!! 

- 대각선으로 올 수 있는 경우는 (x-1,y-1)을 가로/세로/대각선으로 도착한 모든 경우에서 가능함 (세->대/가->대/대->대)

- 가로/세로로 올 수 있는 경우는 (x-1,y) (x,y-1)을 가로 & 대각선 / 세로 &대각선으로 도차한 경우에서 이동 가능

 

2-2) 유의사항

#(0,0) -> (N-1,N-1)로 가는 방법은 dp로도 풀 수 있다. 작은 문제로 나눌 수 있고,memoization이 되기 때문

#포도주시식처럼 dp[x][y][d]로 저장하기( (x,y)를 d방향으로 오는데 가능한 경우의 수 )

# 주의!!!! 배열의 시작/끝을 넣을땐 항상 고민하자. 맨 마지막 좌표(N-1,N-1)이 항상 0이라는 보장은 없음!!

(dp 코드)

#dp로 푸는 방법
#(0,0) -> (N-1,N-1)로 가는 방법은 dp로도 풀 수 있다. 작은 문제로 나눌 수 있고,memoization이 되기 때문
#포도주시식처럼 dp[x][y][d]로 저장하기( (x,y)를 d방향으로 오는데 가능한 경우의 수 )
# 주의!!!! 배열의 시작/끝을 넣을땐 항상 고민하자. 맨 마지막 좌표(N-1,N-1)이 항상 0이라는 보장은 없음!! 
import sys
input = sys.stdin.readline

def solution(N,arr):

	dp = [list( [0]*3 for _ in range(N)) for _ in range(N)]
	#초기화 (d: 0 (대각선) 1(우측) 2(아래) )
	dp[0][1][1] = 1

	for x in range(N):
		for y in range(N):
			#대각선 확인
			if x-1 >= 0 and y-1 >=0 and arr[x-1][y-1] == 0 and arr[x][y-1] == 0 and arr[x-1][y] == 0:
				dp[x][y][0] += ( dp[x-1][y-1][0] + dp[x-1][y-1][1] + dp[x-1][y-1][2])

			#우측 확인
			if y-1 >= 0 and arr[x][y-1] == 0:
				dp[x][y][1] += ( dp[x][y-1][1] + dp[x][y-1][0] )
			
			#아래측 확인
			if x-1 >= 0 and arr[x-1][y] == 0:
				dp[x][y][2] +=( dp[x-1][y][2] + dp[x-1][y][0])
	
	if arr[N-1][N-1] == 0:
		return sum(dp[N-1][N-1])
	else:
		return 0

if __name__ == "__main__":
	N = int(input())
	tmp = list(list(map(int,input().split())) for _ in range(N))

	answer = solution(N,tmp)
	print(answer)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

6. 전쟁 - 전투(BFS)

- 문제 : 우리팀은 W,상대팀은 B로 주어지고 각 전력들 N명이 모여있을 때 위력이 N^2이 된다. 우리팀과 상대팀의 전력을 출력하라

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

- 풀이 방법: BFS로 풀 땐 visited, dxdy, arr 크기(N,M)은 그냥 전역으로 한다 생각하고 풀기!

- 유의 사항: main으로 입력받은 변수나 리스트는 함수에서 global로 안쓰고 사용 가능

   std.readline은 개행문자 '\n'까지 입력으로 들어감!!! 제거하고 싶으면 strip()쓰기!!

 

( 코드 )

#1303 전쟁-전투
#우리편은 W,상대편은B일때 우리 병사 합과 적국 병사 합을 구하라. 병사는 모일수록 N^2만큼 위력을 낼 수 있다.
# sys.stdin.readline쓰면 \n도 같이 들어감.없애려면 strip()쓰기 
#input()에서는 string을 입력받기 위해선 ""을 붙여야 함. 큰따옴표를 안붙이면 변수명이 입력
import sys
from collections import deque
input = sys.stdin.readline

visited = []
dx = [-1,0,1,0]
dy = [0,1,0,-1]
N= 0
M = 0

def bfs(x,y,ch):
	global visited, our_team,your_team 
	q = deque()

	visited[x][y] = True
	cnt = 1
	q.append((x,y))

	while q:
		cur = q.popleft()
		for k in range(4):
			nx = cur[0] + dx[k]
			ny = cur[1] + dy[k]
			if nx < 0 or nx >= M or ny <0 or ny >= N:
				continue
			if visited[nx][ny] == False and arr[nx][ny] == ch:
				cnt += 1
				q.append((nx,ny))
				visited[nx][ny] = True

	return cnt*cnt

def solution(N,M):
	global visited,our_team,your_team
	answer = []
	visited = list( [False] * N for _ in range(M) )
	our_team = 0
	your_team = 0

	for x in range(M):
		for y in range(N):
			if visited[x][y] == False:
				if arr[x][y] == 'W':
					our_team += bfs(x,y,arr[x][y])
				else:
					your_team += bfs(x,y,arr[x][y])

	answer.append(our_team)
	answer.append(your_team)
	return answer

if __name__ == "__main__":
	N,M = map(int,input().split()) #가로 N 세로 M
	arr = [list(input().strip()) for _ in range(M)]

	answer = solution(N,M)

	for x in answer:
		print(x, end = " ")