Algorithms/simulation90 알고리즘 문제 해결 전략 1권 4.6 수행 시간 어림짐작하기 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많음. 1억이라는 기준은 가능한 한 보수적으로 정한 것임 4.7 계산 복잡도 클래스 : P, NP, NP-완비 일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들을 빠르다고 말합니다 P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부릅니다. 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기란 어렵습니다. 주어진 배열을 비교 정렬하는 문제와 최소치를 찾는 문제의 난이도를 비교하면, 정렬 문제는 최소치 문제 이상으로 어렵다고 말할 수 있습니다. NP문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미합니다. 이런 속성을 갖.. 2021. 5. 14. 알고리즘 문제 해결 전략 4.6 수행 시간 어림짐작하기 book.algospot.com/estimation.html 알고리즘 문제 해결 전략 4.6 수행 시간 어림짐작하기 주먹구구 법칙 프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결 book.algospot.com "입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 합니다." "프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많기 때문입니다. CPU의 클록 속도, 1클록마다 수행 할 수 있는 CPU 명령어의 수, 프로그램의 메모리 접근 패턴, 운영 체제와 컴파일러의 버전, ..., 목록을 만들자면 끝이 없습니다." "그러나 많은 경우에는.. 2021. 5. 6. [LeetCode] Squares of a Sorted Array leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3240/ - 정수 숫자가 담긴 배열이 주어집니다. 그것은 오름차순으로 정렬되어있습니다. 그것의 제곱들을 오름차순으로 리턴하세요. - 음수 시작인 경우 양수로 전환 하는 곳을 지점으로 오른쪽 i, 왼쪽 j 인덱스를 비교하면서 작은 수부터 배열에 담으면 됨. 같을 경우 아무거나 상관없음. i를 해도 됨. 처음과 끝 인덱스를 넘어가지 않도록 조심하면 됨. - 양수 시작인 경우는 바로 배열에 담으면 됨. - O(N) 풀이법이 있음... 으음.... class Solution { public: vector sortedSquares(vector& nums) { vector newArr; int l,.. 2021. 5. 5. [leetcode] Find Numbers with Even Number of Digits leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3237/ - 주어진 정수 배열안에서, 짝수 자릿수를 가진 숫자의 수를 리턴하세요. - 예를 들어 12면 10의 자리이므로 오케이. 1234도 자릿수가 4이므로 오케이. - 10진수로 표현했으므로, 10진수로 풀이하는 방법이 생각남. - 제약조건은 배열 안의 숫자가 최대 500개, 그리고 하나의 숫자는 10^5이 최대임. class Solution { public: int findNumbers(vector& nums) { int result = 0 ; int check = 0; for(int i=0; i 2021. 5. 5. 종만북 p14~23 "가능한 한 많은 문제 풀기 프로그래밍 대회를 제대로 준비하기 위해 공부해야 할 주제는 굉장히 많습니다. 예를 들어 이 책은 전체 서른두 개 장이나 되는데, 이것으로도 대회에 필요한 주제를 전부 다룰 수는 없습니다. ... 그러나 복잡한 알고리즘을 하나 더 아는 것보다는 실제로 자신이 아는 것을 이용해 문제를 풀 수 있는 능력이 훨씬 더 중요합니다. ... 이런 경험과 능력은 실제 문제를 직접 풀어 보는 과정에서만 기를 수 있으므로 ... " "가능한 한 많은 프로그래밍 대회에 참가하기 실제 대회에 참가해서 다른 사람과 경쟁하는 경험은 혼자서 문제를 푸는 것보다 훨씬 많은 도움과 자극이 됩니다. 그것이 인터넷 모의고사라고 하더라도 대회가 끝난 뒤 혼자서 연습하는 것보다 훨씬 도움이 되기 때문에 가능한 한.. 2021. 5. 2. Topcoder SRM 연습하기 www.acmicpc.net/blog/view/2 Topcoder SRM 연습하기 Topcoder의 주소는 http://community.topcoder.com/tc 입니다. 아직 가입하지 않은 분은 이 곳에 들어가서 회원 가입을 하고 오세요. SRM SRM은 Topcoder에서 개최하는 정기적인 프로그래밍 대회입니다. 보통 2주 www.acmicpc.net "SRM은 Topcoder에서 개최하는 정기적인 프로그래밍 대회입니다. 보통 2주에 한 번씩 열립니다. ... SRM이 끝나면, 자신의 등수에 따라서 복잡한 공식을 거쳐 Rating이 결정됩니다. Rating에 따라 아이디의 색상이 결정되는데 2200이상, 1500~2199, 1200~1499, 900~1199, 1~899와 같습니다." "SRM은 .. 2021. 5. 2. 알고리즘 문제 해결 전략 공부 시작!! 체계적으로 꾸준히 공부하기 위해서 이 책을 기준으로 공부를 시작합니다 !! book.algospot.com/ p7~p13 "이 책은 프로그래밍 대회문제를 풀며 각종 알고리즘 설계 기법과 자료 구조를 직관적으로 이해하고, 나아가 알고리즘 문제 해결 능력을 키울 수 있도록 구성했습니다. 이를 위해 각 기법이 생겨난 배경과 이유, 그리고 기법을 만들기 위해 필요한 과정을 자세히 다루었습니다." "그러나 문제 해결 능력을 훈련하기란 굉장히 어렵습니다. 문제 해결 능력은 추상적인 기술이기 때문입니다. 자기 계발을 하고 싶은 프로그래머들은 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없습니다. 단지 경험이 생기면서 나아질 것이라고 막연히 짐작할 뿐입니다. .. 2021. 5. 2. Check Sum __sum 16 check = 2402; 수신부에서 보내고, 송신부에서 2402를 더함 그럼 송신부에서는 2FFFD => FFFF가 되는 것임. 그럼 마지막에 ~ 을 하면 0000 0000 0000 0000 가 나오면 됨. (encode, decode 가 동일함) parity bit 와 다르게 비트가 변형이 되어도 검증이 가능함. 다만 하나의 비트가 ++, 하나가 -- 이면 전체의 합에는 변동이 없으므로 검증이 안됨 (한계점임) 2021. 4. 24. Parity bit - char data = 'a'; 8비트 중에 7비트는 데이터이고 첫 비트는 parity bit 임. 이렇게 설계되도록 해서 8비트가 만들어진 것이구나. 핵 신기하네. - 짝수개가 변형되면 검사를 할 수가 없음 #include unsigned int hweight(unsigned int w) { unsigned int res = w - ((w >> 1) & 0x55); res = (res & 0x33) + ((res >> 2) & 0x33); return (res + (res >> 4)) & 0x0F; } int main() { char data = 'a'; if (hweight(data) % 2) data |= 0x80; //data |= 0x2; //data |= 0x4; //-------------.. 2021. 4. 13. 이전 1 2 3 4 ··· 10 다음
