CS/Algorithm
[프로그래머스(파이썬/Python)] 순위
https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 이 문제를 해석할 때 가장 중요한 포인트는 "어떤 상황에서 순위가 결정되는가?"에 대한 이해입니다. 순위가 결정되려면 자신이 결투를 해서 이기는 사람, 지는 사람을 카운트할 때 자신을 제외한 n-1명의 정보가 모두 있어야 합니다. 따라서 results 배열로 주어진 승패 정보를 통해 먼저 각 사람이 이길 수 있는 사람 리스트를 DFS 탐색으로 만들 수 있고, 이 리스트를 바탕으로 역으로 생각해볼 때 이긴 사람의 리스트에 포함된 사람은 해당 사람에게 진 사람이 되기 때문..
CS/Algorithm
[프로그래머스 / 파이썬(Python)] 110 옮기기
https://programmers.co.kr/learn/courses/30/lessons/77886 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 사전 순으로 앞에 오기 위해서는 "110이 무조건 111보다 앞에 있어야 한다"는 아이디어를 떠올려야 하는 문제입니다. 스택을 이용해 문자열을 순회하면서 110을 따로 추출해주고 나면, 110이 모두 제거된 후에 문자열은 연속된 1이 나타나는 지점이 없거나, 한 곳밖에 존재할 수 없습니다. 1이 연속되다가 0이 나타나면 110형태가 되어버..
CS/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 노드부터 가중치를 부모..
CS/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..
CS/Algorithm
[프로그래머스] 2개 이하로 다른 비트
코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 한 개 혹은 두 개의 비트만 바꿔서 현재 숫자보다 큰 값중 최솟값을 찾는 문제입니다. 현재 숫자의 모든 비트가 1인 경우와 0이 한 개라도 존재하는 경우로 나눠서 생각하면 됩니다. 그 이유는 아래와 같습니다. 1) 모든 비트가 1이라면 이보다 큰 수를 만들기 위해서는 무조건 앞에 1비트를 붙이고, 그 다음에 1비트를 0으로 바꿔주는게 최선이겠죠. 2) 비트 중에 하나라도 0이 있다면 그 비트를 1로 바꾸는 순간 현재 숫자보다는 커지는 값이 됩니다. 따라서 되도록 작은 주소값에 있는 0비트를 1비트로 바꾸고, 만약 그 뒤로 1비트가 나타난다면 그 비트도 0으로 바꾸면 총 2개의 비트를 바꾸고 최적값을 찾을 수 있습니다. 이를 코드로..
CS/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..
CS/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,..
CS/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의 거듭 제곱수 형태를 하고 있으므로 재귀 호..
