1. DFS (Depth-First-Search) 스택 자료 구조 이용하거나 재귀 함수를 이용. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 ㅇ낳은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복. #DFS 메소드 정의 def dfs(graph, v, visited): visited[v] = True print(v, end = '') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) #각 노드가 연결된..

Greedy 알고리즘 ? 1. 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 2. 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 3. 정당성 분석이 중요. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토. 문제 . 1이 될때까지 n , k = map(int, input().split()) # N = 25, K = 3 res = 0 while True: #시간 복잡도 : O(log(n)) target = (n // k) * k res += (n - target) n = target if n < k : # 더이상 나눌 수 없으면 종료 break res += 1 # 횟수 count n //= k # 마지막으로 남은 수에 대해 1씩 빼기 res += (n..

DP(동적계획법)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 일반적으로, 구현 방식은 탑다운(Top-down)과 보텀업(Bottom-up) 방식으로 구성된다. 1. DP 를 사용할 수 있는 조건 1) 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2) 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 함. 2. DP 종류 1) 탑다운 방식 : 메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하..

2020 KAKAO BLIND RECRUITMENT > 문자열 압축 문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어..

연결 리스트는 가장 대표적인 선형 알고리즘. 효율적으로 풀기 위해서 첫번째 방법은 deque를 이용하여 최적화 시킬 수 있다. 동적 배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다. 왜냐하면 첫번째 값을 꺼내오면 모든 값이 한 칸씩 shifting되며, 시간 복잡도도 O(n) 가 발생한다. 파이썬의 deque는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에서 실행된다. 두번째 방법은 런너를 이용하는 것이다. 순서에 따라 2개의 런너, 빠른 런너와 느린 런너를 각각 출발 시키면, 빠른 런너가 끝에 다다를 때 느린 런너는 중간 지점에 도달하게 된다. 그럼 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나간다. 이제 중간에 도달한 ..

문제. 두수의 합 [2, 7, 11, 15] 가 input으로 들어갔을 때 sum = 9가 되는 두 숫자의 인덱스를 리턴하여라. 풀이 1. 브루트 포스로 계산 모든 경우의 수를 다 확인하는 방법. 매우 비효율적. for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + num[j] == target: return [i,j] 풀이 2. in을 이용한 탐색 모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색. for i, n in enumerate(nums): complement = target - n if complement in nums[i+1]: return [nums.index..

SW Expert Academy [S/W 문제해결 기본] 시리즈 1215. 회문1 [문제] "기러기" 또는 "level" 과 같이 거꾸로 읽어도 앞에서부터 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다. 주어진 8x8 평면 글자판에서 가로, 세로를 모두 보아 제시된 길이를 가진 회문의 총 개수를 구하는 문제이다. [입력] 각 테스트 케이스의 첫 번째 줄에는 찾아야 하는 회문의 길이가 주어지며, 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다. [출력] #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 개수를 출력한다. [Code] def solve(): length = int(input()) #4 arr = [input() ..

SW Expert Academy [S/W 문제해결 기본] 시리즈 1213. String 문제 주어지는 영어 문장에서 특정한 문자열의 개수를 반환하는 프로그램을 작성하여라. e.g. Starteatingwellwiththeseeighttipsforhealthyeating,whichcoverthebasicsofahealthydietandgoodnutrition. 위 문장에서 ti 를 검색하면, 답은 4이다. 코드 #1213. string def solve(text_input, text): num = text.count(text_input) #count 함수 return num for t in range(1,11): #10개 테스트 case = int(input()) text_input = str(input(..

SW Expert Academy [S/W 문제해결 기본] 시리즈 1210. Ladder1 [문제] 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다. 100* 100 에서 맨 위에서 출발하여 가능한 길을 따라 도착하는 좌표를 출력한다. [제약 사항] 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다. [입력] 입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다. e.g. 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0..

SW Expert Academy [S/W 문제해결 기본] 시리즈 1209. Sum [문제] 다음 100X100의 2차원 배열이 주어질 때, 각 행의 합, 각 열의 합, 각 대각선의 합 중 최댓값을 구하는 프로그램을 작성하여라. [제약 사항] 총 10개의 테스트 케이스가 주어진다. 배열의 크기는 100X100으로 동일하다. 각 행의 합은 integer 범위를 넘어가지 않는다. 동일한 최댓값이 있을 경우, 하나의 값만 출력한다. [입력] 각 테스트 케이스의 첫 줄에는 테스트 케이스 번호가 주어지고 그 다음 줄부터는 2차원 배열의 각 행 값이 주어진다. e.g. 1 13 24 13 24 1 7 24 11 22 18 22 16 24 8 15 28 9 24 14 14 28 18 17 9 3 29 22 12 28 ..