Magin-playground Magin-playground

1) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2)알고리즘 - 한마디로 표현하면 '대칭이동을 활용한 최단거리 구하기' # 문제를 풀고 정리하다가 깨달았다.(참고) - 몇몇 상황을 제외한 상황(즉 한쪽 축이 같은 좌표값을 갖는 경우) 모두 4개의 벽 중 가장 최단거리 구하기 # 문제를 풀고 정리하다가 3) 코드 def solution(m, n, startX, startY, balls): answer = [] for n_x, n_y in balls: if startX == n_x: if n_y > startY : answer.append(min((..

문제) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘) 1. 각 리스트의 최대 공약수를 구하기(math.gcd 함수) 2. 각각 구한 최대 공약수로 서로의 숫자카드를 나눠 조건에 해당하는지 판단 3. 조건에 만족시 가장 큰 수 max 출력 그 외 0 출력 * 유클리디안 알고리즘(최대 공약수 구하기) - 두 수 U, V가 있을 때 (U > V) 최대 공약수 구하기 - U - V와 V의 최대 공약수는 동일하며 해당 과정을 통해 U와 0이 될 때 최대공약수는 U가 된다. 1. U < V 라면 두수 U, V를 바꾼다. 2. U = U - V 3. U가 ..

문제) 알고리즘) - 시간복잡도를 생각하지 않고 문제를 본다면 대부분 for문과 sum 함수를 반복해서 사용해서 코드를 짜면 될 것 같지만 예시) for i in range(N-X+1): #윈도우의 크기와 graph의 크기를 고려해서 움직일 수 있는 횟수만큼 반복 now = sum(graph[i:i+X]) #매번 sum함수로 해당 윈도우안에 해당하는 값 sum 이 경우 시간복잡도에서 걸리게 되어 시간초과가 됩니다.(for문과 sum 동시에 반복시 n^2의 시간복잡도 갖는다 최악!!) - 핵심은 이름 그대로 Sliding Window처럼 지나가면서 윈도우에서 벗어나는 값은 빼고 새로 들어오는 값 더하기 start += graph[i] #들어오는 값 start -= graph[i-X]빠져나가는 값 코드) #..

문제) 알고리즘) * 해당문제는 백준에 "회의실 배정"이란 이름의 문제 비슷합니다. - 목표는 가장 많이 강의실 배정을 하는 것 - 처음에는 sorted, lambda를 사용하여 진행했으나 시간 초과!! - heapq를 사용하여 각 입력시간에서 fin시간이 이른 시간부터 정렬 - 그후 기준점 과 수업 시작시간과 비교하여 사용가능하다면 cnt하고 v를 해당 start로 갱신 이를 입력부에서 받은 모든 값을 돌리고 최종 cnt 출력 코드) import sys import heapq input = sys.stdin.readline n = int(input()) time = [] w = 0 #기준 cnt = 0 #강의실 수 카운트 for _ in range(n): start, fin = map(int, inpu..

문제) 알고리즘) 출력 기준 1. 출발 시작점 좌표값 2. 시작시 로봇이 바라보는 방향 3. 시작부터 끝까지 로봇이 이동 결과 (전진, 좌회전, 우회전) *시작점 찾기 -그래프 탐색을 통해 '#'를 찾고 현재 위치 '#'에서 4방향을 탐색해 '.'이거나 범위외 좌표를 포함해 3개이상이라면 해당 위치는 출발점으로 설정합니다. *이동 - 이동전에 로봇의 현재 상태(방향)를 출력하고 시작한다. - 일반적인 BFS알고리즘을 사용해서 '#'를 찾으며 이동하고 방문처리는 '#' -> '.'로 바꾸면서 처리했습니다. - 3번쨰 출력물인 이동 결과는 코드상에서 방향잡기아래에 해당하는 코드로 처리했습니다. 코드) #[인증평가(1차) 기출] 로봇이 지나간 경로 #사수가 조작한 로봇이 i행 j열을 방문했다면 #이고, 방문하..

문제) 알고리즘) -그래프의 대표적인 bfs 활용 - bfs탐색을 통해 이어져 있는 단지의 크기와 개수를 출력하는 것 - 방문처리는 1 => 0으로 변환하며 처리 코드) #단지번호붙이기 import sys input = sys.stdin.readline n = int(input()) g = [] size = [] move_x = [-1, 0, 1, 0] move_y = [0, -1, 0, 1] for _ in range(n): g.append(list(map(int, input().strip()))) def dfs(y,x): global cnt #단지별 사이즈 if x = n or y = n: #범위밖 조선 return 0 if g[y][x] == 1: #확인된 자리 g[y][x] = 0 cnt += 1..

문제) 알고리즘) 그리디 알고리즘 대표적인 문제 -동전을 내림차순으로 정렬 -큰값부터 차례로 나눠준다 (나눌때 몫을 카운트) 동전 수 출력 코드) #다시 풀이 # 동전0 import sys from collections import deque input = sys.stdin.readline cnt, price = map(int, input().split()) result = 0 coin = [] for _ in range(cnt): coin.append(int(input())) coin.sort(reverse= True) coin = deque(coin) while coin: current = coin.popleft() if current > price: continue result += (price//..

문제) 알고리즘) 풀이 핵심) - 토너먼트의 특징을 잘 생각해보자 풀이) -주어지는 두값은 무조건 생존 -각 라운드마다 절반으로 감소한다 ex) f_1 20 10 5 2 1 f_2 31 15 7 3 1 해당 사이클로 만나게 되는 라운드 값 출력 코드) #토너먼트 import sys input = sys.stdin.readline n, f_1, f_2 = map(int ,input().split()) cnt = 0 while f_1 != f_2: f_1 -= f_1//2 f_2 -= f_2//2 cnt += 1 print(cnt)