아무거나

문제 내용 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 시간 50분 풀이 과정 처음에 문제를 제대로 안 읽어서 비활성 바이러스를 제외한 빈칸중 M개를 골라서 나오는 최소 값인줄 알았다. 하지만 비활성 바이러스중 M개를 활성화 시켜서 나올수 있는 최소 값이었다. 문제 풀이는 조합 + BFS를 이용해서 풀었다. 정답 코드 import java.io.BufferedReader; import java.io.InputStreamReader; impor..

문제 내용 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 시간 50분 풀이 과정 각각의 땅을 체크하는 과정이나, 다리 길이를 구하는 과정에서는 BFS를 이용하였다. 하지만 땅에서 바다로 바뀌는 지점을 찾는 과정에서 시간이 많이 소요 되었다. 이 지점은 간단하게 서로 인접한 두 위치의 값만 비교하면 되는것이었다. (Sliding window 느낌) 둘다 땅이거나 둘다 바다인 경우에는 두 지점의 합은 한 지점의 합의 2배와 같을 것이다. 하지만 ..

문제 내용 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 시간 45분 풀이 과정 문제에 써있는 방식 그대로 각 벽마다 BFS를 실행하였다. -> 시간초과 역으로 생각해서 빈곳들의 크기를 구하고 빈곳의 값을 개수로 넣어줬다. 이후 각 벽마다 사방의 빈곳의 개수의 합+1을 넣었다.-> 오답 => 벽 주위의 빈곳들이 서로 연결되어 있는 경우를 고려하지 못했다. Map을 사용해서 각 빈 그룹별 개수를 넣었다. 이후 빈곳의 ..

문제 내용 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 풀이 시간 1시간 풀이 과정 여러개의 그룹들을 구하는 것이어기 때문에 유니온-파인드가 떠올랐다. 이후 문제를 풀면서 최대값을 구하는 로직을 작성 해지만 오답 -> 문제를 제대로 안읽엇다. - 여러 그룹들이어도 인원의 총 합이 K이하면 가능했다. 가능한 모든 경우의 수를 확인하기 위해 그룹들의 subse..

문제 내용 https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 시간 10분 풀이 과정 문제를 읽어보는 중에 그리디 혹은 DP라고 생각했고, 다 읽어보니 DP라는 확신이 들었음. 이후 상향식과 하향식중 어느쪽으로 할까 고민했고, 구현하기 편한 상향식으로 풀이를 결정함. BOJ순으로 발판을 밟아야 한다. index 0부터 현재 발판에 다음 발판을 찾아가는건 시간적으로 낭비라고 생각함. 따라서 먼저 전체발판을 1회 순회하면서 B,O,J에 해당하는 index를 따로 모아둠. 이후 dp값을 찾는 상향식 과정에서..

문제 내용 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 시간 4분 풀이 과정 백트래킹을 이용해 풀이 중복조합을 구현하는 간단한 풀이 정답 코드 1. 파이썬 import sys sys_input=sys.stdin.readline n,m=map(int,sys_input().rstrip().split()) ans=[] def back_tracking(prev): if len(ans)==m: for x in ans: print(x,end="..

문제 내용 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 시간 24분 풀이 과정 백트래킹을 이용하여 풀이 promising 조건 찾는데에 시간을 대부분 소비 정답 코드 1. 파이썬 #pypy3로 해서 통과함 import sys sys_input=sys.stdin.readline n=int(sys_input()) cur=[] ans=0 def success(row,col): for x,y in cur: if col==y or row+col==x+y or ..

문제 내용 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 시간 4분 풀이 과정 1. (python만) 라이브러리를 이용해서 간단하게 풀이(itertools.combinations 사용) 2. back_tracking을 이용해서 오름차순 조합 구현. 정답 코드 1. 파이썬 import sys from itertools import combinations sys_input=sys.stdin.readline n,m=map(int,sys_in..

문제 내용 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 시간 5분 풀이 과정 DP를 이용한 간단한 풀이 정답 코드 1. 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=[list(map(int,sys_input().rstrip().split())) for _ in range(n)] dp=[[0]*i for i in range(1,n+1)] dp[0][0]=arr[0][0] for i in range(1,n): for j in range(..

백준의 11053과 같은 유형을 흔히 `최장 증가 부분 수열(Longest Increasing Subsequence,LIS)라 하는데 이를 구하는 방법은 크게 두가지가 존재한다. 1. DP를 이용한 풀이 (가장 기본적 간단, 시간복잡도:O(n^2)) 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=list(map(int,sys_input().rstrip().split())) dp=[1] for i in range(1,n): find=0 for j in range(i): if arr[i]>arr[j]: find=max(find,dp[j]) dp.append(find+1) print(max(dp)) 자바 import java.io.*; ..