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

● 접근법 - 처음에 격자 그림이 주어지고 항체가 상하좌우로 퍼진다는 조건을 보고 bfs를 떠올렸다. N,M의 크기가 크지 않은 것을 보고 bfs 확신이 생겼다. ● 풀이법 ★ 두개 before에서 상하좌우로 마주친 칸이 같은 크기였다면 항체는 무조건 퍼져야 한다. ★ 1. 그래프를 순차적으로 하나하나 탐색하면서 방문하지 않은 좌표를 check()함수를 이용해 확인한다. 2. beforeNumber와 afterNumber의 값이 다르다면 answer + 1해준다. (answer의 크기가 1 보다 커진다면 만들어질 수 없는 그래프이다. 왜냐하면 항체는 한 번만 뿌리기 때문이다.) 3. 상하좌우를 탐색하면서 그래프 안에 있으면서 before 그래프에서 서로 크기가 같은 것만 확인한다. (이 문제의 key는 ..

★ 접근법 그래프의 크기, 명령의 개수 입력들의 최대 사이즈가 크지 않았기 때문에 단순 구현으로 접근했다. ★ 풀이법 (좌표의 이동과 그래프의 범위를 벗어나는 것을 계산하는 것은 단순했기 때문에 메인인 주사위 굴리는 것에 초점을 뒀다) 1. 주사위 리스트를 만들어놓고 주사위 인덱스에 자신이 생각하는 인덱스별 주사위 면의 위치를 정한다. (필자는 밑면, 뒷면, 윗면, 앞면, 왼쪽면, 오른쪽면을 기준으로 했다.) 2. 주사위를 굴리는 방향 별로 주사위 면의 위치가 바뀌는 것을 구현해준다. - 코드 n,m,r,c,k = map(int,input().split()) data = [] for i in range(n): data.append(list(map(int,input().split()))) command =..

※ 접근법 입력제한에서 N의 최대 크기는 50이었고 k의 최대 크기는 1000이었기 때문에 문제에서 시키는대로만 구현하면 된다. ※ 풀이 1. defaultdict(list)인 사전형을 두개 만들었다. 2. 사전형의 키는 좌표 값이었고 좌표 값은 변하지 않을 것이기에 튜플 형태로 지정했다. value값은 질량,속도,방향순서대로 리스트 형태로 삽입했다. 3. k의 크기만큼 start(파이어볼 움직임), check(파이어볼이 두개 이상 뭉쳐있는지)를 실행해줬다. 4. start()함수는 매우 간단한데 dic에서 key를 하나씩 꺼내서 파이어볼을 이동시켜준다. 5. check() 함수도 문제에서 시키는 대로만 하면 되는 간단한 함수이다. 6. 문제 알고리즘 유형 자체가 구현, 시뮬레이션으로 구분 되기 때문에 ..

※ 접근법 n의 숫자가 크지 않았기 때문에 구현으로 풀어야겠다고 생각했다. ※ 풀이 1. 처음 도우만 선택했을 때 1원당 칼로리를 계산해놓는다. 2. 입력받은 칼로리를 리스트에 저장해놓고 내림차순으로 정렬한다. 3. 리스트에서 칼로리를 하나씩 보면서 1원당 칼로리를 계산하고 이전에 구했던 것보다 작아진다면 반복문을 탈출한다. ( 토핑의 가격은 하나로 고정돼있기 때문에 칼로리를 내림차순으로 정렬해놓으면 뒤로 갈수록 1원당 가격이 내려갈 수 밖에 없다.) n = int(input()) a,b = map(int,input().split()) dow = int(input()) data = [] for i in range(n): data.append(int(input())) data.sort(reverse=Tru..

※ 접근 입력 개수가 최대 3,000,000만이었기 때문에 반복을 한 번 돌아야겠다고 생각을 했고 이벤트에 무조건 참여해야했기에 k개의 초밥을 무조건 먹었어야했다. 그래서 k개씩 짤라서 이동해야했기에 슬라이딩 윈도우를 사용했다. (문제에서 주어진 조건대로 구현했지만 이런 방식의 알고리즘을 슬라이딩 윈도우라고 부른다.) ※ 풀이 1. 이벤트에 무조건 참여해야했기에 c 쿠폰번호의 초밥은 무조건 먹었다고 가정했다. 2. 처음에는 left, right(코드에서는 left, right가 없지만)가 움직일 필요가 없기에 k개까지 초밥을 먹는다. 3. 그 다음부터는 가장 맨 처음 먹었던 초밥은 뱉고 마지막에 먹었던 초밥 바로 오른쪽 것을 먹어주는 동작을 반복한다. -- 정답 코드 -- import sys input ..

※ 접근 풍선의 갯수가 최대 백 만개였고 데이터를 정렬시킬 수도 없었기 때문에 그리디 알고리즘으로 풀어야겠다고 생각했다. ※ 풀이 1. defaultdict를 이용해서 해당 바늘이 key에 존재하지 않거나 value가 0이라면 결과값을 + 1을 해주고 해당 바늘 -1한 값을 key로 만들어줬다. 2. 해당 바늘이 있었다면 value -1을 해주고 해당 바늘 높이 -1한 값을 key로 만들어줬다. from collections import defaultdict import sys input = sys.stdin.readline n = int(input()) data = list(map(int,input().split())) s = defaultdict(int) count = 0 for i in data: ..

※ 접근법 옥상의 개수가 최대 팔만 개였기 때문에 단순 이중 for 문을 돌면 시간 초과가 발생할 것이라고 생각을 했다. 높이를 정렬을 하면 안 됐기 때문에 느낌상 스택을 사용해야 할 것 같았다. ※ 풀이 생각의 전환이 필요한 문제이다. 내가 바라볼 수 있는 옥상 정원의 개수가 아니라 나를 바라보는 옥상의 개수를 구하는 것이다. 1. stack이 아니라 단순 스택이라고 불리는 내림차순, 올림차순을 유지하는 stack을 만드는 것이다. 2. 10, 3, 7, 4, 12, 2라고 했을 때 10은 일단 stack에 넣는다. [10] 10은 맨 왼쪽에 있기 때문에 바라볼 수 있는 옥상이 없다. 3. [10,3]은 3을 바라볼 수 있는 옥상 10이 있기에 len(stack) - 1(자기 자신을 바라볼 수 없으니)..

※ 접근법 주사위 갯수가 최대 만 개였지만 따져야할 주사위 면에 주사위 숫자는 1~6으로 고정돼 있었기 때문에 경위의 수가 많지 않다고 생각해 문제에서 시키는 대로 구현하면 풀릴 것이라고 생각했다. ※ 풀이 (전체적인 관점 : 주사위 윗면 아랫면에 4,5,6이 없다면 옆면으로는 계속 회전시킬 수 있기 때문에 어떻게든 최대인 기둥이 만들어진다. 그렇다면 윗면 아랫면에 6 or 5 or 4가 없는지 확인하고 없다면 elif문으로 걸러서 제일 큰 숫자를 더해준다. 1. 첫 번째 주사위에 윗면을 담당할 숫자는 1~6까지가 있다. 2. 윗면 아랫면에 4,5,6이 없었다면 임의 변수 temp에 6또는 5또는 4를 더해준다. 3. 이것을 마지막 주사위까지 반복해주면 되는 간단한(?) 문제였다. n = int(inpu..