전체 글
-
⏭playDataAlgo 동적계획법파이썬/알고리즘 공부 2021. 9. 5. 22:41
⏭동적계획법(Dynamic Programming) 💢동적계획법이란?? 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정(규칙을 찾아가는 과정) ❗점화식 위 그림과 같이 수열에서 n번째 항을 이전에 나온 항들로 나타낸 공식 아래 예시로 여러가지 점화식 구현도 가능하다. ✅ex1) ✅ex2) ❗동적계획법 접근방법 동적계획법에는 작은 것부터 구현하여 결합식히는 형식의 Bottom up과 큰것들을 쪼개는 형식의 Top Down방식으로 구현한다. ❗동적계획법 활용 ✅Bottom up for i in range(2, n+1): fibList.aoppend(fibList[i-2] + fibList[i-1]) return fibList[-1]✅Top Down..
-
playdataAlgo재귀함수 🔄파이썬/알고리즘 공부 2021. 9. 5. 20:16
➰재귀함수 ➰ 💢재귀함수란?? 메소드 혹은 함수의 내부에서 자기자신의 메소드 혹은 함수를 다시 호출하는 함수! ex) ✅예시문제 data = [3, 5, 8]성분들의 합으로 표현할 수 있는 숫자의 경우의 수는?? ✅성분들의 합 중복값들이 존재하므로 2^3의값인 8과 값이 다르므로 완전탐색으로 구현해보자 ✅반복문을 활용한 완전탐색 data = [3, 5, 8] result = set() for i in range(2): for j in range(2): for k in range(2): result.add(data[0] * i + data[1] * j + data[2] * k) print(result) [0, 3, 5, 8, 11, 13, 16] 위에 함수에서 값이 3개이므로 for문으로 가능했지만 아래와..
-
210826_#1-Stack, Queue파이썬/알고리즘 공부 2021. 8. 25. 00:45
210826_#1-Stack, Queue 1. 스택(Stack)의 특징 삽입과 삭제가 같은 쪽에서 이루어지는 구조다. 나중에 입력된 데이터가 먼저 출력하는 메모리 사용법이다(Lifo - last in first out) 데이터가 저장될 때 입력된 데이터의 위치를 스택 포인터가 가리키고 있다. 데이터가 입력될 때 포인터는 1씩 증가하며, 스택 크기보다 큰 값을 갖게 되면 데이터를 더 이상 기억할 수 없다->Overflow stack 활용 1.함수를 호출하여 복귀할때 사용 2.깊이 우선 탐색(DFS)에서 사용 3.재귀적 함수를 호출할대 사용 4.인터럽트 수행 시 현재 수행중인 프로세스의 복귀 주소를 저장할때 사용 5.수식을 우선적으로 연산하기 위한 방법으로 사용 1. (4 + 5) * 2 - 3 2. (4 ..
-
playdataAlgo 비밀지도🌐, 전화번호 목록☎️파이썬/알고리즘 공부 2021. 8. 17. 22:25
playdataAlgo 비밀지도, 전화번호 목록 1.비밀지도🌐 1.지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 2.전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 3."지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 4.암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다. 입력형식 입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1,..
-
playdataAlgo DFS,BFS 예제파이썬/알고리즘 공부 2021. 8. 9. 22:41
DFS, BFS예제 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크..
-
playdataAlgo DFS, BFS파이썬/알고리즘 공부 2021. 8. 8. 17:04
DFS DFS - 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드르르 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드르 꺼낸다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 [step0]- 그래프 준비(1부터 시작, 가장 낮은 노드번호에 우선순위 부여) [step1]- 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 해준다. [step2]-스택의 최상단 노드인 '1'에 방문하지 않은 ..
-
playdata 프로그래머스 체육복파이썬/알고리즘 공부 2021. 8. 4. 23:50
playdata 프로그래머스 체육복 문제 접근방식 1. 모두 다 체육복을 가지고 있다는 가정하에 쉽게 접근 2. 잃어버린 번호와 여벌을 가지고 있는 변수 lost와 reserve를 인덱스로 가져와 해당값을 -1, +1 해줌으로써 쉽게 변환 --------- [1,1,1,1,1]에서 [2,4]를 받아와 -1해줌으로써 ->[1,0,1,0,1]형태로 처리, [1,3,5]를 받아와 +1을 해 [2,0,2,0,2] 형태로 만듬 3. 위에서 만든 리스트에 i가 0 보다 클 경우와, i가 n-1 보다 작을경우 나누어 처리 ex1) i 가 0보다 클경우 해당값이 0이고 앞에값이 2이면 앞에 값으로 부터 1을 받아온다(인덱스 0은 앞에값을 받을 수 없으므로 i가 n-1보다 작을경우에 처리) ex2) i 가 n-1보다 작..
-
playdata 프로그래머스,백준 기초알고리즘5파이썬/알고리즘 공부 2021. 8. 3. 22:45
playdata 프로그래머스,백준 기초알고리즘5 프로그래머스 소수 찾기 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다. import itertools def is_prime(num): #0과 1은 소수에 포함되지 않기때문에 False로 처리 if num < 2: return False elif num==2: return True #넘겨 받은 수를 2부터 넘겨받은 숫자전까지의 숫자로 나누어줄때 나머지가 없으면 소수가 아니므로 False, 나머지가 있으면 소수이므로 True for i in range(2, num): if num % i == 0: return Fa..