여행자의 책

N= int(input()) num_list = list(map(int, input().split())) M = int(input()) test_case = list(map(int, input().split())) num_list.sort() #타겟 리스트를 정렬 def bs(num_list, start, end, num): mid = (start + end)//2 if num_list[mid] == num: return 1 if start > end: return 0 if num_list[mid] > num: #중간 값이 찾고자 하는 값보다 크면 앞쪽을 찾으면 된다. answer = bs(num_list, start, mid-1, num) if num_list[mid] < num:#중간 값이 찾고자 하..

import sys sys.setrecursionlimit(100000) N, M = map(int, input().split()) woods = list(map(int, input().split())) def calcHeight(cr, woods): answer =0 for wood in woods: if wood > cr: answer += wood-cr return answer def bs(height, woods, start, end): mid = (start + end)//2 cutWoods = calcHeight(mid, woods) if start > end: return mid if height cutWoods: end = mid -1 answer = bs(height, woods, sta..

전형적인 이분 탐색 1. input을 받고 2. 정렬을 한 다음 3. 이분탐색 함수를 구현해서 돌리면 된다. 간단! 파이썬으로 하면 시간 초과가 나는데 Pypy3로 돌려주면 통과! value = int(input()) num_list = [int(i) for i in input().split()] N= int(input()) test_case = [int(i) for i in input().split()] num_list.sort() def bs(value, num_list): mid = len(num_list)//2 if num_list[mid] == value: return 1 if len(num_list) value: answer =bs(value, num_list[:mid]) elif num_li..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 풀이 삼성 A형 기출 문제/구현과 브루트포스 반복문이 다음과 같은 방식으로 진행된다. 궁수의 배치를 바꿔가면서 아래를 진행한다. 1. 공격할 대상 찾기 2. 공격 3. 적 좌표 업데이트 4. 공격한 대상 제거 게임 맵 전체를 갖고 연산을 수행하는게 아니라 목표를 갖는 배열을 따로 만들어서 관리하는게 낫다 def calc_distance(case): #궁수별 공격가능한 좌표를 찾아서 저장해준다. poss..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1. 풀이 문제 : BOJ 9730 미확인 도착지 알고리즘 유형 : 다익스트라 시작점 A에서 T까지 가는 최단 경로중 경유지에 g,h 노드가 있는지 확인하는 문제였다. 맨 처음 풀 때는 최단경로를 지나는 경로중에 g,h가 있으면 출력하도록 했는데 최단 경로가 여러개 있는 경우를 잡지 못해 실패했다. S에 T까지 가는 최단 경로중 g,h가 포함되어 있음을 보장하기 위해선 다음을 만족해야한다. ..

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 : 1774ms BOJ 1039 교환 파이썬 BFS 문제 맨 처음에 모든 자릿수에 대해 방문여부를 확인 하는 배열을 만들려고 했지만 자꾸 시간초과가 났다. 전체 숫자 범위(1에서 1,000,000)와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열을 만든뒤 BFS를 수행한다. N, K = input().split() M = len(N) #전체 자릿수 K = int(K) #전체 숫자 범위와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열 cache =[[..

1. 상호 배타적 집합과 유니온 파인드 상호 배타적 집합이란 서로간의 교집합이 없는 부분집합을 의미한다. 이를 표현하기 위해 유니온 파인드(Union Find) 라는 자료구조를 사용한다. 상호 배타적 자료구조를 표현하기 위해선 크게 3가지 연산이 필요하다. 1. 초기화(Initialization) : n개의 원소를 n개의 집합에 포함되어 있도록 초기화 2. 합치기(Union) : 두 원소에 대해 이 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합친다. 3. 찾기(Find) : 임의의 원소가 어떤 집합에 속해 있는지 반환 => 이러한 연산을 클래스로 구현해주면 된다. 2. 구현 다음은 파이썬으로 구현한 Navie한 Union 파인드이다. class NaiveDisjointSet(): parent =..

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 1. 풀이 다이나믹 프로그래밍 문제다. 규칙 1, 2, 3에 따라 채워가면 되는 문제로 bottom up 방식을 사용했다. * 먼저 카드 개수가 N이라고 할 때 N*N을 만들고 뒤쪽에서 부터 채워간다. * i 인덱스는 left의 카드번호 j 인덱스는 right 의 카드번호를 의미한다. * left[i] > right[j] 인 경우에는 오른쪽 카드를 버리고 스코어에 버..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 풀이 전형적인 플루이드 마셜 구현 문제이다. 플루이드 마셜은 모든 노드에대한 모든 노드의 최단 거리를 구하는 알고리즘이다. 특정한 학생의 키순서를 알기 위해선 자신보다 몇 명이 큰지 그리고 몇명이 작은지 전체 학생 수에 대해서 알아야한다. 예를 들어 전체 학급 구성이 8명인 반에서 학생 A가 전체 반에서 4번째로 크다고 가정해보자. 이 학생이 4번째로 큰 학생임을 알기 위해선 위로 3명 아래로..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 전형적인 삼성 DFS/BFS + 구현 문제 였다. 규칙이 복잡하게 구성되어 있기 때문에 구조를 먼저 짠 후에 코드를 작성하도록 하자 1. 초기 상어의 위치를 알아내고 상어위치에 있는 값을 0으로 바꾸어준다. 반복문 1. 상어의 위치 주변에 먹을 수 있는 물고기가 있는지 확인한다. 2. 있으면 먹은 후 시간, 먹은 횟수, 사이즈, 상어의 위치를 업데이트 한 후 continue를 통해 1과..