본문 바로가기

백준74

백준 1253: 좋다(java/python) 문제풀이 오름차순 정렬한 배열 A[]에 투 포인터 기법을 사용하여 풀이할 수 있다. 낮은 인덱스부터 탐색할 left와 높은 인덱스부터 탐색할 right 포인터를 선언하고, for문을 순회하며 오름차순 정렬한 A[i]를 순서대로 탐색한다. 현재 요소(A[i])가 sum = A[left] + A[right]보다 크면 right을 1 감소시키고, A[i] for(int i=0; iA[i]) { right--; } else if(sumleft 포인터는 항상 right 포인터의 왼쪽에(낮은 인덱스에) 위치해야 하므로 while문의 조건을 left 여기에 "어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면" 의 조건을 위해 left나 right가 i와 같을 경우 반복을 건너뛰는 작업을 추가하면 알고리즘은.. 2024. 10. 7.
백준 1940: 주몽(java/python) 문제풀이 이중 for문을 사용해, i를 기준으로 j를 i부터 N까지 1씩 증가시키며 i번째 원소와 j번째 원소의 합이 M이 될 때 count++하는 풀이를 떠올릴 수 있지만, 이 방식은 \(O(N^{2})\)의 시간 복잡도를 가지므로 시간 초과 오류가 표시된다.//오류 코드for(int i=0; i 따라서 배열을 정렬한 후, 시간 복잡도가 \(O(N)\)인 투 포인터 기법을 활용해야 한다.(길이가 N인 배열 내에서 탐색하는 투 포인터 기법에서 왼쪽 인덱스와 오른쪽 인덱스를 각각 left, right라 했을 때, 항상 left \(O(N)\)) 투 포인터 기법을 사용해 재료 배열 materials[] 내에서 합이 M인 두 원소를 찾는 알고리즘을 작성하면 아래와 같다. 탐색하기 전에 materials[] 배.. 2024. 10. 1.
백준 10986: 나머지 합 구하기(java) 문제풀이 모듈러(modulo) 연산의 성질을 알고 있어야 시간 제한 내에 해결할 수 있는 문제다. \(A\;mod\;B=R\) 에서 \(mod\)를 모듈러 연산자라 하고, 이때 \(R\)은 \(A\)를 \(B\) 로 나눈 나머지이다. 자바, 파이썬 등에서는 % 연산자로 표기한다. 모듈러 연산에서 분배 법칙이 성립하는데, 이 중 1번, 2번 공식을 풀이에 이용할 것이다.\((a\;mod\;n+b\;mod\;n)\;mod\;n=(a+b)\;mod\;n\)\((a\;mod\;n-b\;mod\;n)\;mod\;n=(a-b)\;mod\;n\)\((a\;mod\;n\times{b\;mod\;n})\;mod\;n=(a\times{b})\;mod\;n\)입력받은 N개의 정수를 저장할 arr[N]과, arr[i-1] +.. 2024. 9. 30.
백준 2750: 수 정렬하기(java/python) 문제풀이 버블 정렬으로 풀이하거나, 내장 함수 (파이썬)list.sort() 또는 (자바)Arrays.sort()를 사용해 간단하게 해결할 수 있다. 1. python_버블 정렬(Bubble Sort) 버블 정렬은 인접한 두 데이터의 크기를 비교하는 정렬 방법이다. 이중 for문을 사용하므로 \(O(N^{2})\)의 시간복잡도를 가진다. 앞뒤의 원소를 비교해, 앞의 원소가 더 크다면 뒤의 원소와 자리를 바꾼다.N=int(input())arr=[0]*Nfor i in range(N): arr[i]=int(input())for i in range(N-1): for j in range(N-1-i): if arr[j]>arr[j+1]: temp=arr[j] .. 2024. 9. 30.
백준 1629: 곱셈(java) 문제풀이 분할 정복(Divide and Conquer)으로 풀이하는 문제이다.기본적으로 \(x^{n}=(x^{\frac{n}{2}})^2=(x^2)^{\frac{n}{2}}\)임을 이용하며, 더 자세히는 n이 홀수일 때 \(x^{n}=(x^{2})^{\frac{n}{2}}\), 짝수일 때 \(x*{n}= x\times{(x^{2})^{\frac{n-1}{2}}}\)이다.  이를 바탕으로 \(x^{n}\)을 구하는 pow(x, n) 함수를 아래와 같이 작성할 수 있다.int pow(int x, int n){ if(n==0){ //x의 0제곱은 1 return 1; } else if(n%2==0){ //n이 짝수일 때 return pow(x*x, n/2); } else{ .. 2024. 9. 28.
백준 11660: 구간 합 구하기 5(java/python) 문제풀이이중 for문을 순회하며 (0, 0)부터 (i, j)인 지점까지의 합을 배열 arr에 저장하고, 이들을 적절히 가감하여 (x1, y1)부터 (x2, y2)인 지점까지의 누적 합을 계산한다. 전체 코드 1. javaimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); .. 2024. 9. 26.

티스토리툴바