알고리즘(13)
-
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]만큼의 배열로 선언하여 계산했다.고정된 배열 길이로 구하려니.. 뒤에 자리들 처리해주는게 여간 성가신게 아니었다.그래서 벡터나 리스트 중에 뭐 써볼까 하다가 리스트로 ..
2015.02.24 -
책읽기003)프로그래밍 면접 이렇게 준비한다 - 2
1. 디버거를 쓰지 않고 체계적 분석, 중점적으로 살펴봐야 할 부분- 데이터가 함수에 제대로 들어오는지 확인한다.- 함수의 각 줄이 제대로 작동하는지 확인한다.- 함수에서 데이터가 올바르게 나오는지 확인한다.- 흔히 발생하는 오류 조건을 확인한다. 2. 연결 리스트의 마지막에서 m번째 원소 찾기문제단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어 보라.이때 시간 및 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현하라.여기에서 "맨 뒤에서 m번째 원소"는 m = 0일 때 리스트의 마지막 원소를 변환하는 식으로 생각한다. 순차적으로 찾는 방법가장 기본적인 알고리즘은 Head에서부터 Tail까지 리스트를 종주하고 전체 리스트를 체크한다...
2015.02.20 -
Project Euler Problem15
Lattice pathsProblem 15Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.How many such routes are there through a 20×20 grid? 나의 풀이)1. 최단경로 구하기좌상단의 값을 더하면 그 지점에 갈 수 있는 경로의 수가 나온다.검은색으로 패스를 적고 이를 배열에 넣는다.1행과 1열은 다 1로 초기화 하고 2행 2열부터 값을 계산한다. 2. 구현Xcode로 작성했다. 배열 중간에 오버플로우로 계산이 제대로 되지 않아 int64형을 이용..
2015.02.17 -
책읽기003)프로그래밍 면접 이렇게 준비한다 - 1
예전에 급하게 샀던 책인데 교양삼아 지하철 왔다갔다 하며 읽기로 했다.근데.. 역시 교양삼아 읽기는 좀 어려운 책.요새 자료구조 알고리즘 직접 짜보고 있어 도움이 되긴한다.링크드리스트 구현에 많은 도움이 되었다.뒤에 스택이랑 등등 많은 내용이 있는데 천천히 곱씹으며 읽어야겠다. 문제 해결 부분이 괜찮아 정리하면기본 단계1. 문제를 확실히 이해한다.2. 일단 문제를 이해하고 나면 간단한 예를 시도해 본다.* 문제를 풀기 시작하기 전에 우선 문제를 확실히 이해해야 하며, 몇 가지 예를 통해 제대로 이해하고 있는지 확인해보는 것부터 시작하도록 하자.3. 문제 풀이에 사용할 알고리즘과 자료구조에 초점을 맞춘다.4. 알고리즘과 구현 방법을 알아내고 나면 면접관에게 풀이를 설명한다.5. 코딩을 할 때도 뭘 하고 있..
2015.02.15 -
Project Euler Problem10
Problem10The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million. 나의 풀이)정말.. 수퍼 발코딩으로 풀었다.저번에 구현했던 isPrime 함수를 통해 소수를 찾고 2,000,000까지 반복문!isPrime에서 돌아가는 for문과 메인에서 돌아가는 for문을 합치니... 거의 O(n^2)급이니루프 200만번은 정말 가혹한 속도..15분만에 결과가 나왔는데.... 여튼 답은 구했다.. 외국 고수님들 풀이를 좀 읽어봐야겠다. 다른 사람의 풀이)continue ...
2015.02.15 -
Project Euler Problem6
Problem6.The sum of the squares of the first ten natural numbers is,12 + 22 + ... + 102 = 385The square of the sum of the first ten natural numbers is,(1 + 2 + ... + 10)2 = 552 = 3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.Find the difference between the sum of the squares of the first one hundred natural..
2015.02.05