친절한 도현씨 친절한 도현씨

# 그리디 알고리즘 # n의 범위가 현저히 작았다면 dfs 풀이도 가능한데 n의 범위가 너무 크다. ★ 풀이 이 문제의 주 목적은 욱제부터 공을 던지기 시작해서 마지막 사람이 받을 수 있냐 없냐이다. 결국 욱제부터 공을 던져서 욱제 오른쪽 사람들이 받으면서 마지막 사람한테 전해주면 된다. 그럴라면 어떻게 해야할까? 일단 최대 사거리로 던진다. 그리고 바로 오른쪽 사람이 받을 수 있다면 오른쪽 사람이 최대로 던진다. 그 과정에서 바로 전에 사람보다 더 멀리 던진다면 값을 갱신시켜주고 그것이 아니라면 값을 유지한다. 이 과정을 마지막 사람까지 반복해주면 된다. ★ 코드 import sys input = sys.stdin.readline n = int(input()) data = list(map(int,inp..

# 맛도리 문제였다 # 쉽지 않았다 # 그리디적인 생각 == 직관 # 누적합 여러 알고리즘이 결합된 맛있는 문제였다. 쉽지 않았고 중간에 포기할까도 생각했지만 스크롤을 내렸을 때 중등부 1번 문제인 것을 보고 더 생각을 해보기로 했다. 일단 주어지는 입력의 최대 크기는 십만이다. 마지막 테스트 케이스를 통과하기 위해서는 이 십만개의 테스트 케이스를 통과해야 한다. 문제를 읽고 단순하게 생각하기만 해 본다면 꿀벌이 위치해야 하는 위치 2곳과 꿀통이 위치해야 하는 위치를 합한 총 3곳을 조합 형태로 뽑아 경우의 수를 구하는 것에서 끝나는게 아니라 여기서 더 나아가 벌들이 위치한 곳에서부터 이동하면서 꿀을 채취해야한다. 더 나아갈 필요도 없이 3곳을 조합 형태로 뽑는 곳에서부터 시간 초과가 발생한다. 그렇다면..

와우와우와우와우와우 진짜 맛도리 문제였다. 처음에는 조합을 떠올렸으나 입력 크기를 보고 그리디를 생각했다. 하지만 그리디로 생각하기에는 말이 안되는 부분들이 많아서 dp가 아닌가 싶었다. 그런데 또 dp로 풀자니 안 돼서 알고리즘 분류를 봤다. 그리디, 누적합, 정렬이 있는 것을 보고 더 헷갈렸다. 정렬을 처음부터 하는 것은 문제에 어긋나는 것이기 때문에 안되고 그리디는 처음에 생각했던 것처럼 말이 안 됐고 남은 것은 누적합인데 평소에 ps에서 누적합의 빈도가 낮긴 했지만 그렇다고 모르는 알고리즘을 아니었지만 도대체 누적합으로도 어떻게 풀라는 것인가 k명이 교실을 선택해야 하는데 흠...... 교실 점수에 * 횟수를 막 그리디적으로 해보다가 문제에서 시키는 대로 그냥 한 명 한 명 교실을 택해서 앞으로 ..

5일 만에 풀었다. 원래 30분~1시간 정도 고민해보고 안 떠오르면 구글링을 하는 편인데 level2에 높은 정답률에 문제에서 무슨 알고리즘인까지 알려줘서 구글링을 하기에는 존심이 살짝 상해.. 할 것 없을 때 5분 씩 고민해봤다. # 접근 크지 않은 n의크기 wires의 길이는 n -1이라고 문제에서 주어졌으니 bfs를하면 시간내에 풀 수 있다. # 풀이 1. wires를 차례대로 하나씩 받아서 graph를 만든다. 2. 연결돼 있는 전력망을 끊었을 때 둘의 차이를 어떻게 구할까 => 끊고자 하는 전력망을 타고가서 몇 개가 연결돼 있는지 확인한다. 3. 구한 개수를 이제 나머지 부분에서의 개수와 빼주면 된다. 끝~~~ 쉽죠잉 (이걸 왜 처음에는 생각을 못했지...) # 코드 from collection..

(가성비 맛집입니다. 빠르게 개념을 잡고 싶으시다면 잘 오셨습니다. 읽기 좋게 간단명료하게 정리해놨습니다!!!!) ○ mongoDB란! mongoDB는 NoSQL 데이터베이스 중 한 종류로 비관계형 데이터베이스 시스템이다. 테이블 대신 문서 지향(Document-Oriented) 데이터베이스입니다. 유명한 관계형 데이터베이스(RDBM) 시스템인 MySQL과는 다른 데이터베이스 시스템을 가집니다. 또한 JSON 형태의 BSON(Binary JSON) 문서를 사용하여 데이터를 저장합니다. mongoDB는 컬렉션이 기본 단위로 db를 구성하며 db내에서 문서들을 논리적으로 그룹화한것입니다. ○ mongoDB 장점! 1. mongoDB는 속도와 효율성을 제공하는 목적에서는 효과가 좋은 DB이다. ex) 데이터를..

★ 접근 센서의 개수 최대 만 + 집중국의 개수 최대 천 + 센서 좌표값 (절댓값) 백 만 + 시간 제한 2초 => 종합적으로 미뤄봤을 때 그리디 알고리즘이 떠올랐다. 근데 도대체 이것을 어떻게 그리디로 풀 것인가? 오랜 시간 생각해서 떠오른 것은 일단 데이터를 정렬하고 index가 1차이 나는 센서끼리 차이를 구해보기로 햇다. ★ 풀이 집중국을 하나 설치한다는 것은 모든 센서가 하나의 집중국과 수신한다는 얘기이다. 즉 모든 센서가 하나의 구성이다. 집중국을 두개 설치한다는 것은 센서가 두 개로 나뉘어져서 집중국과 수신한다는 얘기이다. 즉 센서가 두 구성이다. 예제 입력 1번을 예시로 들어보면 센서간의 차이가 1,2,2,3이 있다. 여기서 집중국을 두개 설치하는데 둘의 차이가 가장 적은 1을 빼면 센서는..

★ 접근 문제 지문에서 '네트워크 형태' + n과 q의 최대 크기를 미뤄봤을 때 그래프 문제인 것을 떠올렸고 처음에는 dfs로 풀었다가 시간초과가 발생했다. 입력 최대 크기가 백을 넘어가면 웬만하면 dfs를 사용하지 않는데도 불구하고 dfs를 사용했던 이유는 k,v가 입력으로 주어졌을 때 매번 v에 대해서 dfs 성질을 이용해야 된다고 생각했기 때문이다. 역시나 시간초과가 나왔고 bfs로 풀었다. ★ 풀이 코드를 보면 어이가 없을 정도로 간단하다. 매 입력에 대해서 방문하지 않은 노드이면서 현재 usado가 k보다 크거나 같다면 q에 추가(노선을 따라감) count(결과 값)를 1씩 늘린다. ★ 코드 from collections import deque import sys input = sys.stdin..

★ 접근 r,c,n의 크기가 최대 200이기 때문에 bfs로 풀까 생각했지만 폭탄이 동시에 깔리고 동시에 터지는 문제는 bfs로는 풀기 힘든 상황들이 자주 발생해서 쌩 구현을 해도 된다고 생각하고 접근 ★ 풀이 n이 1초 => 초기 상태 출력 n이 짝수 => 모든 칸이 폭탄 그 외 = > 0초 폭탄, 1초 폭탄, 2초 폭탄을 나누어서 2초를 터트리고 0초를 1초로 만들고 => 다음 1초동안 모든칸 포탄 채우고 1초 => 2초 폭탄 0초 폭탄 생성 위 구문을 n-2초 동안 반복 ★ 코드 import sys input = sys.stdin.readline r,c,n, = map(int,input().split()) graph = [list(input().rstrip()) for _ in range(r)] i..