분류 전체보기 (75) 썸네일형 리스트형 이분탐색/삼분탐색 #2805: 나무 자르기 [JAVA] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 접근 #1654 랜선 자르기 문제와 거의 똑같다..! 근데 몇 가지 착각한 부분이 있어서 생각하는 데 시간 걸림 ㅠ 착각한 부분 랜선 자르기 문제와 달리 절단기에 설정한 길이를 달리 하면 도출되는 나무의 길이의 합이 겹치지 않으므로 그냥 일반 이분 탐색으로 쓰면 안되나?? -> X. 이분탐색은 딱 M이 될 때의 길이를 찾게다는거니까,, 근데 주어진 나무.. 이분탐색/삼분탐색 #10816: 숫자 카드2 [JAVA] https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 문제 접근 3가지 방법으로 풀 수 있다. 1. 이진 탐색 활용 - upper bound, lower bound 이용 이해가 안되서 한참 들여다봤다.. 이분탐색 활용 버전인 upper bound, lower bound를 구해서 중복 원소에 대한 길이를 찾아야 하는 문제이다. 이분 탐색에서 원래는 arr[mid]==key 이면 return mid 해서 binary .. 객체 생성 시 유용한 빌더 패턴(Builder Pattern) 스프링 시큐리티 강의에서 Builder로 객체 생성하길래 궁금해서 찾아봄 https://mangkyu.tistory.com/163 #15650: N과 M (2) [JAVA] https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 N과 M(1) 문제 복습하고 풀기 코드 1. N과 M(1) 문제에서 if문 한 줄 추가 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; public class Main { static int n; static.. #15649: N과 M (1) [JAVA] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 nPm을 구하는 문제이다. dfs로 백트래킹을 구현 [ 참고 ] https://st-lab.tistory.com/114 ㄴ 봐도봐도 이해가 안됐는데.. 보다보니 이해 됨..! 코드의 흐름을 잘 따라가보자 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; .. #11660: 구간 합 구하기 5 [JAVA] https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근 1. 행 별로 메모제이션 해서 구할 수 있음(#11659 구간 합 4 아이디어) 2. 2차원으로 메모제이션 해서 구할 수 있음 [ 참고 ] https://propercoding.tistory.com/29 코드 1. import java.io.BufferedReader; import java.io.IOException; import java.io.. #11659: 구간 합 구하기 4 [JAVA] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 접근 암생각 없이 그냥 풀었더니 시간 초과 났음. 주어진 N, M의 범위를 보면 알 수 있듯이 단순 for문 돌려서 풀면 당연히 시간 초과 남! 그래서 누적 합이라는 접근법으로 시간을 줄여야한당 누적 합은 다음과 같다. 주어진 수가 5,4,3,2,1이라고 하자. a 배열의 0번 인덱스는 안쓴다고 치면 누적 합을 다음과 같이 저장할 수 있다. a[1] a[2] a[3] .. 그래프 문제(bfs,dfs) #2178: 미로 탐색 [JAVA] https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 접근 최단 거리니까 bfs를 쓰자. 왜 bfs를 써야하는지는 이전 포스팅 '그래프 탐색 bfs, dfs 정리'를 참조하시라 코드1 Point 클래스에 행,열 위치와 거리를 저장해서 큐에 저장. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Point { int.. 이전 1 2 3 4 5 ··· 10 다음
