✔ 스택 수열 [백준 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(수열 개..
✔ 스택과 큐 배열에서 발전된 형태의 자료구조 스택과 큐는 구조는 비슷하지만 처리 방식이 다름 (LIFO ↔ FIFO) ✔ 스택 스택이란? 삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out, FILO : First-in Last-out)로 이뤄지는 자료구조 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가짐 새 값이 스택에 들어가면 top이 새 값을 가리킴 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 됨 스택 용어 top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peak : top 위치에 현재 있는 데이터를 단순 확인하는 연산 스택은 언제 사용할..
✔ DNA 비밀번호 [백준 12891] 문제 분석하기 시간 제한은 2초이지만 P와 S의 길이가 1000000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘이 필요 이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우 개념을 이용 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 둔 후 윈도우를 오른쪽으로 밀면서 조건에 맞는지 탐색하여 문제에 접근 손으로 풀어보기 S 배열과 비밀번호 체크 배열을 저장 윈도우에 포함된 문자로 현재 상태 배열을 만들고, 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트하고 비밀번호 유효성을 판단 이때 빠지는 문자열과 신규 문자열만 보고 업데이트하는 방식으로 진행 이로인해 부분 문자열의 크기가 크더..
✔ 슬라이딩 윈도우 슬라이딩 윈도우란? 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하면서 문제를 해결하는 알고리즘 투 포인터 알고리즘과 매우 비슷하고 원리도 간단 시간 복잡도는 O(N) 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 수들의 합 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 == ..
✔ 투 포인터 투 포인터란? 2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 알고리즘 2개의 포인터를 문제에 주어진 조건에 맞게끔 잘 이동해서 값을 구함 시간 복잡도는 O(N) 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 구간 합 구하기 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의 숫자를 입력받아..
