성장하는사람

[문제] - BFS 알고리즘의 기본을 구성해본다 [아이디어] - DFS 는 재귀함수 형태로 만들어진다. 스택 자료구조로 만들어진다. - BFS 는 큐 자료구조로 만들어진다. - DFS 와 BFS모두 시간복잡도는 O(N) 으로 동일하지만, 일반적으로 실제 수행시간은 BFS가 빠르다고 본다. (재귀함수의 이용으로 인한 컴퓨터의 동작시간으로만 언급되고 있으며, 너무 깊어지는 내용이므로 일반적인 수행시간으로만 알고있도록 하자) # deque 라이브러리를 이용 from collections import deque def bfs(graph, start, visited): # 큐의 구현을 위해 deque 라이브러리를 이용한다. queue = deque([start]) # 현재노드 방문처리 visited[start] ..

[문제] - 8X8 나이트 판이 존재한다. - 행은 12345678, 열은 abcdefgh 로 표현한다. - 나이트는 수평2-수직1 or 수직2-수평1 로만 이동이 가능하다. - 나이트의 좌표가 주어졌을때 (ex a,1) 나이트가 이동할 수 잇는 경우의수를 구하는 프로그램을 구현한다. - 나이트는 정원의 밖으로 나갈 수 없다. [코드] # 나이트가 움직일 수 있는 경우의수 8가지를 구해본다. steps = [ (-2,-1), (-1,-2), (1,-2), (2,-1),(2,1), (1,2), (-1,2), (-2,1) ] row,col=1,1 result = 0 for i in steps: next_row = row+i[0] next_col = col+i[1] # 맵 안에 들어있는경우 result 를 1..

[문제] - N이 입력되면, 00시00분00초부터 N시00분00초까지 모든 시각중에서 3이 하나라도 포함되는 모든 경우의수를 구하는 프로그램을 구성한다. - N 으로 5 가 입력되면, 00시00분00초부터 05시00분00초까지 3이 하나라도 포함되는 모든 경우의수를 구하는 프로그램이다. [코드] n=5 result = 0 for i in range(n+1): for j in range(60): for k in range(60): if '3' in str(i)+str(j)+str(k): result += 1 print(result) [아이디어] - XX시 YY분 ZZ초 를 문자열로 봐버린다. - 결국 000000, 000001 ..... 000058, 000059, 000100, 000101, ..... ..

[문제] - N을 입력받는다. N은 N x N 의 맵을 만든다. - L, R, U, D 를 입력받는다. LEFT / RIGHT / UP / DOWN 을 의미한다. - 입력받은 LRUD 만큼 (1, 1) 위치에서 이동했을때 어느 좌표에 위치하는지 구현하는 프로그램을 작성한다. - N x N 을 벗어나는 LRUD 는 무시된다. [코드] N=5 x,y,nx,ny = 1,1,0,0 plan = ['R', 'R', 'R', 'U', 'D', 'D'] # 이동을 위한 LRUD 정의 # L 은 (2,2) > (2,1), dx+0 dy-1 # R 은 (2,2) > (2,3), dx+0 dy+1 # U 는 (2,2) > (1,2), dx-1 dy+0 # D 는 (2,2) > (3,2), dx+1 dy+0 move = [..

[문제] - 숫자 N, K 가 주어진다. - N에 대하여 다음 두가지 연산을 할 수 있다. a. N-1 b. N/K (떨어질때만 가능) - a,b 연산을 이용하여 N을 1로 만들수있는 최소횟수를 만들어본다. - N=17, K=4 라면, a, b, b 연산으로 1을 만들 수 있다. [아이디어] - 1을 만들기위해서는 a 보다 b 가 유리하다. - 큰수에서는 당연하다. 작은수에서 검증을 해보면, N=2 일때 a 와 b 의 효력이 같아진다. - 결국 나눌수있다면 나누고, 나눌수 없다면 빼는 식으로 간다. [실패코드] n = 10000 k = 4 result = 0 # n 이 1보다 크다면 연산을 계속한다. while( n > 1 ): # n 이 k 로 나누어떨어지지않는다면, n에서 1을 빼준다. while (..

[문제] - m x n 의 2차행렬의 숫자카드가 주어진다. - 각 행마다 가장 작은숫자를 뽑는다 - 뽑은 작은숫자중에서 가장 큰 숫자를 뽑는다. 3 1 2 4 1 4 2 2 2 숫자카드에서는 1 / 1 / 2 중에 2가 뽑히게된다. [코드] n=3 m=3 map = [ [3, 1, 2], [4, 1, 4], [2, 2, 2] ] result = 0 for i in range(m): min_value = min(map[i]) result = max(result, min_value) print(result) [해설] - 단순하게 배열을 하나씩 탐색하면서 풀어간다. - min() 함수는 인자에있는 값중 가장 작은값을 리턴한다. - 배열의 1열, 2열, 3열 ... 을 하나씩 탐색하면서 최소값 min_value..

[문제] - 배열의 갯수는 N 이다. - 주어진 배열에서 M 번을 더하여 가장 큰 수를 만들어야 한다. - 특정 인덱스의 숫자는 연속으로 K 번을 초과할 수 없다. - [ 2, 4, 5, 4, 6] 배열이 있고, M=8, K=3 이라면, 6+6+6+5+6+6+6+5 = 46 이다. - 단, 인덱스가 다른데 같은숫자가 있다면, 이건 다른것으로 간주한다. - [ 3, 4, 3, 4, 3] 배열이 있고, M=7, K=2 라면 4+4+4+4+4+4+4 = 28 이다. [아이디어] - 배열에서 첫번째로 큰수를 찾고, 이걸 최대횟수 (K) 만큼 더해준다. - 배열에서 두번째로 큰수를 찾고, 이걸 최소횟수 (1) 만큼 더해준다. - 그다음 첫번째로 큰수를 다시 (K) 만큼 더해준다. n = 5 m = 8 k = 3 ..

예제 3-1. 거스름돈 문제 - 거스름돈은 500원, 100원, 50원, 10원 동전이 무제한 존재한다. - 손님에게 거슬러줄 돈은 N원이다. - 거슬러 줘야할 동전의 최소 개수는 ? import time start_time = time.time() ## n = 1260 count = 0 coin_types = [500, 100, 50, 10] for coin in coin_types: count = count + ( n // coin ) # count n = n % coin print(count) ## end_time = time.time() print ("TIME : ", end_time - start_time) - 거슬러 주어야할 돈은 1260원이다. - 500원으로 나누게되면 ( 1260 / co..