본문 바로가기

개발 서적 리뷰/DoIt 알고리즘 코딩테스트26

[우선순위 큐]백준 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.
[슬라이딩 윈도우 + deque] 백준 11003번 문제1. 숫자 배열 크기 + 범위 크기가 주어짐2. 숫자 배열이 주어짐3. 숫자배열에서 범위만큼 움직이며, 그때마다 최소값을 저장문제 조건 : ( 1  문제분석범위 크기 이동만큼 최소값 탐색슬라이딩 윈도우 : 2개의 포인터를 잡고, 이동시키며 최소값 탐색범위크기 및 숫자개수 최대치가 5,000,000이므로 시간복잡도를 O(n) 초과하여 잡을 수가 없음 (시간 초과)기본 정렬 시간 복잡도 : O(nlogn)일반적인 정렬알고리즘으로 풀지 못하므로, 덱(deque)을 도입Deque (덱) - 앞쪽에서 추가/삭제 가능, 뒷쪽에서도 추가/삭제 가능[구조]    Add    ->                                               -> Remove                   Fr.. 2024. 10. 27.
[슬라이딩윈도우] 백준 12891번 문제문자열 {A, C, G ,T}인 문자열만 주어지는 상황1. 문자열 길이(S)를 입력 받고, 그 중에 부분 문자열(P)을 가지고 비밀번호를 만듬2. 부분 문자열중에서 비밀번호를 만들 때,A,C,G,T 각각의 만족하는 최소 조건이 존재3. 최소 조건을 만족하면 비밀번호를 만들 수 있음 (해당 개수 세기)4. 2초이내,  (1 ex) A C G T A C G G T A C C (주어진 문자열) (A (2개), C(0개), G(1개), T(1개) 이상 조건 충족)->해당 조건을 만족하는, 비밀번호 만들 수 있는 개수 구하기 문제분석1,000,000개 이므로, O(n)으로 시간복잡도를 가져야함슬라이딩 윈도우를 이용하여, 부분문자열을 표현조건에 맞는 비밀번호 생성 문자를 이용하여, 몇개를 만들 수 있는지 구현[.. 2024. 10. 24.

티스토리툴바