피보나치
-
BOJ) 01타일알고리즘/백준 2020. 6. 25. 17:04
01타일 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 풀이 처음 문제를 봤을 때는 순서를 모두 구해주어야 한다고 생각했다. 그래서 처음 로직은 for문을 돌리면서 0타일이 n이하까지 2개씩 증가시키면서, 1타일은 n-0타일의 수 를 통해 각각 타일의 수를 구해주었다. 그리고 0타일은 2개를 1개로 인식해야하기 때문에, /2를 해주었다. 0타일의 갯수 : ZERO 1타일의 갯수 : ONE total = ZERO + ONE 위의 변수를 가지고 따지면, total! / ZERO! / ONE! ( ! = 팩토리얼)..
-
프로그래머스 Lv.3) 멀리 뛰기알고리즘/프로그래머스 2020. 5. 29. 18:11
멀리 뛰기 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2�� programmers.co.kr 풀이 dp 문제이고, 피보나치 문제임을 바로 눈치챘다. 바로 1차원 배열을 만들어서 제출했는데, 1번 문제가 틀렸다고 나왔다. 피보나치 문제가 아닌가? 생각에 다시 문제를 꼼꼼히 봤으나 피보나치가 맞았다. 문제점을 모르겠어서 질문하기 탭을 확인했는데, n만큼 배열을 만들면 메모리 초과가 뜬다는 것이었다... 충격.. 최대 n이 고작 2000인데 메모리 초과가 난다.. 아무튼 그래서 변수 두개..
-
프로그래머스 Lv.2) 피보나치 수알고리즘/프로그래머스 2020. 5. 21. 16:36
피보나치 수 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 풀이 피보나치를 배열을 통해 푸는 방법과, 1234567로 나눈 나머지 값을 저장 및 return한다는 것 이외는 특별하게 신경써야하는 부분이 없다. 혹시 피보나치를 구현하는데 어려움을 겪는 분이 있다면, 피보나치를 배열로 풀기 전에 재귀를 통해 푸는 방법을 먼저 익히는 것을 ..
-
프로그래머스 Lv.3) 2xn 타일링알고리즘/프로그래머스 2020. 5. 14. 23:28
2 x n 타일링 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 1 이 문제도 풀었었는데..?? 하는 생각이 들었다. 나중에 알고보니 백준에 타일링 시리즈가 많다는 것을 들었다. dfs의 로직을 dp로 옮기는 문제 중 가장 기본인 문제라고 생각한다. 이 문제는 피보나치 수열을 이용하는 문제로 무리없이 풀 수 있었다. 2020.06.03) 코드 2 얼마 전, 멀리뛰기 문제를 풀면서, 피보나치를 배열이 아닌 세 변수를 이용해 푼 기억이 났다. 그래서 이 문제에서도 배열이 아닌, 변수 세 개를 이용해 풀면서 완벽히 숙지했나 확인하려고 다시 풀었다. ..