9월 30일은 세미나를 보고 정리한 내용만 올리고 오랜만에 한국으로 돌아온 친구, 타지에서 일하는 친구들이 모두 부산에 모여서 친구들을 만났고, 10월 1일은 부모님과 함께 보냈다. 번아웃으로 조금 힘든 날들을 보내고 있었는데 오랜만에 공부를 잠깐 쉬어가면서 사람들을 만나니 다시 에너지를 얻은 기분이다. 역시 공부와 휴식이 조화를 이룰 때 공부도, 휴식도 잘할 수 있는 게 맞다. 오늘은 본가에 다녀와서 짧게나마 알고리즘 문제풀이와 객체지향의 사실과 오해를 읽고 정리했다. TIL-37 시작하겠다. 백준 4949 자바(Java) 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"..

[백준 18111 자바(Java)] 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 1024 MB 54089 14225 10578 23.922% 문제 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거..

오늘은 프로젝트도 끝났기에, 알고리즘 문제를 풀었다. 알고리즘 문제는 아래와 같다. https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 시간 제한메모리 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 11202 4366 3511 37.773% 문제 다음과 같은 규칙에 따라 수들을 만들려고 한다. 첫 번째 수로 양의 정수가 주어진다. 두 번째 수는 양의 정수 중에서 하나를 선택한다. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수..

https://www.acmicpc.net/problem/11003 1단계 - 문제 분석하기 일정 범위 안에서 최솟값을 구하는 문제 → 슬라이딩 윈도우 + 정렬 일반적인 정렬의 시간 복잡도 nlog(n) → N과 L의 최대 범위가 5,000,000인 이 문제에서 정렬 사용 불가 → O(N)의 시간 복잡도로 해결해야 함. → 슬라이딩 윈도우를 덱(deque)으로 구한하여 정렬 효과를 볼 수 있음 덱은 그림처럼 양 끝에서 데이터를 삽입하거나 삭제 가능한 자료구조이다. 2단계 - 손으로 풀어 보기 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 덱에서 노드를 제거하는 상황 설명을 위 해 (1,1)을 덱에 추가할 때, (2,5)를 덱에 추가할 때 필요한 탐색, 검사 과정 생략 이 상태에서 ..

4. 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하다. [❌][백준 12891] DNA 비밀번호 12891번: DNA 비밀번호 1단계 - 문제 분석하기 P와 S의 길이가 1,000,000으로 매우 큼 → O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 함. 부분 문자열의 길이가 P → 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결 가능 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓는다. 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제 해결 가능 2단계 -..

2. 구간합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘. 코딩 테스트에서 사용 빈도 높음! 구간 합의 핵심 이론 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열. 합 배열을 미리 구해두면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소! A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)이다. 합 배열을 사용한다면 O(1) 안에 답을 구할 수 있다. 합 배열 S를 만드는 공식 S[i] = S[i - 1] + A[i] ..