yeony's story

(처음 든 생각) 일단 맵을 만들자. 그리고 나서 생각을 다시 해보자, 빗물이 차오르게 하려면? 양 옆에 빗물을 가둘 수 있는 기둥이 존재해야 한다. 위 그림에서는 양 옆에 빗물을 가둘 수 있게끔 기둥이 존재하고, 왼쪽 기둥은 높이가 3, 오른쪽 기둥높이는 4이다. 이때는 왼쪽 기둥의 높이에 맞춰야한다. (즉 최솟값) 그래서 이때 든 생각은 바닥부터 탐색을 시작해서 체크를 하자..? 여기서도 마찬가지로 왼쪽 빗물부터 보면, 왼쪽 기둥 높이는 3, 오른쪽 기둥 높이는 4 이때도 3을 선택 오른쪽 빗물은 왼쪾 기둥이 4, 오른쪽 기둥 높이가 2 따라서 2를 선택 위 그림에서는 빗물이 고일 수가 없다. 기둥이 1개만 존재하기 때문이다. (내가 맨 처음에 성공했던 풀이) 맨 아래부터 탐색을 시작한다. h, w ..

[처음 든 생각] 최소를 구하라고 해서 bfs가 제일 먼저 떠올랐다. 근데 bfs 구현을 매끄럽게 잘 해내지 못하는 상태라 사전공부를 하고 왔다. 사다리와 뱀이 이 문제에서는 키포인트! 너비 우선 탐색은 현재 노드에서 갈 수 있는 모든 노드를 먼저 탐색하는 과정이기 때문에, 최단 거리 구할 때 주로 사용한다. https://eboong.tistory.com/253 [이것이 코딩테스트다 Ch5 ] DFS와 BFS 1. 스택과 큐 (1) 스택 - 후입선출 - 삽입은 append(n) , 삭제는 pop() (2) 큐 - 선입선출 - 파이썬에선 큐 구현을 위해 deque 라이브러리를 사용한다. - 삽입 append(n), 삭제 popleft() - queue 라이브러리 대신.. eboong.tistory.com..

[처음 한 생각] s를 t로 바꾸기 위해 2가지 연산만 사용할 수 있다. 그러면 역으로 생각해서 t를 s로 바꿀 수 있으면 그게 답이 아닐까 생각했다. s : A t : BABA이면, BABA에서 맨 오른쪽에 있는 A는 빼내고, B는 거꾸로 한 뒤 B를 빼내고, BA에서 A를 빼내고, B가 남는다..? 근데 예제는 분명 s에서 t로 바꿀 수 있다고 했는데.. 이게 아닌가보다.. 아니다.. 마지막 부분이 잘못된 오류가 있었다! BA에서 1번 연산이 아닌 2번 연산을 취하면 된다. 그럼 A가 남게 되니까 최종값은 1이 된다..! [풀이] T->S 과정을 거치면 답을 구할 수 있다. S->T로 만들면서 나타날 수 있는 경우의 수는 총 4가지 1번 연산 : 맨 끝에 A 추가 2번 연산 : 맨 끝에 B추가 후 문..

https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 매번 점화식을 재귀함수로 구하면 시간이 매우 오래걸려서 메모이제이션 방식을 사용하여 푼다. 처음엔, for문을 한 번만 돌리면 되는 줄 알았다. n=3일경우 f(3)= f(0)*f(2) + f(1)*f(1) + f(2)*f(0)이니까 3번만 돌리면 되..

https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 구현 문제 처음엔 2차원 배열에 시작점과 끝점을 다 넣어줘야하나 고민했다. 하지만 그렇게 되면, 연속지점은 어찌저찌 구하더라도 중간에 끊어지는 부분이나, 코팅지 면적의 높이를 구할 수 없게 된다. 이 문제는 일단 365개의 숫자가 들어갈 배열을 구해야한다. 1일부터~ 365일까지니까, 크기가 366인 배열을 만들어서 0번째 배열은 버리고, 1번째 배열부터 사용할 예정이다. calendar 배열에는 row(높이..

* 정렬 알고리즘 * 1. 선택정렬 2. 삽입정렬 3. 병합정렬 4. 퀵정렬 1. 선택정렬 가장 작은 값을 골라 정렬 앞쪽에 두는 것을 반복하는 정렬이다. 입력값=[5,10,66,77,54,32,11,15] 정렬된리스트=[] while 입력값: 정렬된리스트.append(min(입력값)) 입력값.pop(입력값.index(min(입력값))) print(정렬된리스트) #최솟값 구하는 함수 만들기 def 최솟값(array): 최소=array[0] cnt=0 for i in array: if 최소>i: 최소=i index=cnt cnt+=1 print(최소) print=("최솟값의 idx",index) 2. 삽입정렬 앞에서부터 차례대로 넣는데, 넣을 때 이 값보다 크게 되면 뒤에 놓고 이 값보다 작게 되면 앞에 ..

# 피보나치 수열 a=0 b=1 def fibo(num): if num==1 or num==0: return 1 else: return fibo(num-1)+fibo(num-2) print(fibo(5)) fibo(5) = fibo(4) = fibo(3) = 5 + 3 = 8 fibo(4) = fibo(3) + fibo(2) = 3 + 2 = 5 fibo(3) = fibo(2) + fibo(1) = 2 + 1 = 3 fibo(2) = fibo(1) + fibo(0) = 2 # 팩토리얼 def factorial(num): if num==1: return 1 else: return num*factorial(num-1) print(factorial(5)) # for문 이용 더하기 -> 재귀함수로 구현 s=0 ..

문제 접근 방법 1. 반복문의 경우 > Bottom - up (작은 문제에서 출발) 2. 재귀함수의 경우 > Top-down (큰 문제에서 출발) recursion = 재귀함수 재귀함수에서는 종료조건이 꼭 있어야한다.! # 2진수 구하기 (방법1 : 내장함수 사용) print(bin(11)[2:]) #2진수, 0b 지우기 print(oct(11)) #8진수 print(hex(11)) #16진수 (방법2 : while문 사용) result='' input_num=10 while True: if input_num%2==0: result+='0' else: result+='1' x=x//2 if x==1 or x==0: print(result[::-1]) break (방법3 : 재귀함수 사용) result =..

* 재귀함수를 이용한 1부터 100까지의 합과 곱 구하기 * 1. 재귀함수 사용 x, for문 사용 # 재귀함수 사용 x def f(N): x=0 n=100 plus_sum=0 multi_sum=0 for i in range(n+1): plus_sum+=i for i in range(n+1): multi_sum*=i f(100) 2. 재귀함수 사용 o def plus_f(n): if n

1. matrix 형태의 동적 계획법 - Recursion -memorization 이동 방법 1. 맨 왼쪽에서 시작할 경우 이동할 수 있는 방향 : 오른쪽, 아래 3으로 이동하는 최단 거리를 구하는 방식 > min(최소경로(i-1,j), 최소경로(i,j-1)+값(i,j) 일반적으로는 왼쪽에서 출발해서 오른쪽으로 순회를 한다. 하지만 문제에서는 다르다. 오른쪽에서 출발해서 왼쪽으로 순회한다. cross=[ [[3, 0, 1, 1, 8], [5, 0, 4, 5, 4], [1, 5, 0, 5, 1], [1, 2, 1, 0, 1], [0, 2, 5, 1, 1]], [[1, 2, 0, 3, 3], [1, 2, 0, 2, 4], [1, 2, 0, 2, 4], [4, 2, 0, 0, 1], [8, 4, 1, 1, ..