Algorithm
[프로그래머스/파이썬(Python)] 모두 0으로 만들기
https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 트리구조와 DFS를 사용하는 문제입니다. 최근에 기업 코딩테스트에서 트리 문제가 자주 나오기 때문에 잘 알아두면 좋을 것 같습니다. 이 문제의 특징은 1) 어떤 정점을 잡아도 해당 정점이 루트 노드가 될 수 있다는 점, 2) 따라서 아무 정점이나 잡은 다음에 DFS를 통해 Leaf 노드까지 내려갈 수 있고, 3) Leaf 노드부터 가중치를 부모..
Algorithm
[프로그래머스/파이썬(Python] 이진 변환 반복하기
코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr - 문제에서 요구한 조건 그대로를 재귀적으로 반복해서 수행하면 되는 문제입니다. [코드] def binaryTranslate(x, tanslateCount, zeroCount): # 종료조건 x == 1 if x == '1': return tanslateCount, zeroCount # 모든 0을 제거 numOfZeroes = x.count('0') x = '1' * (len(x) -numOfZeroes) zeroCount += numOfZeroes # x는 x의 길이 c를 이진법으로 표현한 문자열 x = bin(len(x))[2:] return binaryTranslate(x, tanslateCount+1, zeroCount) de..
Algorithm
[프로그래머스] 2개 이하로 다른 비트
코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 한 개 혹은 두 개의 비트만 바꿔서 현재 숫자보다 큰 값중 최솟값을 찾는 문제입니다. 현재 숫자의 모든 비트가 1인 경우와 0이 한 개라도 존재하는 경우로 나눠서 생각하면 됩니다. 그 이유는 아래와 같습니다. 1) 모든 비트가 1이라면 이보다 큰 수를 만들기 위해서는 무조건 앞에 1비트를 붙이고, 그 다음에 1비트를 0으로 바꿔주는게 최선이겠죠. 2) 비트 중에 하나라도 0이 있다면 그 비트를 1로 바꾸는 순간 현재 숫자보다는 커지는 값이 됩니다. 따라서 되도록 작은 주소값에 있는 0비트를 1비트로 바꾸고, 만약 그 뒤로 1비트가 나타난다면 그 비트도 0으로 바꾸면 총 2개의 비트를 바꾸고 최적값을 찾을 수 있습니다. 이를 코드로..
Algorithm
[프로그래머스] 괄호 회전하기
코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 올바른 괄호 문자열인지 확인하는 함수는 스택을 이용하여 작성했고, 메인 solution 함수에서는 문자열을 회전하면서 올바른 괄호열 때 answer를 1씩 증가시키도록 했습니다. [풀이] # 올바른 괄호 문자열인지 확인하는 함수 def isValidBusket(str): stack = [] for s in str: if len(stack) == 0: stack.append(s) else: # 스택 마지막 원소가 여는 괄호이면서 현재 문자는 닫는 괄호 if stack[-1] in bucketDict and s not in bucketDict: # 두 괄호가 매치되지 않으면 False if s != bucketDict[stack[-1]]: r..
Algorithm
[프로그래머스(Programmers)] 게임 맵 최단거리
https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr BFS로 풀 수 있는 전형적인 문제입니다. 최단거리를 구해야하기 때문에 너비 우선 탐색을 진행해주고 도착점에서 결과값이 1이면 거리가 갱신되지 못한 것이므로 -1을 리턴하고, 그 외에는 도착점의 값을 리턴해주면 됩니다. [풀이] from collections import deque dx, dy = [1,-1,..
Algorithm
[프로그래머스] 쿼드압축 후 개수 세기
https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr - 백준에 있는 쿼드트리 압축 문제와 거의 똑같은 문제다. 각 구간의 시작점과 길이를 생각하는 것이 포인트인데, 이 문제에서는 2의 거듭 제곱수 형태를 하고 있으므로 재귀 호..
