컴퓨터공학 공부/알고리즘 (10) 썸네일형 리스트형 BruteForce (완전탐색) vs DP (동적 프로그래밍) 둘이 무슨 차이점이 있는지 의문이 들어 찾아봤다.1. 브루트포스정말 모든 경우의 수를 다 계산한다. 시간 복잡도가 크다. 2. DP브루트포스의 개선된 버전이다. 값을 저장할 공간이 있다는 것이 가장 큰 차이점이다.한번 계산했던 값을 반복하지 않기 위해 다른 공간에 따로 저장해둔다. DFS, BFS DFS (Depth First Search)깊이 우선 탐색. 특정 분기를 맨 끝단계까지 완벽하게 탐색 후 다른 분기로 이동함.BFS에 비해 느리지만 좀 더 간단하다. BFS (Breadth First Search)너비 우선 탐색. 최대한 넓게 이동한 후 아래로 이동한다.인접한 노드 먼저 탐색 후 이동하는 방식으로, 최단 경로를 탐색할 때 유용하다. 다이나믹 프로그래밍 (DP) 백준 문제풀이 하다가 DP를 사용하는 문제가 나오기 시작해서알고리즘 개념 정리할 겸 포스트를 쓴다. 다이나믹 프로그래밍 (Dynamic Programming) 동적 계획법으로, 큰 문제를 여러개의 작은 문제로 나누어 푸는 기법이다.똑같은 문제를 다시 풀기 때문에 시간이 많이 걸린다는 단점이 있다.하지만 문제 결과를 저장해두면 다시 풀 때 시간 손실이 일어나지 않아 보완 가능하다. 피보나치 수열 등 같은 문제를 계속 풀어야 할 때 사용된다.최적해를 찾을 때 사용된다. [알고리즘] 브루트포스 브루트포스 (Brute Force)브루트 Brute: 무식한포스 Force: 힘직역하면 무식한 힘이라는 뜻이다.가능한 모든 경우의 수를 무식하게 모두 탐색하고, 요구조건에 충족하는 결과를 도출해내는 완전탐색 알고리즘이다.100% 확률로 정답을 찾아낸다는 장점이 있다. NP Complete Problems Class P: Polynomial time (다항시간) 안에 작동되는 알고리즘. Class NP: 다항시간 안에 문제를 풀 수 있는지 없는지 검증 가능한 것. NP Hard: every problem in NP is reducible to Q (NP에 있는 어떤 문제보다도 Q가 어려울 때, Q를 NP hard라고 함.) NP complete: NP에 속해있으면서, NP 속 모든 문제보다 어려운 문제. Polynomial Reductions: 문제 X와 Y가 있을 때, X를 풀 수 있으면 Y도 풀 수 있다. 이것은 곧 X가 Y보다 쉽지는 않다는 것을 뜻한다. Y를 다항시간 안에 X instance 형태로 바꿀 수 있다면, Y를 풀 수 있다. >>Y is polynomial reducible to X. 1.. Big O 알고리즘을 배우면서 시간복잡도에 쓰이는 Big O 가 정확히 어떤 뜻인지 몰랐는데, 이번에 확실히 알아둬야 할 것 같아서 구글링했다. 알고리즘이 빠른지 느린지는 알고리즘의 단계로 판단한다. 단계가 적을수록 빠르고, 단계가 많을수록 느린 알고리즘이다. O(n)이라는 건, 알고리즘의 단계가 n개라는 것이다. Big O는 디테일한 것은 관심없기 때문에, 상수는 제외한다. 2진함수는 O(logn)으로 나타낸다. 2진함수는 input을 반으로 계속 나누기 때문이다. 총 합을 반으로 몇번 나눌 것인가에 따라 결정된다. 문제해결법 ✏컴퓨터로 문제해결하기 ✔Problem: 인풋과 아웃풋을 정확히 파악하는 것이 중요하다. ✔Strategy: 문제풀이 전략을 결정한다. ✔Algorithm: 알고리즘 디자인 - input, output, step ✔Analysis: 분석 ✔Correctness (정확성), time and space, optimality(최적성 - 이것보다 더 적합한 알고리즘이 있는지) ✏알고리즘을 표현하는 2가지 방법 ✔수도코드 ✔순서도 (flow chart) ✏점근적 분석법 ✔데이터의 개수가 n일 때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 방법이다. ✔worst case: 찾는 값이 마지막에 있거나 아예 없을 때. 최대로 수행했을 때의 경우이다 (n번). ✏분석에 쓰이는 수학공식 ✔연속 정수의.. 객체 지향 프로그래밍 입문 - 의존과 DI 배운 내용 정리 의존이란 기능을 구현하기 위해 다른 구성요소를 사용하는 것으로, 객체 생성이나 메서드 호출 등을 뜻한다. 변경된 사항이 있을 경우 그것이 전파될 가능성을 의미하므로 의존하는 대상이 바뀌면 다른 부분 또한 바뀔 가능성이 높아진다. 특히 순환의존을 이용할 경우 변경 연쇄 전파 가능성이 높아져 위험하다. 의존 대상을 줄이기 위해서는 기능별로 분리하거나 기능 구현을 추상화하여 묶는 방법이 있다. 또한, 의존 대상의 객체를 직접 생성하지 않기 위해 팩토리, 빌더, 의존 주입, 서비스 로케이터 등을 쓸 수 있다. 의존 주입은 DI (Dependency Injection)이라고 하는데, 생성자나 메서드를 이용하여 외부에서 의존 객체를 주입시키는 것이다. 스프링 프레임워크 등의 조립기가 객체를 생성하고.. 이전 1 2 다음
