분류 전체보기
백준 11729 풀이 (하노이탑)
오우 아주 쒯같지만 좋다고 느낀 문제였다. 계속 재귀에 대해서 벽을 느끼고 있었는데 재귀의 동작방식을 너무나 잘 공부할 수 있었다. 하노이탑 알고리즘을 보다 보니 너무 좋은 글을 써주신 블로거분이 있어서 참고하면 좋을거 같다. (shoark7.github.io/programming/algorithm/tower-of-hanoi) 규칙은 쉬우나 문제는 법칙을 찾는게 어렵다는 것이다. 그래서 3을 기준으로 어떻게 옮기는지 보면 몇가지 방식으로 규칙을 찾을수 있다. 완벽히 이해한게 아니라 설명이 어려운데..... 1. 3을 A->C로 옮기는 경우 2. 1,2를 A->B로 옮겨야한다.(2를 A->B로 옮기는 재귀함수) 3. 3을 A->C로 옮겨야한다.(1개만 옮겨도 되기 때문에 재귀가 필요없다.) 4. 1,2를 ..
백준 2447 풀이 (재귀함수, 별찍기 - 10)
진짜 나한테 너무너무너무 어려웠다. 거의 포기하고 넘어갈까 고민하다가 유튜브로 재귀함수도 찾아보고, 알고리즘에 이끌려 포인터가 어려운가요 재귀함수가 어려운가요 동영상까지 보게됐다. 역시 문과생에게 알고리즘은 벽인건가 싶다가 그냥 코드를 외워버리기로 했고 코드를 외우다보니 어떤 방식으로 알고리즘이 진행되는지 이해가 됐다. 그래서 고수들의 코드를 토대로 내 코드를 다시 작성했다. def recur(num): global Map if num == 3 : Map[0][:3] = Map[2][:3] = [1]*3 Map[1][:3] = [1,0,1] return a = num//3 recur(num//3) for i in range(3):# 행 for j in range(3): #열 if i==1 and j==1..
백준 10870 풀이 (재귀함수, 피보나치)
재귀함수는 아직 어렵다. 어떤 구조를 짜야하는지 계속 고민하게 된다. 그래도 얼추 대강 짜서 통과는 할 수 있었다. 솔직히 대강 짠거라 안좋은 코드인줄 알았으나 속도가 빠르다는 장점이 있었다. n = int(input()) def pibo(a,b,num): c = a+b if num == 0: return 0 elif num
백준 10872 풀이 (재귀함수, 팩토리얼)
예전에 c언어를 공부할때 재귀함수를 간단히 다뤄본적이 있다. 솔직히 구조가 한눈에 들어오지 않아서 꽤 맘에 안들었고 그 이후로는 자발적으로 재귀함수를 써본적이 없다. 그래도 이번에 재귀함수를 써야하는 문제가 나와서 오랜만에 재귀함수를 쓰게 되었다. 재귀라는 것은 어떤 사건에 대해서 나를 포함하나 나를 사용하여 정의되는 것을 의미한다. 함수로 생각한다면 함수를 정의할때 선언하는 함수가 포함되어있는것을 재귀함수라고 한다. 아래의 함수를 보면 packtorial함수정의 안에 return값으로 packtorial이 다시 포함되는 것을 확인할 수 있다. 만약 if 조건이 없다면 이 함수는 계속해서 무한루프에 빠질 것이다. 그러나 조건을 선언해주었기 때문에 함수가 종료될 수 있는 것이다. n = int(input(..
#3 알고리즘 공부 2/8 리뷰
2/6 19문제 2/7 11문제 2/8 9문제 총 39문제 확실히 난이도가 슬금슬금 올라가니 풀수 있는 하루치가 줄어들고 있다. 물론 평일에 푸는 경우에는 할애하는 시간이 줄어들기도 했다. 그래도 다행히 3일동안 39문제를 풀었으니 100문제까지 61문제 밖에 남지 않았다. 이정도 페이스라면 문제가 조금씩 어려워 지더라도 2주 안에는 다 풀수 있지 않을까 싶다. 사무실 일도 있고 면접 중이라 완전히 할애하지 못하는게 아쉽긴 하지만 코딩테스트는 장기전이니까 맘편히 꾸준히 노력해야겠다.
백준 9020 풀이 (골드바흐의 추측 )
이번에는 "골드바흐의 추측"이라고 한다. 솔직히 난 문과출신이라 이런거 정의 보면 살짝 불편하다ㅋㅋㅋㅋ 그래도 정의가 어렵지는 않다. 큰 짝수는 반드시 두 소수로 나타낼 수 있다는 소리다. 그래서 N값에 대해서 두 소수를 구하면된다. 단, 두 소수의 차이가 가장 작아야한다. 그래서 시나리오를 짜봤다. 1. 소수리스트를 먼저 구한다.("에라토스테네스의 체"를 활용한다. 저번 포스팅에 이런방식으로 푸는 고수들이 있길래 따라했다.) 2. 짝수는 나누었을때 소수를 바로 가질수도 있고 하나씩 줄여가며 구해야할수도 있다. 3. 빼고자 하는 수가 소수인지, 뺀후에도 소수인지 판별한다. 4. 둘다 소수이면 출력 여기서 포인트는 빼고자 하는 수를 N/2부터 비교해서 빼기 시작한다는 것이다. line 13 def isPr..
백준 1929 풀이 (에라토스테네스의 체)
음 처음에 알고리즘 이름이 너무 길어서 쫄았다. 그래서 검색을 통해 알아보니 소수를 구하기 위한 방식이었다. 1. N 을 나눌경우 몇까지 나눌수 있는지 구한다. => Max_division = N ** 0.5 2. N을 2~Max_division까지 나누면서 떨어지는지 판별한다. 3. 만약 N과 값이 같거나 나누어 떨어지지 않으면 소수로 판별한다. 문제는 어떻게 풀어도 시간초과로 뜬다. 그래서 다른 사람들 풀이를 보니 함수로 만들어서 식을 더 최소화 시키는 방법을 적용하는 것을 알게되었다. a,b = map(int,input().split()) for val in range(a,b+1): flag = 1 for i in range(2,int(val ** 0.5)+1): if val == 1: flag =..