전체 글 (119) 썸네일형 리스트형 [백준] 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 .. [코드포스] edu_round #99(div2)-B JUMPS 문제 링크 : codeforces.com/contest/1455/problem/B Problem - B - Codeforces codeforces.com 역시 코포 문제가 직관 기르기에 좋은 것 같다. 1+2+3+.....+ xi 의 값이 n이라면 i가 답 아니라면 최초로 (n+1)보다 큰 값이 나오는 수까지 더한 횟수(i)가 답이 된다. 이유는 음수가 두 개 이상 나오지 않는것을 공책에 써가면 직관적으로 느낌이 온다. 자명하다는 것은 알아서 증명 음수가 한 개 나온다면 그것은 +1 대신에 -1, +2 대신에 -1 , +3 대신에 -1 이런식으로 바뀔 수 있으므로 xi까지 더한 값을 sum이라 하면 sum -xi-1 ~ sum-2까지 가능하다 그래서 (n+1)보다 큰 값이 나온다면 그 값에서 어떤 수든 .. [백준] 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.. [코드포스] Round #686(div3)-B Unique Bid Auction 문제링크 : codeforces.com/contest/1454/problem/B Problem - B - Codeforces codeforces.com 배열에 있는 값이 나온 횟수를 cnt배열에 저장했다. cnt배열에 저장된 수 중 1번만 나온 수를 찾아서 다시 한번 반복문을 돌며 인덱스를 출력해주었다. 효율성이 애매할 것 같았는데 모든 테스트케이스에서의 sum of n이 20만 미만이라서 간신히 돌아간 듯 하다. #include #include #include #include #include #include using namespace std; int cnt[200001]; int arr[200001]; int main() { int tc; cin >> tc; for (int i = 0; i < tc;.. [백준] 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; .. [백준] 1920 수 찾기 문제 링크 : 정렬 후 이분탐색을 활용해서 풀었다. set을 활용하면 더 빠르다고는 생각했는데 문법을 몰라서 일단 이분탐색 코드도 오랜만에 작성해보려 했다. 내코드 if __name__ == '__main__': N = input() arr = list(map(int,input().rstrip().split())) query = input() order = list(map(int,input().rstrip().split())) arr.sort() for x in order: suc = False left = 0;right = len(arr)-1; while(left 이전 1 ··· 11 12 13 14 15 다음