Computer_Science/Algorithm
-
탐욕 알고리즘 tipsComputer_Science/Algorithm 2019. 2. 3. 10:38
이 글은 SW EXPERT ACADEMY의 파이썬 SW문제해결 응용_구현 - 03 탐욕 알고리즘을 학습하고 내용을 정리한 글입니다.(https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT) 탐욕 알고리즘 수행 과정1. 해 선택- 현재 상태에서 부분 문제의 최적해를 구한 뒤, 부분 해 집합(solution set)에 추가- 하나의 선택이 이루어지면 새로운 부분 문제 발생2. 실행 가능성 검사 실시- 새로운 부분 해 집합의 실행가능 여부 확인- 문제의 제약 조건 위반을 검사 3. 해 검사- 새로운 부분 해 집합이 문제의 해가 되는지 확인- 전체 문제의 해가 ..
-
계산기하의 도구들 #알고리즘문제해결전략 ch.15Computer_Science/Algorithm 2019. 2. 1. 21:02
벡터 내적 외적 내적 사용 용도1. 벡터의 사이각 구하기 (cos값으로부터 사이각 추출) 2. 벡터의 직각 여부 확인 (내적의 값이 0이라면 직각)3. 벡터의 사영 (하나의 벡터가 다른 벡터로 내리는 사영의 크기 구하기)벡터 a가 b위에 내리는 사영을 구하고 싶다면 b의 단위벡터와 a를 내적하면 됨 외적 사용 방법 외적으로 반환되는 벡터의 길이와 방향 을 유용하게 쓰면 됨 a=(ax,ay) , b=(bx,by) axb =ax*by-ay*bx = |a|*|b|*sin() (계산하는 방법) (계산하는 목적) 용도 1. 면적 계산하기 (두 벡터가 만드는 평행사변형의 넓이를 구할 수 있음)2. 두 벡터의 방향 판별 (a에서 b까지 반시계방햐으로 얼마나 회전해야 하는가)sin이 양수이면 반시계 방향으로 180도 ..
-
최적화 문제 결정 문제로 바꿔 풀기 #알고리즘문제해결전략 ch.12Computer_Science/Algorithm 2018. 12. 28. 23:02
이 글은 '알고리즘 문제해결전략' (저자 구종만 , 출판사 인사이트)의 12번째 챕터(최적화 문제 결정 문제로 바꿔 풀기)의 내용을 정리한 글입니다. (https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=21089176) 알고리즘을 설계할 때, 어느 한 지점, 조합에 대해 대답하는 알고리즘보다 임의로 설정한 구간에 대해 대답하는 알고리즘을 설계하는 것이 더 쉬울 때가 있습니다. 예를 들어, 술게임(...)에서 많이 하는 1에서 50사이의 숫자 맞추기 게임은 두가지 버전이 있을 수 있을 것입니다 . 1. 어느 한 숫자를 부르면 그 숫자가 정답인지 아닌지만 알려주는 방식 2. 어느 한 숫자를 부르면 정답인 숫자가 더 큰지 작은지 알려주는 방식 당연히 2번 방식의 게임이..