본문 바로가기

전체 글91

백준(BOJ) 7576 토마토(Python) BFS 문제. queue에서 좌표를 한 번 꺼내고, 주변 토마토를 익게 한 다음 현재 익은 토마토의 개수가 전체 토마토의 개수와 같다면 break한다. 만약 위에서 break하지 못했다면 이는 모든 토마토를 익게할 수 없는 경우이다. 그 외에는 while문을 돌기 전 현재 익은 토마토의 개수와 전체 토마토의 개수가 같다면 0을 출력한다. ​ 코드는 다음과 같다. ​ # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import permutations import bisect input=sys.stdin.re.. 2022. 7. 30.
백준(BOJ) 7569 토마토(Python) BFS 문제. 일반적으로는 dx와 dy만 사용하지만, 이 문제는 dz도 사용해서 각 이동마다 고려해준다. queue에서 좌표를 한 번 꺼내고, 주변 토마토를 익게 한 다음 현재 익은 토마토의 개수가 전체 토마토의 개수와 같다면 break한다. 만약 위에서 break하지 못했다면 이는 모든 토마토를 익게할 수 없는 경우이다. 그 외에는 while문을 돌기 전 현재 익은 토마토의 개수와 전체 토마토의 개수가 같다면 0을 출력한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools impor.. 2022. 7. 30.
백준(BOJ) 1083 소트(Python) 그리디 문제. 0번 인덱스부터 n-2번 인덱스까지 값을 수정하는데, 각 인덱스가 남아있는 교환 횟수를 초과하지 않는 선에서 가장 큰 원소를 갖도록 수정한다. 교환 횟수는 당연히 (목표 인덱스)-(현재 인덱스)로, 목표 인덱스의 값을 교환을 통해 현재 인덱스까지 가져오는 횟수이다. 교환 횟수가 0이거나, 현재 인덱스의 값이 이후 인덱스의 모든 값보다 큰 경우를 예외 처리해줬다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import permutations import bisect .. 2022. 7. 25.
백준(BOJ) 12892 생일 선물(Python) 두 포인터 문제. 선물의 가격을 기준으로 입력값을 오름차순 정렬한 리스트를 생성하고, s, e 두 포인터를 이용해 문제를 해결했다. (e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만인 경우 k에 e가 가리키는 선물의 만족도를 더한다. 그러다가 d 이상인 경우 ans를 max(k,ans)로 갱신하고, (e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만이 될 때까지 s를 옮기며 k를 수정한다. e가 n인 경우 이를 종료한다. 마지막에는 ans를 한 번 더 갱신해주는데, 이는 목록 중 가장 비싼 선물과 싼 선물의 값 차이가 d 미만인 경우 ans가 위 과정에서 갱신되지 않기 때문이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import .. 2022. 7. 23.
백준(BOJ) 2580 스도쿠(Python) 백트래킹 문제. 빈 칸의 좌표를 먼저 모두 담은 리스트를 만들고, 그 리스트의 원소의 개수만큼 백트래킹을 하며 문제를 해결했다. 어떤 수를 빈 칸에 넣을 때 행과 열, 3X3 칸에 같은 수가 존재하는 지를 확인하고 존재하지 않는다면 다음 칸으로 넘어가는 방식으로 해결했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) L=[list(map(int,input().split())) .. 2022. 7. 23.
백준(BOJ) 9663 N-Queen(Python) 백트래킹 문제. 각 행마다 퀸을 하나씩 배치하는데, 이때 이전 행에 배치한 퀸의 열 번호를 토대로 현재 위치에 퀸을 배치할 수 있는 지를 판단한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n=int(input()) L=[0]*n ans=0 def func2(k): for i in range(k): if L[k]==L[i] or abs(L[k]-L[i])==k-i: retu.. 2022. 7. 22.

티스토리툴바