알고리즘

[Java] 문자열 패턴 매칭

작성자:
Featured image for [Java] 문자열 패턴 매칭

1. 문자열 패턴 매칭 문자열 패턴 매칭은 주어진 문자열에서 특정 패턴이 어디에 위치하는지 찾는 알고리즘. 예를 들어, “나는 전선을 간다”라는 문자열에서 “전선”라는 패턴을 찾는 경우가 문자열 패턴 매칭의 한 예다. 검색 엔진, 텍스트 편집기, 데이터베이스 등에서 이용된다. 여러 가지 알고리즘들이 있으며, 각각의 알고리즘은 다른 상황에서 장점을 가짐. 문자열 패턴 매칭 알고리즘 설명 장점 단점 Brute … 더 읽기

[Java] 플로이드 워샬

작성자:
Featured image for [Java] 플로이드 워샬

1. 플로이드 워샬이란? Dijkstra와 달리 2. 구현 DP로 접근하기 위해 부분 문제를 정의해야 한다. n개의 노드를 가진 그래프에서 플로이드 워샬 알고리즘을 통해 각 노드 간의 최단 거리를 구하는 예시 코드다. INF는 무한을 의미하는 값으로 설정하였고, graph는 그래프를 나타내는 2차원 배열입니다. 플로이드-워샬에서 핵심 아이디어는 경유지를 하나씩 추가해 가며 비용을 최적화하는 것이다. 마지막 경유지를 추가하는 시점에서는 모든 … 더 읽기

[Java] LIS, LCS

작성자:
Featured image for [Java] LIS, LCS

  1. LIS란? 2. LIS의 길이 구하기 동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자. 최장 증가 부분 수열 최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주 설명 참고. 가. O(N^2) 이 알고리즘에서, dp[i]는 배열의 i번째 요소를 마지막으로 하는 LIS의 길이를 저장한다. 배열의 모든 … 더 읽기

[Java] Knapsack

작성자:
Featured image for [Java] Knapsack

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 2. 공간 복잡도 개선 기존의 동적 계획법(DP)은 O(NK)의 공간 복잡도를 가지고 있다. (여기서 N은 물건의 개수, K는 배낭의 최대 무게를 … 더 읽기

[알고리즘] 12891. DNA 비밀번호

작성자:
Featured image for [알고리즘] 12891. DNA 비밀번호

0. 문제 12891번: DNA 비밀번호 1. 문제 이해 수학 잘 못함. 2. 제출 조건을 만족하는 부분 순열을 구하는 문제다. 매번 문자열을 새로 카운팅하면 시간을 초과한다. 슬라이딩 원도우를 사용해서 나가는 것과 들어오는 것만 체크한다.

[알고리즘] 2023. 신기한 소수

작성자:
Featured image for [알고리즘] 2023. 신기한 소수

0. 문제 2023번: 신기한 소수 1. 시간초과 2. 시간 줄이기 위를 바탕으로 코드를 최적화한다. 먼저 수(i)를 만들고 특정 자리까지만 숫자(num)를 가져오기 위해서 Math.pow()를 사용했다. 무조건 숫자(i)를 만들고 각 자리의 수가 2, 3번 조건을 만족하는지 확인하다 보니 불필요한 연산이 발생했다. 1번과 2번 조건을 만족하는 숫자만 생성하고 3번 조건을 만족하는지 확인하면 불필요한 연산을 줄일 수 있다. 재귀함수로 … 더 읽기

[Java] Stack, Queue, Priority Queue

작성자:
Featured image for [Java] Stack, Queue, Priority Queue

1. Stack Stack underflow와 overflow를 조심하자. 2. Queue Java의 java.util.Queue는 interface다. 구현체로는 대표적으로 ArrayDeque 또는 LinkedList를 사용한다. 대부분의 상황에선 LinkedList보다는 ArrayDeque를 사용하자. ArrayDeque 양쪽 끝에서 삽입, 삭제하기에 효율적이다. 3. Priority Queue 기본은 오름차순으로 정렬한다. 정렬의 순서를 자신이 원하는 방법으로 바꾸고 싶다. → Comparator를 추가한다. 또는 Comparable을 구현해도 된다. Data Structure Insertion Time Complexity Deletion Time … 더 읽기

[Java] 부분집합

작성자:
Featured image for [Java] 부분집합

  종류 설명 기호 시간 복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! /( r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 집합에 포함된 원소들을 선택하는 것. 원소들의 그룹에서 최적의 부분 … 더 읽기

[알고리즘] 풀었던 문제 (240202)

작성자:
Featured image for [알고리즘] 풀었던 문제 (240202)

1. 23300. 웹브라우저 2 Stack 23300번: 웹 브라우저 2 2. 2164. 카드 2 Queue 2164번: 카드2 3. 5432번. 쇠막대기 자르기 Stack SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 4. 1158. 요세푸스 문제 Queue 1158번: 요세푸스 문제 5. 1218. 괄호 짝짓기 Stack SW Expert Academy SW 프로그래밍 역량 강화에 도움이 … 더 읽기