분류 전체보기 (42) 썸네일형 리스트형 IntelliJ Gradle 리프레시 | Gradle 안 보일 때 오늘도 어김없이 만난 빨간줄 오늘은 import를 안 해서 생겼다 build.gradle 열어서 오른쪽에 떠있는 코끼리 누르라고 하는데 난 코끼리가 없었다. 물론 오른쪽 gradle 여는 바도 없었음 이럴 땐 하나하나 찾아가 줘야지 View → Tool Windows → Gradle....... 로 가야 하는데 여기에도 Gradle이 없다..? 찾아보니 종종 내 프로젝트를 gradle로 인식을 못할 때가 있다고 한다 build.gradle 우클릭 → Link Gradle Project 이제 오른쪽에 Gradle 툴바가 생긴 것을 볼 수 있다. 여기서 리프레시 눌러주면 빨간줄 해결 완료 자주 사용하는 인텔리제이 단축키(window기준) 이클립스랑 단축키가 조금 달라서 정리해 보는 인텔리제이 단축키 RUN Ctrl + Shift + F10 창 크게 보기 Ctrl + Shift + F12 프로젝트 / 에디터 창 포커스 on/off Alt + 1 한 줄 복사 Ctrl + D 한 줄 삭제 Ctrl + Y 줄 위/아래 이동 Ctrl + Shift + ↑/↓ Getter / Setter / Constructor Alt + Insert 폴더 및 파일 생성 Alt + Insert import 적용 Alt + Enter 사용하지 않는 import 정리 Ctrl + Alt + O 리턴값에 맞는 변수 자동 생성 Ctrl + Alt + V 함수 필요 인자값 확인 Ctrl + P Override 자동완성 Ctrl + I 코드 자동 정렬 Ctrl + Alt +.. 분기 한정 기법 (Branch-and-Bound) 백트래킹 기법 (Backtracking) 문제의 조건에 따라 해를 깊이 우선 탐색으로 찾음 최적화 문제에 대해서는 최적해가 상태 공간 트리의 어디에 있는지 알 수 없으므로, 트리에서 대부분의 노드를 탐색해야 하고 입력의 크기가 커지면 해를 찾는 것이 거의 불가능 이러한 단점을 보완한 탐색 기법이 분기 한정 기법 분기 한정 기법 (Branch-and-Bound) 상태 공간 트리의 각 노드에 특정한 값(한정값)을 부여 노드의 한정값을 활용하여 가지치기를 함으로써 백트래킹 기법보다 빠르게 해를 찾음 분기 한정 기법에서는 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색으로 해를 찾음 해 탐색 원리 1. 최적해를 찾은 후에 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색 X (가.. 동전 거스름돈 문제 동전 거스름돈 문제 대부분의 경우 그리디 알고리즘으로 해결되나, 그렇지 않은 경우도 존재 ex) 거스름돈이 20원일 때 동전이 16원, 10원, 5원, 1원인 경우(그리디는 16원 1개, 1원 4개의 결과가 나옴) DP 알고리즘은 모든 동전 거스름돈 문제에 대해 항상 최적해를 도출 앞서 했던 배낭 문제의 DP 알고리즘에서 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결한 것처럼 거스름돈을 1원씩 증가시켜가며 문제를 해결 C[n] = n원을 거슬러 받을 때 사용되는 최소의 동전 수 ◼ 500원 동전이 필요하면 (n-500)원의 해(C[n-500])에 500원 동전 1개 추가 ◼ 100원 동전이 필요하면 (n-100)원의 해(C[n-100])에 100원 동전 1개 추가 ◼ 50원 동전이 필요하면 (n-50).. 배낭 문제 배낭 문제 n개의 물건과 각 물건 i의 무게 wi와 가치 vi가 주어지고, 배낭의 용량이 C일 때, 배낭에 담을 수 있는 물건의 최대 가치를 구하는 문제 (각 물건은 1개씩만 존재) 배낭의 용량이 0(kg)부터 1(kg)씩 증가하여 최종 용량인 C(kg)가 될 때까지 변화시켜 가며 배낭의 용량 내에서 어떤 물건을 담았을 때 가치가 더 커지는지를 결정 임시 배낭 용량 : 배낭 용량은 C(kg)이지만 배낭 용량이 0(kg)부터 1(kg)씩 증가할 경우의 배낭 용량 K[i, w] = 물건 1 ~ i까지만 고려하고, (임시) 배낭의 용량이 w일 때의 최대 가치 ∴ K[n, C] = 구하고자 하는 최종해 두 가지 경우가 존재 ① 물건 i의 무게 > 임시 배낭 용량 ② 물건 i의 무게 임시 배낭 용량 물건 i를 배.. 편집 거리 편집 거리 (Edit Distance) 삽입(insert), 삭제(delete), 대체(substitute) 연산을 사용하여 스트링 S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 예제 S = strong T = stone E[i, j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집 거리 E[4, 3] = 'strong' → 'stone'에 대해서, 'stro'를 'sto'로 바꾸기 위한 편집 거리 s1 → t1 ['s' → 's'] : s1 = t1 = 's' 이므로 E[1, 1] = 0 s1 → t1t2 ['s' → 'st'] : s1 = t1 = 's'이고, 't'를 삽입하므로 E[1, 2] = 1 s1s2 → t1 ['st' → 's'] :.. 모든 쌍 최단 경로 찾기 (플로이드 워셜 알고리즘) 동적 계획 알고리즘 (Dynamic Programming; DP) 입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 분할 정복 알고리즘과 유사한 부분이 많으나 DP는 같은 부분 문제를 다시 풀지 않는다는 점, 부분 문제의 해를 중복 사용한다는 점에서 정복 기법과 다름 모든 쌍 최단 경로 (All Pairs Shortest Paths) 찾기 각 쌍의 점 사이의 최단 경로 다익스트라 알고리즘을 이용한다면 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 플로이드-워셜 알고리즘 워셜(Warshall) : 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 플로이드(Floyed).. 백트래킹 기법 (Backtracking) 백트래킹 기법 (Backtracking) 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 깊이 우선 탐색을 통해 해를 찾음 TSP(Traveling Salesman Problem)를 위한 백트래킹 알고리즘 tour = [] : 방문한 지점(방문 순서) bestSolution = (tour, tour의 거리) : 현재까지 찾은 가장 거리가 짧은 해 BacktrackTSP(tour) 함수 ① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때) ② tour가 완전하지 않을 때 (모든 지점을 방문하지 않았을 때) ① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때) 만약 tour의 거리가 bestSolution의 거리보다 작으면 bestSolution = (tour, .. 이전 1 2 3 4 5 6 다음
