알고리즘/백준 (51) 썸네일형 리스트형 [백준] 1992 쿼드트리 문제링크: www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 문제를 읽는 순간 분할정복임을 알았다. import java.io.*; import java.util.*; public class Main { public static int N; public static char [][]board; public static void divide_q(int start_y, int start_x, int square_size) { if(square_size.. [백준] 1541 잃어버린 괄호 문제링크: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 마이너스가 하나라도 존재하는 부분부터 다 음수가 가능하다는 것이 자명하기 때문에 마이너스 기준으로 나누었다. split 방법을 몰라서 검색했고 배웠다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = ne.. [백준] 11054 가장 긴 바이토닉 부분 수열 문제링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 지난번 LIS로 백준의 전깃줄이라는 문제를 풀었다. LIS를 안다면 전깃줄 문제보다 쉽게 직관적으로 LIS로 풀면 된다는 것을 알 수 있다. 그래서 이 문제가 골드3인게 이해는 안가지만 어쨌든 풀이는 LIS로 해결했다. 정방향,역방향으로 증가하는 가장 긴 부분수열을 구해서 그 합이 최대인 값이 증가하다가 감소하는 가장 긴 부분수열의 길이일 것이다. import java.io.*; import java.util.*; p.. [백준] 2565 전깃줄 문제링크: www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 지난번에 이어서 백준 단계별로 풀어보기 다이나미프로그래밍 문제다. LIS라는 생각이 안떠오르면 어려울 것 같다. 나도 그리디로 접근하다가 생각보다 오래걸렸다. 어려운 구현 문제를 더 많이 풀어봐야겠다고 생각했다. 근데 N이 100이라 비효율적으로 짜더라도 풀릴 것 같긴 하다. import java.io.*; import java.util.*; public class Main { public static cl.. [백준] 1003 피보나치 함수 문제링크: www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 백준 단계별로 풀어보기를 시작했다. 다이나믹프로그래밍 기초1을 다 풀어볼 예정이다. 이 문제를 자바 Scanner로 입력 받았더니 시간초과가 떴다. BufferedReader로 바꾸고 통과 import java.io.*; import java.util.*; public class Main { public static int []dp0; //0이 나온 횟수 public static int []dp1; //1이 나온 횟수 public static void init(){ dp0 = new int[41].. [백준] 2042 구간 합 구하기 문제링크 : www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 예전에 세그먼트 트리(인덱스 트리) 문제 기본 문제로 풀어봤던 문제를 다시 풀어봤다. 재귀 대신 반복으로 할 수 있으면 반복으로 하는 편이다. 예전 SDS 알고리즘 심화 특강 때, 강사분이 푸셨던 재귀가 아닌 방법을 기억해보며 코드를 짰다. import java.io.*; import java.util.*; public class Main .. [백준] 1072 게임 문제 링크 : www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 아직 익숙하지 않은 파이썬 들여쓰기 문제로 왜 틀렸는지 한참 고민했다. 들여쓰기 잘 봐야겠다 from math import floor if __name__ == '__main__': N,M = map(int,input().split()) original = floor((M*100)/N) left = 0 right = 1000000000 if original >= 99: print(-1) else: while(leftoriginal: right=mi.. [백준] 1806 부분합 문제링크 : www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 기본적인 투포인터 문제다. 개인적으로 이런 문제가 왜 골드3인지는 모르겠다. 가끔 자바로도 문제를 풀 것 같다. 내코드 import java.io.*; import java.util.*; public class Main { public static int[] arr; public static void main(String[] args)throws Exception { int N,S; .. 이전 1 ··· 3 4 5 6 7 다음