본문 바로가기

백준13

[삽입정렬] 백준 11399번 문제1. ATM 기 한 개가 있고, 손님들이 각자 업무를 보는 시간이 주어진다2. 모든 손님들의 서비스를 합한 시간의 최소값을 구해라(사람의 수  : 1 (사람 당 서비스 시간 :  1 * 시간제한 : 1초 문제분석1. 가장 빠른 시간에 인출하는 방법을 그리디 방식이라고 한다.2. 시간제한은 1초 이므로, O(N^2) 이하인 정렬 알고리즘 아무거나 사용하면 된다3. 정렬 이후 서비스 시간을 합정렬을 이용하여, 최소값 구함그리디 방식? - 그리디 방식이란 탐욕법으로서 가장 최적의 해를 구하는 것을 목표하는 알고리즘이다. - 현재 문제에서는, 앞에 있는 손님들의 서비스 시간을 더해야하므로 반복적으로 더해지는 서비스 시간이 적어야한다 - 따라서, 그리디 방식을 적용하여 서비스 시간의 최적의 해를 도출해야한다 .. 2024. 11. 10.
[선택정렬] 백준 1427번 문제1번째 줄에 정렬할 수 N이 주어진다.N은 1,000,000,000 보다 작거나 같은 자연수다(주어진 N을 내림차순으로 정렬하시오) 문제분석- 자연수를 받아서, 정렬하는 문제이므로 먼저 숫자를 배열로 넣어야한다ex) 2143 -> 2,1,4,3 (분리필요)- 선택 정렬을 이용하여 문제풀이 진행과정빨간색 : 정렬된 수파란색 : 정렬해야하는 범위순서과정첫번째4123두번째4321세번째4321 슈도코드N(정렬할 수 입력)arr(N을 분리하여 배열로 저장)for(i=0 ~ arr 크기만큼 반복){ for(j= i ~ arr 크기만큼반복){ 현재 범위에서 최대 인덱스값 찾기 } if (현재 i값과 maxIdx값이 다르면){ swap (arr[i], arr[maxIdx]) }}.. 2024. 11. 9.
[우선순위 큐]백준 11286번 문제1. 첫번째 입력값으로 연산의 개수 N이 주어진다 (1 2. 다음 N개의 줄에는 정수x가 주어진다3. x값이 0이 아니라면 배열에 x라는 값을 추가하고, x가 0이라면 배열에서 절대값이 가장 작은 값을 출력한다(단, 절대값이 같을경우 음수를 우선순위로 둔다)*2초이내 풀이 문제분석N의 최대 범위가 100,000이므로 O(nlogn)이 가능하다데이터가 새로 삽입될때마다 절대값과 관련된 정렬이 필요하므로 우선순위 큐를 이용하여 문제를 해결주의) 정렬기준은 직접 정의해야함 (절대값에 따른 값이 같은 경우 기준 설정 필요) 슈도코드N(질의 요청개수 입력)우선순위 큐 설정for(N만큼 반복){ 요청이 0일때, 비어있으면 0 출력 / 있으면 front 출력 (poll()) 요청이 0이 아닐때, que.. 2024. 11. 6.
[큐] 백준 2164번 문제N장의 카드가 존재 (순서가 순차적으로 카드개수만큼 존재)1. 1에서 N까지 번호가 존재2. 아래 동작으로 계속 반복 후 마지막 수를 출력 ( 순서 )    > 가장 위에 있는 카드를 바닥에 버림    > 그다음 가장 위에있는 카드를 마지막으로 옮김    > 이걸 반복정수 N ( 1  문제분석가장 위에있는 카드를 가장 마지막으로 이동 시키는 작업 ( -> Queue의 이해도 확인 )선입선출을 생각하여 문제 풀기 슈도코드N개 입력 받기for( 카드의 개수 ){ 큐에 카드 저장}while( 카드 1장이 남을때까지 ){ 맨위의 카드를 버림 맨위의 카드를 가장 아래의 카드 밑으로 이동}마지막으로 남은 카드 출력 구현import java.io.BufferedReader;import java.. 2024. 11. 4.
[스택] 백준 17298 문제1. 크기가 N인 수열(A) 존재2. 각 원소 A[i]에 관련된 오큰수 NGE[i] 를 구한다3. 오큰수가 존재하지 않는 경우는 , "-1"로 저장( 1 (* 오큰수 : 오른쪽에 큰 수 중 가장 왼쪽에 있는 수 )ex) A [ 3,5,2,7 ] => NGE [ 5,7,7,-1 ]A [ 9,5,4,8 ] => NGE [ -1, 8,8,-1 ] 문제 분석N의 조건이 1,000,000까지 가능하므로 , 일반적인 반복문으로 풀이를 할 경우 시간초과가 난다스택을 이용하여, 풀이 진행스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수 는 오큰수가 된다오큰수 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력ex) A[top] ex) A [ 3,5,2 ,7] // result [ ] // s.. 2024. 10. 30.
[스택] 백준 1874번 문제1. 수열의 개수 N 제공 ( 1 2. n개의 줄에는, 1이상 n이하의 정수가 1개씩 제공 (같은 정수가 2번 나오지는 않음)3. 해당 제공된 n개의 줄의 수열을 오름차순으로 정리 (스택 이용)4. 오름차순 정렬이 불가능할경우, "No"반환입력출력8+4+3+6+8-7-5+2+1- + + - - - -  문제 분석1부터 자연수를 증가시키면서, 입력으로 주어진 숫자와 비교하며 자연수를 스택에 추가하거나 빼는 방식으로 풀이스택 연산 방법1. 현재 수열 값 >= 자연수- 현재 수열값이 큰 경우, 자연수를 증가시키며 스택에 삽입2. 현재 수열값 == 자연수- 스택에서 값을 빼오며, 입력버퍼에 쌓아두고, 삭제진행- 단, 같지 않을경우 스택을 이용해서 오름차순을 만들 수 없으므로 "No" 반환  수도코드probl.. 2024. 10. 29.

티스토리툴바