✔ 카드2 [백준 2164] 문제 분석하기 큐의 원리를 정확하게 알고 있는지 묻는 문제 큐의 선입선출 성질을 이용하여 문제에 접근 손으로 풀어보기 poll을 수행하여 맨 앞의 카드를 버림 add를 수행해 맨 앞에 있는 카드를 가장 아래로 옮김 큐의 크기가 1일 될 때까지 과정 1~2를 반복한 후 큐에 남은 원소를 출력 슈도코드 작성하기 N(카드의 개수) myQueue(카드 저장 자료구조) for(카드의 개수만큼 반복) { 큐에 카드 저장하기 } while(카드가 1장 남을 때까지) { 맨 위의 카드를 버림 : poll() 맨 위의 카드를 가장 아래의 카드 밑으로 이동 : poll() → add() } 마지막으로 남은 카드 출력 코드 구현하기 /** * 2164) 카드_2 */ public class D0..
✔ 스택 수열 [백준 1874] 문제 분석하기 스택의 원리를 정확하게 알고 있는지 묻는 문제 스택의 pop, push 연산과 후입선출 개념을 이해하여 문제에 접근 손으로 풀어보기 1부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식 이용 현재 수열 값 >= 자연수일 경우 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 스택에 push한 후, 마지막 1회만 pop 현재 수열 값 < 자연수일 경우 pop으로 스택에 있는 값을 꺼낸 후, 꺼낸 값이 현재 수열 값이 아니라면 수열을 표현할 수 없게 됨 자연수 1~4 자연수 5~6 자연수 7~8 4 3 2 1 2 1 6 5 2 1 5 2 1 8 7 5 2 1 슈도코드 작성하기 N(수열 개..
✔ DNA 비밀번호 [백준 12891] 문제 분석하기 시간 제한은 2초이지만 P와 S의 길이가 1000000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘이 필요 이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우 개념을 이용 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 둔 후 윈도우를 오른쪽으로 밀면서 조건에 맞는지 탐색하여 문제에 접근 손으로 풀어보기 S 배열과 비밀번호 체크 배열을 저장 윈도우에 포함된 문자로 현재 상태 배열을 만들고, 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트하고 비밀번호 유효성을 판단 이때 빠지는 문자열과 신규 문자열만 보고 업데이트하는 방식으로 진행 이로인해 부분 문자열의 크기가 크더..
✔ 수들의 합 5 [백준 2018] 문제 분석하기 시간 제한은 2초이지만 N의 최댓값은 10000000으로 매우 크게 잡혀 있으므로 O(n)의 시간 복잡도 알고리즘이 필요 이런 경우 자주 사용하는 방법이 투 포인터 시작 인덱스와 종료 인덱스를 투 포인터로 지정하여 연속된 수를 표현하도록 문제에 접근 손으로 풀어보기 입력받은 값을 N에 저장한 후 사용할 변수를 모두 초기화하고, 결과 변수는 N 하나만 사용하는 경우가 있으므로 1로 초기화 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우를 수를 구함 sum > N : sum = sum - start_index; start_index++; sum < N : end_index++; sum = sum + end_index; sum == ..
✔ 구간 합 구하기 4 [백준 11649] 문제 분석하기 구간 합을 매번 계산한다면 100000 X 100000 가 되므로 최악의 경우 1억 회 이상의 연산을 수행하게 되어 0.5초 안에 모든 구간 합 계산을 끝낼 수 없음 그러므로 구간 합을 이용 손으로 풀어보기 N개의 수를 입력받음과 동시에 합 배열을 생성 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답을 출력 슈도코드 작성하기 suNo(숫자 개수), quizNo(질의 개수) 저장하기 for(숫자 개수만큼 반복하기) { 합 배열 생성하기(S[i] = S[i - 1] + A[i]) } for(질의 개수만큼 반복하기) { 질의 범위 받기(i ~ j) 구간 합 출력하기(S[j] - S[i - 1]) } 코드 구현하기 /** * 11659) 구간_..
✔ 숫자의 합 [백준 11720] 문제 분석하기 N의 범위가 100자리까지 받아야 하지만 10자리까지 가능한 int형, 19자리까지 가능한 long형과 같은 숫자형으로는 담을 수 없음 그러므로 문자열 형태로 입력값을 받은 후 이를 문자 배열로 변환하고, 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함 문자 배열값에서 숫자형으로 변환할 때는 아스키코드를 이용하여 '1' - 48 또는 '1' - '0'과 같이 연산함 손으로 풀어보기 숫자의 개수만큼 입력받은 값을 String형으로 저장함 String형으로 입력받은 값을 char[] 형으로 변환함 인덱스 0부터 접근하여 끝까지 배열을 탐색하며 각 값을 정수형으로 변환하고 결과값에 더하여 누적함 슈도코드 작성하기 N값 입력받기 길이 N의 숫자를 입력받아..
