12865. 평범한 배낭주어진 무게 이하로 물건을 담아서 만들 수 있는 최대 가치를 구하라.특정한 조건을 만족하는 부분집합(과 관련된 계산값)을 구하라.완전탐색 시 시간초과.DP로 문제를 풀어야 한다.12865번: 평범한 배낭2239 - 스도쿠구현백트래킹2239번: 스도쿠1263. 사람 네트워크 2최단 거리플로이드-워샬SW Expert Academy3055. 탈출시뮬레이션BFS3055번: 탈출4014. 활주로 건설시뮬레이션배열SW Expert Academy1249. 보급로최단거리다익스트라SW Expert Academy

1. 문자열 패턴 매칭 문자열 패턴 매칭은 주어진 문자열에서 특정 패턴이 어디에 위치하는지 찾는 알고리즘. 예를 들어, "나는 전선을 간다"라는 문자열에서 "전선"라는 패턴을 찾는 경우가 문자열 패턴 매칭의 한 예다. 검색 엔진, 텍스트 편집기, 데이터베이스 등에서 이용된다. 여러 가지 알고리즘들이 있으며, 각각의 알고리즘은 다른 상황에서 장점을 가짐.  문자열 패턴 매칭 알고리즘설명장점단점Brute force주어진 문자열을 처음부터 하나씩 검사하며 패턴과 일치하는지 확인구현이 간단하다문자열이 길 경우 비효율적이다라빈 카프해시 함수를 이용하여 패턴의 해시값과 문자열의 해시값을 비교평균적으로 빠른 검색 속도해시 충돌로 인해 오동작할 가능성이 있다KMP패턴 내에서의 반복을 찾아내어 검사 횟수를 줄임중복 검사..

1. 플로이드 워샬이란? 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘.시간복잡도 : O(N^3) Dijkstra와 달리 모든 노드 쌍에 대한 최단 거리를 구하고,음의 가중치를 가지는 그래프에서도 쓸 수 있다! 2. 구현 DP로 접근하기 위해 부분 문제를 정의해야 한다. s에서 e까지 가는 데 걸리는 최단거리는 (s->e) 또는 (s->m→e)이다.(s->m→e) = s에서 m까지 가는 데 걸리는 최단거리 + m에서 e까지 가는 데 걸리는 최단거리 int INF = 1000000; // 도달할 수 없음을 의미 (구체적인 값은 문제 따라서 다름)int[][] graph; // 그래프를 나타내는 2차원 배열int n; // 노드의 개수public void floydWarshall() { //..

1. LIS란? Longest Increasing Subsequence최장 증가 부분 수열어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만든다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 뜻한다. 2. LIS의 길이 구하기 동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자.  최장 증가 부분 수열최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주namu.wiki 설명 참고. 가. O(N^2) 시간복잡도는 O(N^2)이다.int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; // 배열의 i번째 요소를 마..

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 0-1 Knapsack: 각 물건을 배낭에 넣거나 넣지 않거나 두 가지 경우만 고려하는 문제.0-N Knapsack: 각 물건을 배낭에 여러 개 넣을 수 있는 문제입니다.Fractional Knapsack: 각 물건을 배낭에 일부분만 넣을 수 있는 문제입니다.: 무게 대비 가치가 높은 물건부터 배낭에 담는 탐욕 알고리즘(Greedy Algorithm)을 이용하여 풀 수 있다.  import java.io.Buf..

0. 문제 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 1. 문제 이해 Greedy 정렬 회의실 배정(Activity-Selection) 문제는 아닌 것 같다. 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ2457 { sta..

11726. 2 x n 타일링메모이제이션모듈러 연산   11726번: 2×n 타일링2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.www.acmicpc.net 11727. 2 x n 타일링 2DP모듈러 연산  11727번: 2×n 타일링 22×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.www.acmicpc.net 5653. 줄기세포배양시뮬레이션  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 1..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 부분집합 시뮬레이션 2. 제출 import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; class SWEA2383 { static int N, min; static List persons, entrys; // 사람들의 좌표, 입구 좌표를 저장 public static void main(String[] args) throws Exception { BufferedReade..