그랬었습니다

지식 표현 데이터(data) 특정 분야에서 관측된 아직 가공되지 않은 것 사실인 것처럼 관측되지만 오류나 잡을을 포함할 수 있다. 정보(information) 데이터를 가공하여 어떤 목적이나 의미를 갖도록 한 것 지식(knowledge) 정보를 취합하고 분석하여 얻은 대상에 대해 사람이 이해한 것 지혜(wisdom) 경험과 학습을 통해서 얻은 지식보다 높은 수준의 통찰 지식 경험이나 교육을 통해 얻어진 전문적인 이해와 체계화된 문제 해결 능력 어떤 주제나 분야에 대한 이론적 또는 실제적인 이해, 또는 현재 알려진 사실과 정보의 모음 암묵지(tacit knowledge) 형식을 갖추어 표현하기 어려운, 학습과 경험을 통해 쌓은 지식 형식지(explicit knowledge) 비교적 쉽게 형식을 갖추어 표현..

제약조건 만족 문제(constraint satisfaction problem) 주어진 제약조건을 만족하는 조합 해(combinatorial solution)를 찾는 문제 ex) N Queen problem 탐색 기반의 해결 방법 backtracking search(백트래킹 탐색) DFS를 하는 것처럼 변수에 허용되는 값을 하나씩 대입 모든 가능한 값을 대입해서 해가 없으면 이전 단계로 돌아가서 이전 단계의 변수에 다른 값을 대입 constraint propagation(제약조건 전파) 인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식 최적화(optimization) 여러 가지 허용되는 값들 중에서 주어진 기준을 가장 잘 만족하는 것을 선택하는 것 목적 함수(objectiv..

게임 트리(game tree) 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리 (tic-tac-toe, 바둑, 장기, 체스 등) 게임의 결과는 마지막에 결정 많은 수(lookahead)를 볼 수록 유리 mini-max 게임 트리 MAX 노드 = 자신에 해당하는 노드. 자기에게 유리한 최댓값 선택 MIN 노드 = 상대방에 해당하는 노드. 최소값 선택 단말 노드부터 위로 올라가면서 최소(minimum)-최대(maximum)연산을 반복하여 자신이 선택할 수 있는 방법 중 가장 좋은 값을 결정. 일반적으로 게임이 끝나는 시점까지 수를 보기 어렵기 때문에, 어느 정도 깊이의 수까지 본 다음에 해당 상태에서 유리한 정도를 판정(휴리스틱 이용)하여 이를 바탕으로 최선의 방법을 선택. α-β 가지..

정보이용 탐색(Informed search) 상태 공간에 대한 정보를 이용하여 탐색 효율을 높이는 탐색 휴리스틱 탐색(heuristic search)이라고도 한다. 휴리스틱(heuristic) = 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림짐작하는 것을 의미. 휴리스틱을 사용하는 탐색 방법으로 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A* 알고리즘 등이 있다. 검색 효율은 좋으나 일반적으로 최적해를 찾는다는 보장은 하지 못한다. 어떤 휴리스틱을 사용하는가에 따라 성능 차이가 크게 나타날 수 있다. 언덕 오르기 방법(hill climbing method) 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한..

탐색(Search) = 문제의 해(Solution)가 될 수 있는 것들의 집합을 공간(Space)으로 간주하고 문제의 최적해를 찾기 위해 공간을 체계적으로 찾는 것. 상태(State) = 특정 시점에 문제의 세계가 처해있는 모습. 세계(World) = 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭하는 말. 해(Solution) = 문제의 요구조건을 최적으로 만족하는 것. 상태 공간(State space) = '문제의 초기 상태로부터 도달할 수 있는 모든 상태의 집합', '문제의 해가 될 가능성이 있는 상태들의 집합' 초기 상태(Initial state) = 문제가 주어진 시점의 시작 상태 목표 상태 = 문제에서 원하는 최종 상태 상태 공간 그래프(State space graph) = 상태 공간에서..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std; int countLine(int N); class Line {private: int A, B;public: void setLine(int A, int B) { this->A = A; this->B = B; } bool operatorA B; }}; int main() { int N; scanf("%d", &N); printf("%d\n", countLine(N));} int countLine(int N) {..

https://everyyy.tistory.com/75 [백준]11053-가장 긴 증가하는 부분 수열(Dynamic Programming) 이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i].. everyyy.tistory.com 11053번 가장 긴 증가하는 부분 수열 문제와 매우 흡사하고, 위 문제를 조금만 변형해면 풀 수 있는 문제이다. 우선 똑같이 가장 긴 증가하는 부분 수열을 구한다. 동시에 오른쪽에서 왼쪽으로 가면서 가장 긴 감소하는 부분 수열을 구한다. 왼쪽에서 오른쪽으로 이동하며 반환할 후보 변수에 일단 증가, 감소 중 더 ..

이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i][1]이 i번째 수의 값을 증가수열의 마지막 수로 잡았을 경우 가장 길게 만들 수 있는 증가수열의 길이라고 한다면, v[i][0] i)라면 v[i][1] < v[j][1]이다. 이 말이 무슨 말이냐면, 주어진 수열의 어떠한 값이 그보다 왼쪽에 있는 수열보다 크다면, 그 수를 마지막으로 하여 만들 수 있는 증가수열의 길이는 왼쪽에 위치한 그보다 작은 값을 마지막으로 하여 만들 수 있는 증가수열의 길이보다 길다. 라는 것이다. 따라서 풀이는 간단하다. 왼쪽에서부터 오른쪽으로 진행하면서 하나씩 ..

이 문제는 2579번 계단 오르기 문제와 매우 흡사하다. 다만 하나의 조건이 빠졌다. 다만 그 조건이 계산의 편의를 돕는 조건이었기 때문에 조건이 빠졌다고 계산이 쉬워진 게 아니라, 중간에 하나의 계산이 추가됐다. https://everyyy.tistory.com/71 [백준]2579-계단 오르기(Dynamic Programming) 계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법. 그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다. 조금 관점을 바꿔서, 올라올 계단의 입.. everyyy.tistory.com 일단은 위 포스팅을 참고하면 좋다. 계단 오르기에서는 있었지만 이 문제에서 없어진 조건은 "무조건 1칸이나 2칸을 전진해야 한..

정답률이 30퍼도 안되는 문제다. 근데 솔직히 정답률 더 높은 계단 오르기나 1로 만들기 문제보다 쉽게 느껴졌다. 왜지..? 요즘 동적 계획법 문제를 많이 풀어서 익숙해졌나? 아무튼.. 이 문제는 의외로 간단하다. 중복을 생각할 필요가 없다. 대신 예외를 생각해야한다. 1에서 파생되는 수는 10, 12가 있다. 2에서는 21, 23이 있다. 등등.. 그럼 두 자리 숫자로 넘어가보자. 10에서 파생되는 수는? 101뿐이다. 89에서 파생되는 수는? 898뿐이다. 나머지는 모두 끝 자리 숫자에 1을 빼고 더하는 두 가지 경우가 나온다. 복잡하게 생각하지 말고 맨 끝자리만 보면 된다. 길이 N인 계단 수 중에서 끝자리가 0인 수의 개수는? 길이 N - 1인 계단 수 중에서 끝자리가 1인 수의 개수와 같다. 끝..