본문 바로가기

전체 글79

JAVA INT VS LONG class Solution { public long solution(int price, int money, int count) { long answer = -1; long total=0; for(int i=1;itotal 변수를 int로 선언했을 때 문제가 발생하는 이유는 정수형의 범위를 초과할 가능성 때문입니다.Java에서 int 타입은 -2,147,483,648 ~ 2,147,483,647의 범위를 갖습니다. 하지만 문제 조건에 따라 price, money, count의 조합에 의해 total 값이 이 범위를 초과할 수 있습니다.문제 상황 분석total은 price와 count를 이용하여 계산됩니다:total=price×(1+2+3+⋯+count)\text{total} = price \times (1.. 2025. 1. 17.
파이썬 : 파라메트릭 서치 최적화 문제를, 결정 문제로 바꿔서 이진탐색으로 푸는 방법 *최적화 문제 : 문제 상황을 만족하는 변수의 최솟값 또는 최댓값을 구하는 문제  (ex. 최단 경로 문제)*결정 문제 : Yes 또는 No 를 구하는 문제  수강생들의 외모값(외모를 수치화할 수 있는 기계가 생겼다고 가정하자..)과,, 커플/솔로 여부가 주어진다..커플들은 항상 솔로들보다 외모값이 높다고 가정하자..그럼 외모 값이 최소 몇 이상일 때부터 커플인가? 회원외모값. 커플 여부. 커플?외모값?회원01234567커플여부FFFTTTTT외모값245667910  "파라메트릭"은 **"파라미터(변수)"**에 의존하는 문제를 해결하는 접근법을 나타냅니다.일반적으로 문제를 단순히 해답을 찾는 방식으로 접근하지 않고, 특정 변수(파라미터)의 범위를 .. 2024. 12. 23.
파이썬 : 이진탐색 bisect + 예제문제 이진 탐색에 사용되는 bisect 라이브러리가 존재한다.from bisect import bisect_right, bisect_left import bisectarr = [1, 3, 4, 7, 9]x = 5 # 넣을 숫자index = bisect.bisect_left(arr, x)print(index) # Output: 3arr = [1, 3, 4, 7, 9]x = 7 # 넣을 숫자index = bisect.bisect_right(arr, x)print(index) # Output: 4 기존 7의 오른쪽에 들어감 2024. 12. 23.
파이썬 : 입력을 배열로 저장하기 입력101111101010101011111011 import sysinput_data1=sys.stdin.read() #전체 줄을 읽어온다 # input_data1="101111\n101010\n101011\n111011\n" input_data2=input_data2.strip()# input_data2="101111\n101010\n101011\n111011" input_data3=input_data2.split('\n') #input_data3=["101111", "101010", "101011", "111011"] for i in range(4):   row=list(map(int,input_data3[i]))   arr=append(row) *map은 반복 가능한 객체에 대해(=input_dat.. 2024. 12. 23.
Chap4. Dfs,Bfs, 백트래킹 - 백준 11724 연결 요소의 개수 시간 제한메모리 제한제출정답맞힌 사람정답 비율3 초512 MB149531676154432242.119%문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 방향 없는 그래프이므로, 양방향 그래프이다. 인접행렬로 저장했을 때 대칭 행렬 형태이다.연결 요소를 묻고 있으므로, 간선으로 이어진 덩어리의 개수를 찾아야한다.  예를 들어, a 노드와 이어진 b 노드, b 노.. 2024. 12. 22.
Chap 4. Dfs, Bfs, 백트래킹 - '백트래킹' 백트래킹. 대추적..이라고도 한다.  미연시를 생각해보자..선택지를 고르는 거에 따라 이후 상황이 바뀐다. 즉, 분기가 생긴다.. 만약 선택지가 3개가 주어진다면? 상황이 3가지로 나뉜다는 뜻이고,, 이런 선택지를 택하는 횟수가 10번 이라면3의 10제곱 만큼의 상황이 나뉜다는 것이다.  모든 경우를 다 살펴본다면? 너무 많은 상황을 살펴봐야함. [보라 머리 여자애] [핑크 머리 여자애] 둘 중에 [보라 머리 여자애]와 친애도를 max 로 찍는게 목표라면?그것을 위한 선택지를 눌러야됨.그런데 선택- 선택 - 선택을 잘하다가.. 어떤 선택을 했는데 여기서 친애도가 뚝 떨어졌다면?그러면 다시 직전 선택으로 돌아와, 다른 선택지로 가야 max를 찍을 수 있음. 이미 친애도가 떨어진 상황에 대한 분기를 더 살펴.. 2024. 12. 21.