Algorithm with Java

[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는 배낭의 최대 무게를 … 더 읽기

[알고리즘] 2457. 공주님의 정원

작성자:
Featured image for [알고리즘] 2457. 공주님의 정원

0. 문제 2457번: 공주님의 정원 1. 문제 이해 회의실 배정(Activity-Selection) 문제는 아닌 것 같다. 2. 제출 어떤 것을 기준으로 정렬할지 판단하는 것이 어려웠다. 3월 1일부터 11월 30일까지 하루도 빠짐없이 꽃을 피워야 하기 때문에 꽃이 피는 날이 빠른 순서로 정렬했다.

[알고리즘] 풀었던 문제 (240227 ~ 29)

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

11726. 2 x n 타일링 11726번: 2×n 타일링 11727. 2 x n 타일링 2 11727번: 2×n 타일링 2 5653. 줄기세포배양 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1941. 소문난 칠공주 1941번: 소문난 칠공주

[알고리즘] 2383. 점심식사시간

작성자:
Featured image for [알고리즘] 2383. 점심식사시간

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 이런 소위 “시간 관리”를 해야 하는 문제는 보통 특정 상황에서 어떻게 동작하는지 자세하게 분석해 준다. 올바르게 구현했는지 확인하기 위해서 모든 부분집합에 대하여 실행하지 말자. go(new int[]{0,0,0,1,1,1}, true);로 예시와 동일한 상황으로 테스트하는 것이 도움이 되었다. “시간 … 더 읽기

[알고리즘] 1767. 프로세서 연결하기

작성자:
Featured image for [알고리즘] 1767. 프로세서 연결하기

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 가. 오답 근본 없이 풀었다. 완탐으로 풀면 비효율적이라고 생각해서 그랬다. 나. 완전 탐색으로 풀기 진짜 일부의 유명한 그리디 알고리즘을 제외하고선 완전탐색으로 풀자.주어진 시간 안에 문제를 풀어야 하는데 머리 아프게 고민할 시간이 없다.근본 있게 풀기.