전체 글 (36) 썸네일형 리스트형 [Algorithm] 06. 스택 (Stack) 스택 (Stack) 스택(Stack)은 마지막에 추가된 데이터가 먼저 출력되는 후입선출(LIFO) 방식으로 데이터를 저장하는 자료구조이다.스택의 top에 데이터를 추가하는 것을 push, 스택의 top에서 데이터를 추출하는 것을 push라고 한다. 스택(Stack)은 Deque 인터페이스를 사용한다. 스택(Stack)을 구현하는 방법에는 Linked List를 기반으로 한 방법과 Deque를 기반으로 한 방법이 있다. Linked List 기반의 Stack Linked List를 기반으로 한 Stack은 선형 자료구조로 LIFO(Last In Fist Out) 방식으로 요소를 처리한다.Deque s = new LinkedList(); Deque 기반의 Stack ArrayDeque를 기반으로 한 .. [Algorithm] 05. 큐 (Queue) 큐 (Queue) 큐(Queue)는 먼저 저장한 데이터가 먼저 출력되는 선입선출(FIFO) 방식으로 데이터를 저장하는 자료구조이다.큐의 앞에서 데이터를 출력하는 것을 dequeue, 큐의 뒤에 데이터를 추가하는 것을 enqueue라고 한다. 큐(Queue)는 Queue 인터페이스를 사용한다.큐(Queue)를 구현하는 방법에는 Linked List를 기반으로 한 방법과 Deque를 기반으로 한 방법이 있다. Linked List 기반의 Queue Linked List를 기반으로 한 Queue는 선형 자료구조로 FIFO(First In Fist Out) 방식으로 요소를 처리한다.이 구조는 삽입과 삭제가 빠르며, 메모리의 동적 할당이 가능하다.Queue q = new LinkedList(); Deque.. [Programmers/JAVA] 05. 전화번호 목록 ※ 전화번호 목록https://school.programmers.co.kr/learn/courses/30/lessons/42577 문제 분석전화번호의 배열 phone_book 이 주어질 때, 한 번호가 다른 번호의 접두어인지 구하는 문제이다.어떤 번호가 다른 번호의 접두사인 경우가 있으면 fasle, 없으면 true 를 반환한다. 접근 방법 정렬 을 사용하여 어떤 번호가 다른 번호의 접두사인지 살펴볼 것이다.어떤 번호가 다른 번호의 접두사일 경우, 정렬된 배열 phone_book 에서 두 번호는 반드시 붙어있게 된다.따라서 배열을 정렬한 후, $i$ 번째 번호가 $i + 1$ 번째 번호의 접두사인지 확인하면 된다. 배열의 길이를 $N$, 전화번호의 길이를 $M$ 이라고 할 때, 정렬에 $O(Nlon.. [Programmers/JAVA] 04. 연속된 부분 수열의 합 ※ 연속된 부분 수열의 합https://school.programmers.co.kr/learn/courses/30/lessons/178870 문제 분석오름차순으로 정렬된 수열 sequence 와 부분 수열의 합을 나타내는 정수 k 가 매개변수로 주어진다.원소의 합이 k 인 부분 수열을 찾을 때, 부분 수열의 시작 인덱스와 마지막 인덱스를 구하는 문제이다.단, 합이 k 인 수열이 여러 개인 경우 길이가 짧은 수열을 찾고, 길이가 같은 경우 시작 인덱스가 작은 수열을 찾는다. 접근 방법 슬라이딩 윈도우 방식을 사용하여 합이 k 인 수열 중 조건에 맞는 수열을 찾을 것이다.윈도우의 시작과 마지막 인덱스를 모두 0에서 시작한다.시작 인덱스부터 마지막 인덱스 사이의 합이 k 보다 작으면 마지막 인덱스를 오른.. [Programmers/JAVA] 03. 예산 ※ 예산https://school.programmers.co.kr/learn/courses/30/lessons/12982 문제 분석부서별 신청 금액이 들어있는 배열 d 와 예산 budget 이 주어질 때, 최대 지원 가능한 부서의 수를 구하는 문제이다.단, 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 주어야 한다. 접근 방법신청 금액이 작을수록 보다 많은 부서의 물품을 지원해 줄 수 있을 것이므로 정렬 을 이용할 것이다. 부서의 개수가 $N$개 일 경우, 정렬의 시간 복잡도는 $O(NlogN)$이고 예산 분배의 시간 복잡도는 $O(N)$이다.따라서, 평균 시간 복잡도는 $O(NlogN + N) == O(NlogN)$이다. 코드 설계# 지원 가능한 부서의 개수를 저장할 변수 re.. [Programmers/JAVA] 02. 소수 만들기 📄 소수 만들기https://school.programmers.co.kr/learn/courses/30/lessons/12977 문제 분석배열 nums 안의 숫자 중 서로 다른 3개의 수를 더했을 때, 소수가 되는 경우의 개수를 구하는 문제이다. 접근 방법 완전 탐색 을 이용하여 서로 다른 3개의 숫자를 선택하고 그 합이 소수가 되는 경우의 개수를 구한다. 주어진 숫자를 $N$, 배열 nums 의 크기를 $K$라고 할 때, 시간 복잡도는 $O(NK^{3})$이다.$N = 3a$ 인 경우, $N$은 $I = 3$ 일 때와 $I = a$ 일 때 모두 $N$을 나누어 떨어지게 한다.따라서 $I$는 $I^{2} = N$이 되는 경우까지 확인하면 되므로 시간 복잡도는 $O(\sqrt{N}K^{3})$이다... [Programmers/JAVA] 01. 완주하지 못한 선수 📄 완주하지 못한 선수https://school.programmers.co.kr/learn/courses/30/lessons/42576 문제 분석마라톤에 참가한 선수의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion 이 주어진다.이 때, 완주하지 못한 선수의 이름을 리턴하는 문제이다. 접근 방법 완전 탐색 을 사용하여 두 배열의 값이 동일하면 공백으로 치환한다.for 문을 사용하여 공백으로 치환 된 participant 배열의 값 중 공백이 아닌 값을 리턴한다. 배열의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(n^{2})$이다.N">$N$은 최대 $10^{5}$이므로 최대 수행 횟수는 $10^{10}$이고, 따라서 효율성 테스트에서 통과할 수 .. [Leetcode/JAVA] 01. Two Some 📄 Two Somehttps://leetcode.com/problems/two-sum/ 문제 분석정수 배열 nums 의 원소 중 합이 target 인 두 숫자의 인덱스를 반환하는 문제이다. 접근 방법 완전 탐색 을 이용하여 for 문을 통해 합이 target 인 두 원소를 찾을 것이다. 정수 배열 nums 의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(N^{2})$이다.$N$은 최대 $10^{4}$이므로 최대 수행 횟수는 $10^{8}$이고, 따라서 시간 초과에 걸리지 않는다. 코드 설계# 결과를 저장할 배열 result 를 선언한다.# 이중 for 문을 돌며 배열 nums 에서 두 수를 선택하고, 두 수의 합이 target과 같으면 숫자의 인덱스를 반환한다. 코드 구현class Solutio.. 이전 1 2 3 4 5 다음
