-
[SWEA] 1247. 최적 경로 -DPProblem_Solving/DP 2019. 2. 3. 19:38
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE 문제를 읽고 짧은 시간 안에 해결해야 하는 문제인줄 알고 겁부터 먹었지만 모든 가능한 경로를 살펴서 해를 찾아도 좋다기에 신나는 마음으로 완전 탐색을 적용할 생각을 했습니다. ㅎㅎ 문제 형태를 보아하니 주로 쓸 함수를 이렇게 정의하면 좋을것 같더라고요. ㅎㅎ visited에는 현재까지 방문한 고객들을 비트마스크를 이용해서 표현하고, last는 마지막으로 방문한 고객의 index를 ..
-
탐욕 알고리즘 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. 해 검사- 새로운 부분 해 집합이 문제의 해가 되는지 확인- 전체 문제의 해가 ..
-
[SWEA] 3752. 가능한 시험 점수 -DP카테고리 없음 2019. 2. 2. 23:17
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn 완전 탐색과 DP를 적용하는 방법 말고는 다른 방법이 떠오르지 않네요... 이 문제는 DP를 적용했을 때 어느 정도의 시간 복잡도일지 계산하는게 너무 어려워서 선뜻 DP를 적용하기 고민됐던것 같네요. DP를 설계할때 핵심이 됐던 함수 는 현재까지 계산한 점수와, 현재 위치를 인자로 받아서 앞으로 더 만들 수 있는 새로운 수를 반환하게 했습니다. 이 DP를 위한 cache입니다 n이 100이하고 각 숫자가 100이하 이므로 최대 num은 10000 이고, pos의..
-
[SWEA] 2819. 격자판의 숫자 이어 붙이기 -DPProblem_Solving/DP 2019. 2. 2. 16:43
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE 사실 다 풀고 나서다른 분들이 풀고 블로그에 올린 풀이들을 봤는데.... 거의 다 DFS로 접근하시더라고요.... 풀고 나서 보니까 '아 그러게 DFS로 생각하기 딱 좋네...' 싶네요 ㅋㅋㅋㅋ 그리고 거의 STL에 있는 set을 많이 사용하셨는데 저는 그걸 몰라서...ㅠㅠㅋㅋㅋㅋ 좀 다른 방식으로 접근 했습니다! 먼저 몇개를 만들 수 있냐는 질문에 처음으로 들었던 생각은 6칸씩 ..
-
계산기하의 도구들 #알고리즘문제해결전략 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도 ..
-
"프로그래머가 몰랐던 멀티코어 CPU 이야기" #Story 02_프로세서의 언어 : 명령어 집합 구조Computer_Science/Computer_Design 2018. 12. 31. 18:41
프로그래머가 몰랐던 멀티코어 CPU 이야기 (김민장 (지은이) | 한빛미디어 | 2010-05-28) https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=7086498 이 글은 위 책을 읽으며 공부한 내용을 정리한 글입니다. "프로그래머가 몰랐던 멀티코어 CPU 이야기" #Story 02_프로세서의 언어 : 명령어 집합 구조 내용 현재 프로세서의 상태ex) -레지스터의 상태 (gdb 명령 : info reg) -지금까지 어떤 경로로 함수들이 호출되었는지 알려주는 호출 스택(gdb 명령 : backtrace)-문자열이 담겨 있는 메모리 (gdb 명령 : x/s) 와 같은 것들을 컴퓨터 구조적 상태(architectual state)라고 부른다. 프로세서는 구조적 상태..