알고리즘 썸네일형 리스트형 [잡다한코딩] 플로이드워셜 알고리즘 짜보기 http://hmjo.tistory.com/195 옛날 코드 보니깐 추억이 새록새록. 블로그에 코드가 잘못 되었다고 댓글이 달려서 오랜만에 복습을 했다.일단 그림이 잘못 되어 있던 것을 좀 고치고.코드는 문제가 없는데..ㅋㅋㅋㅋ 코드 짜 놓은게 ..거의 한 천만년전 C98 코드 같아서 다시 짜봤다.예전에 경로 추적도 이해 안되서 빼먹고 막 짰던거 같은데 ㅋㅋㅋ VS2015 기준 C++11 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929.. 더보기 [effective STL] 항목 34 : 정렬된 범위 동작 알고리즘들 기본적으로 정렬된 데이터를 넘겨 동작하는 알고리즘들이 있다는 이야기. binary_search, lower_bound, upper_bound, equal_range: 반드시 정렬된 데이터. 내부적으로 이진 탐색을 사용해 값을 찾는다. set_union, set_intersection, set_difference, set_symmetric_difference: 기본적으로 선형시간으로 동작하지만 정렬하지 않은 데이터는 터무니 없이 느리다. merge, inplace_merge: 두 정렬된 범위를 받아 합치는 알고리즘으로 하나라도 정렬되지 않으면 동작하지 않는다. includes: 어떤 범위 안에 값이 있는지 여부를 알아보는 알고리즘. 정렬되어 있음을 가정하고 동작한다.기본적으로 선형시간이지만 정렬되어 있지 .. 더보기 [effective STL] 항목 31 : 정렬시 선택 사항들을 제대로 파악 정리- vector, string, deque, c++ array에 대해 전체 정렬을 수행할 필요가 있을 때는 sort나 stable_sort를 사용한다.- 상위 n개의 요소만 순서에 맞추려면 partial_sort를 사용한다.- 상위 n개의 요소를 뽑되 순서를 고려할 필요가 없다면 nth_element가 적합하다.- 표준 시퀀스 컨테이너가 있고, 이 컨테이너의 요소들을 어떤 기준에 만족하는 것들과그렇지 않은 것들을 모아 구분하고 싶다면 partition이나 stable_partition을 고려해본다.- 사용하고 있는 데이터가 list인 경우엔 partition과 stable_partiton은 직접 사용할 수 있으며sort와 stable_sort 알고리즘 대신에 list:sort 멤버 함수를 사용할 수 .. 더보기 [effective STL] 항목 30 : 알고리즘의 데이터 기록 범위는 충분히 크게 잡자. 핵심알고리즘을 쓰기 전에 내부 동작 구조를 알고 컨테이너를 결정해주고,재할당이 최대한 일어나지 않게 범위를 잘 잡아야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include #include #include #include using namespace std; int transmogrify(int x) { return x*x; } template void printVector(T SomeContainer, string str) { cout 더보기 Project Euler Problem8 Largest product in a seriesProblem 8The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 6.. 더보기 책읽기003)프로그래밍 면접 이렇게 준비한다 - 3 1. 순환형 연결리스트 여부알아보기순환형인지 아닌지 판단하는 알고리즘을 찾는것.일단 먼저 떠오르는 방법은 노드에 한번 지나간 자리인지 확인하는변수를 선언하고 변수를 체크해 순환형을 가려낼 수 있다.하지만 이렇게 푸는건 적절한 문제 풀이가 아니다! 적어도 면접관에겐!- 노드에 변수를 넣는것은 노드를 수정한다는 의미. 최대한 노드 수정 없이! 2. 해결방법토끼와 거북이 알고리즘! Tortoise and Hare 알고리즘이다.2개의 포인터의 증감률을 다르게 하여 탐색한다.이 알고리즘의 장점은 특히 비순환일때 탐색 속도가 n/2로 줄어든다.빠르게 뛰는 토끼포인터가 거북이 포인터와 같아지거나 앞지르게 되면 이것은 순환형!빠르게 뛰는 토끼포인터가 널 포인터를 만난다면 이것은 비순환형이 되는것이다. 위키에서 퍼온 것.. 더보기 Project Euler Problem16 Power digit sumProblem 16215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.What is the sum of the digits of the number 21000? 나의 풀이)2의 1000승을 표현하기는 매우 어렵다.기본적으로 몇 백자리의 수가 나오기때문에.. 표현할 수 있는 자료형이 없다.게임 아카데미 동기가 라지넘버 라이브러리를 쓰면 된다는데..찾아보니 gmp인거 같은데.. 설치가 귀찮아 이 방법은 접는것으로... 처음 배열로 구현하려고 str[500]만큼의 배열로 선언하여 계산했다.고정된 배열 길이로 구하려니.. 뒤에 자리들 처리해주는게 여간 성가신게 아니었다.그래서 벡터나 리스트 중에 뭐 써볼까 하다가 리스트로 .. 더보기 책읽기003)프로그래밍 면접 이렇게 준비한다 - 2 1. 디버거를 쓰지 않고 체계적 분석, 중점적으로 살펴봐야 할 부분- 데이터가 함수에 제대로 들어오는지 확인한다.- 함수의 각 줄이 제대로 작동하는지 확인한다.- 함수에서 데이터가 올바르게 나오는지 확인한다.- 흔히 발생하는 오류 조건을 확인한다. 2. 연결 리스트의 마지막에서 m번째 원소 찾기문제단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어 보라.이때 시간 및 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현하라.여기에서 "맨 뒤에서 m번째 원소"는 m = 0일 때 리스트의 마지막 원소를 변환하는 식으로 생각한다. 순차적으로 찾는 방법가장 기본적인 알고리즘은 Head에서부터 Tail까지 리스트를 종주하고 전체 리스트를 체크한다... 더보기 이전 1 2 다음
