짧은코딩

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)에만 영향을 받고 거슬러 줘야하는 금액의 크기와는 무관하다.

시간 복잡도: 입력에 대해 알고리즘이 얼마나 오래 걸리는지, 필요한 연산의 횟수 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리르 차지하는지, 필요한 메모리의 양 효율적인 알고리즘을 사용하면 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 반복 연산을 생략하면서 계산 복잡도를 줄일 수 있다. -시간복잡도 만약 연산 횟수가 3N^3 + 5N^2 + 1,000,000이면 상수를 무시할 수 없다. 일반적 코딩 테스트에선 상수를 고려해야 하는 경우는 적지만 빅오 표기법이 항상 절대적인 것은 아니다. 일반적으로 코딩테스트에서 O(N^3)을 넘어가면 문제 풀이에 사용하기 어렵다. 그렇기에 알고리즘 문제 풀이 전에 조건을 먼저 확인하고 얼마나 효율적..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 내 풀이(질문 봄) import heapq def solution(scoville, K): answer = 0 scoville.sort() sum = 0 while scoville[0] < K: if len(scoville)