짧은코딩

n, m = map(int, input().split()) ary = [] for i in range(n): x = list(map(int, input())) ary.append(x) def dfs(x, y): #범위 체크 if x = n or y = m: return False #방문했는지 체크 if ary[x][y] == 1: return False #상하좌우 탐색 ary[x][y] = 1 dfs(x-1, y) dfs(x, y-1) dfs(x+1, y) dfs(x, y+1) return True count = 0 for i in range(n): for j in range(m): if dfs(i, j): count += 1 print(count) ​(0, 0)부터 DFS 탐색으로 좌우앞뒤를 재귀적으로..

DFS DFS: 깊이 우선 탐색이라고도 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 -인접 행렬 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될 수없는 999999999, 987654321 등의 값으로 초기화하는 경우가 많다. INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) -인접 리스트 방식 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. # 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연..

DFS와 BFS를 구현하려면 재귀 함수도 이해해야 한다. -재귀 함수의 종료 조건 재귀 함수를 사용할 때는 재귀 함수가 언제 끝날지 종료 조건을 꼭 명시해야 한다. 컴퓨터 내부에서 재귀 함수의 수행은 스택을 사용한다. 함수를 계속 호출했을 때 마지막에 호풀한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 연속해서 호풀되는 함수는 메인 메모리의 스택에 적재된다. 그래서 재귀 함수는 스택과 같다는 말이 틀린 말이 아니다. # 반복적으로 구현한 n! def factorial_iterative(n): result = 1 # 1부터 n까지의 수를 차례대로 곱하기 for i in range(1, n + 1): result *= i return result # 재귀적으로 구현한 n! def fa..

문제 풀이(이해가 안되서 보고 풀음) # N, M을 공백을 기준으로 구분하여 입력받기 n, m = map(int, input().split()) # 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화 d = [[0] * m for _ in range(n)] # 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기 x, y, direction = map(int, input().split()) d[x][y] = 1 # 현재 좌표 방문 처리 # 전체 맵 정보를 입력받기 array = [] for i in range(n): array.append(list(map(int, input().split()))) # 북, 동, 남, 서 방향 정의 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] #..

내 풀이(처음에 틀렸는데 해설 보고 수정) x = input() row = int(x[1]) column = int(ord(x[0])) - int(ord('a')) + 1 count = 0 ary = [(2, 1), (2, -1), (-2, 10), (-2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2)] for i in ary: r = row + i[0] c = column + i[1] if r >= 1 and r = 1 and c

풀이법 이 문제는 모든 시각의 경우를 하나씩 세서 풀 수 있는 문제이다. 왜냐면 하루는 24 * 60 * 60이라 86,400초이다. 즉 경우의 수가 100,000개가 되지 않아 하나씩 세도 시간 제한 2초 안에 문제를 풀 수 있다. 이런 유형은 가능한 경우의 수를 모두 검색하는 방법인 완전 탐색(Brute Forcing) 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 주로 전체 데이터 수가 100만 개 이하일 때 사용하면 적절하다. 교재 및 내 풀이 # H를 입력받기 h = int(input()) count = 0 for i in range(h + 1): for j in range(60): for k in range(60): # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가 if '3' in s..

내 풀이 N = int(input()) dis = list(input().split()) cur = [1,1] for i in dis: if i == "L": cur[1] -= 1 if cur[1] N: cur[1] -= 1 elif i == "U": cur[0] -= 1 if cur[0] N: cur[0] -= 1 print('%d %d'%(cur[0], cur[1])) 현재 위치를 cur 리스트로 만들어서 문제를 풀었다. 각 움직임마다 먼저 수행을 하고 만약 범위가 벗어나면 다시 원상복구 시키는 방법으로 구현했다. 교재..

구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. problem-thinking-solution 과정을 거쳐야 한다. -완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 -시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 -int 자료형 데이터의 개수에 따른 메모리 사용량 리스트 중에 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없을 수 있다. 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만번의 연상을 수행한다고 가정하면 크게 무리가 없다. 만약 시간 제한이 1초이고 데이터의 개수가 100만 개인 문제가 있으면 시간 복잡도는 O(NlogN) 이내로 풀어야한다. 실제로 N = 1,00..

이 문제를 for문과 while문을 사용해서 풀면 시간 초과가 발생할 수 있다. 그렇기에 반복되는 수열에 대해 먼저 파악을 해야 한다. # N, M, K를 공백을 기준으로 구분하여 입력 받기 n, m, k = map(int, input().split()) # N개의 수를 공백을 기준으로 구분하여 입력 받기 data = list(map(int, input().split())) data.sort() # 입력 받은 수들 정렬하기 first = data[n - 1] # 가장 큰 수 second = data[n - 2] # 두 번째로 큰 수 # 가장 큰 수가 더해지는 횟수 계산 count = int(m / (k + 1)) * k count += m % (k + 1) result = 0 result += (coun..

이 문제는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다. for coin in coin_types:#coin_types는 잔돈 동전의 모음 count += n#count는 받는 동전 수, n은 입력값 n %= coin 이렇게 하면 코드의 시간 복잡도는 O(K)이다. 이 알고리즘은 동전의 종류(coin_types)에만 영향을 받고 거슬러 줘야하는 금액의 크기와는 무관하다.