본문 바로가기

Algorithm

 (15)
[Leetcode/JAVA] 03. Daily Temperatures 📄 Daily Temperatureshttps://leetcode.com/problems/daily-temperatures/  문제 분석현재 기온보다 기온이 높아지는 날 까지 걸리는 일 수를 구하는 문제이다.조건) 현재 기온보다 기온이 높아지는 날이 없으면 0을 반환한다. 접근 방법 완전탐색 을 이용하여  for 문을 통해 배열을 순회하며 현재 기온보다 높은 기온을 가지는 날을 구한다.이중 for 문을 통해 배열을 순회하며 현재의 온도보다 높은 기온을 가지는 날을 구한다. 배열의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(N^{2})$이다.  코드 설계# 결과를 저장할 배열 result 를 선언한다.# 현재 날짜의 인덱스를 cur, 이후 날짜의 인덱스를 next 라고 하고 이중 for 문을 수행한..
[Leetcode/JAVA] 02. Valid Parentheses 📄 Valid Parentheseshttps://leetcode.com/problems/valid-parentheses/description/  문제 분석문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 문제이다.조건 1) 열린 괄호는 같은 유형의 괄호로 닫아야 한다.조건 2) 열린 괄호는 올바른 순서로 닫아야 한다.조건 3) 모든 닫힌 괄호에는 같은 유형의 열린 괄호가 대응된다. 접근 방법 스택 을 이용하여  for 문을 통해 문자열을 순회하며 열린 괄호를 만나면 스택에 삽입할 것이다.문자열을 순회하며 닫힌 괄호를 만나면 스택에서 짝을 이루는 괄호가 있는지 확인한다.문자열을 순회한 후, 스택이 비어있다면 유효한 괄호이고 아니라면 유효하지 않은 괄호이다. 문자열의 크기를 $N$이라고 할 때, 시간 ..
[Algorithm] 07. 문자열 문자열 문자는 char 타입으로, 문자열은 String 클래스로 표현이 가능하다.  💡  char 타입 char 타입은 문자 하나를 의미하며 작은 따옴표를 사용하여 표현한다.char c = 'a';char[] str = {'a', 'p', 'p', 'l', 'e'};  💡  String 클래스 String 클래스는 문자열을 큰 따옴표로 감싸서 표현한다. 즉,  스트링 리터럴(String literal)을 사용한다.String str = "apple";// 숫자 타입을 문자열 타입으로 변경String num = String.valuOf(3); //char 타입의 배열로부터 문자열 생성char[] strArray = {'a', 'p', 'p', 'l', 'e'};String strCreate = ne..
[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..

티스토리툴바