Coding Test

예상 대진표 (XOR 연산, bit_length)

[1057] 토너먼트 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 karla.tistory.com import math def solution(n,a,b): # a, b 를 xor 취하는 과정에서 ab 사이의 거리가 가까우면 상위비트는 차이가 나지않음 # 거꾸로 ab 사이의 거리가 멀면 상위비트가 차이남 return ((a-1)^(b-1)).bit_length()

점프와 순간 이동 (이진수 변환)

분석 1칸만 이동한다면 2,4,8,16,32,64,...칸은 건전지 사용 없이 이동 가능 2로 나누어 떨어지면 건전지 없이 이동, 나누어 떨어지지 않으면 건전지 사용 풀이 def solution(n): cnt=0 while n!=0: if n%2==0: n/=2 else: n-=1 cnt+=1 return cnt 이진수로 변환 후 1의 개수 카운트 (나머지가 있을 때 1이므로) def solution(n): return bin(n).count('1')

[11729] 하노이 탑 이동 순서 (재귀)

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 분석 1) 재귀 원반이 두 개 이상이면 원반의 개수를 n 이라 할 때, 가장 아래에 있는 원반 n을 도착 기둥에 옮기기 위해 그 위에 놓여 있는 n-1개의 원반을 보조 기둥에 옮긴다. 원반 n을 도착 기둥에 옮긴다. 보조 기둥에 있는 n-1개의 원반을 도착 기둥에 옮긴다. 2) 점화식 먼저 "수열 An​= n개의 원판을 이동하는 횟수" 라고 정의하자. n개의 원판을 이동시키기 위해서는 그 위의 n-1개의 원판을 다른 막대로 이동하고 맨 아래쪽 원판을 ..

연속된 부분 수열의 합 (투포인터)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 [1253] 좋다 (좋은 수 구하기, 투 포인터) 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 분석 투 포인터 이동원칙 A[i] + A[j] > K : j--; A karla.tistory.com 풀이 import sys def solution(sequence, k): answer = [] n=len(sequence) sums = 0..

유사 칸토어 비트열

n 번째 일 때 1의 개수는 4**n 개이니까 주어진 구간을 5의 배수로 나누었을 때 나눠지면 그때의 제곱수가 n 번째 단계의 1의 개수 값과 동일하다. 이런 식으로 나머지가 없어질 때까지 반복하면 주어진 값까지의 1의 개수를 구할 수 있고 a~b 구간의 값을 구하려면 b까지의 1의 개수에서 a까지의 1의 개수를 빼면 된다. def solution(n, l, r): answer = 0 l-=1 a=b=0 def f(x): for i in range(20,-1,-1): if 5**i2: t-=1 return (4**i)*t, x%(5**i) while l or r: a1,l = f(l) b1,r = f(r) a += a1 b += b1 return b-a def solution(n, l, r): answe..

뒤에 있는 큰 수 찾기 (스택)

def solution(numbers): answer = [-1]*len(numbers) stack = [] for i in range(len(numbers)): while stack and numbers[stack[-1]]

당구연습 (그래프, 구현)

import sys,math # 점과 점 사이의 거리 구하는 함수 def dist(x1, y1, x2, y2): result = math.sqrt(math.pow(x1-x2,2) + math.pow(y1-y2,2)) return result def solution(m, n, startX, startY, balls): answer=[] for endX, endY in balls: minval=sys.maxsize # 일직선으로 공이 먼저 부딪히는 경우 빼고 계산 if not (startX==endX and startYendY): # 하 minval = min(minval, dist(startX, -startY, endX, endY)) if not (startY==endY and startX>endX): #..

빛의 경로 사이클 (그래프, 모든 좌표, 네방향 탐색)

https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dr = (1, 0, -1, 0) dc = (0, -1, 0, 1) def solution(grid): # 빛의 경로 싸이클 길이 리스트 오름차순 리턴 answer = [] """ 0,0 에서 시작 네방향 탐색 bfs """ lr, lc = len(grid), len(grid[0]) print(lr,lc) # 네방향 방문 기록 visited=[[[False]*4 for _ in range(lc)]..

2개 이하로 다른 비트 (x보다 큰 1~2비트 다른 가장 작은 수)

https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 숫자가 짝수인 경우 항상 가장 마지막 비트는 0이다. 따라서 마지막 비트를 0에서 1로 바꿔준 값이 답이기 때문에 숫자+1 값을 answer에 넣어준다. 숫자가 홀수인 경우 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔주면 된다. 예를 들어 7(0111) 은 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를..

다리를 지나는 트럭 (다리 큐, 대기 큐)

from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 w=0 # 다리에 올라간 트럭들 무게 wq=deque(truck_weights) # 대기트럭 큐 bq=deque([0 for _ in range(bridge_length)]) # 다리 큐 time=0 while len(wq) or w>0: w-=bq.popleft() if len(wq) and w+wq[0]