본문 바로가기

전체 글91

백준(BOJ) 1113 수영장 만들기(Python) BFS 문제. 가장 먼저 물을 채울 시작점을 구해야한다고 생각했다. 물을 채울 수 있다는 근거는, 칸의 상하좌우 중 현재 칸의 높이보다 높은 칸이 존재하는 것이라고 생각했다. 그렇게 칸을 정하고 나면 상하좌우 중 가장 높은 높이부터 가장 낮은 높이까지 물을 채워본다. 편의상 물의 높이를 w라 하겠다. w보다 칸의 높이가 더 낮다면 queue에 칸의 좌표를 push하는 방식으로 BFS를 진행했다. 만약 BFS를 진행하다 리스트 범위를 벗어나는 좌표가 나타나면 이는 물이 넘치는 것이므로 BFS를 중단한다. 그렇지 않고 끝났다면 현재 w는 그 칸에서 시작해 채울 수 있는 가장 높은 물의 높이일 것이므로, BFS를 하며 계산한 수영장의 부피를 ans에 더한다. 만약 물을 채우는 데에 성공했다면 모든 칸의 높이를.. 2022. 7. 11.
백준(BOJ) 1724 그림판(Python) BFS로 풀 수 있었던 문제. 일반적인 BFS 문제와는 달리 벽을 생성해야 하는 문제였다. 컴실1 maze project에서 이와 비슷한 유형의 자료구조를 구현해봤기 때문에 쉽게 풀 수 있었다. 2차원 리스트의 각 칸을 하나의 픽셀로 생각하고, 그 픽셀의 상, 하, 좌, 우 방향으로 이동할 수 있는지를 체크해줬다. 처음에는 모두 이동할 수 있도록 초기화하고, 가장자리 픽셀에서 리스트 밖으로는 벗어나지 못하도록 한 뒤 선분을 입력받는다. 입력받은 선분이 리스트의 가장자리에 위치한다면 pass하고, 그렇지 않은 경우 두 점의 x좌표가 동일하다면 x좌표를 기준으로 변화하는 y좌표에 대해 해당하는 선분의 위 픽셀은 아래로 이동할 수 없고, 아래 픽셀은 위로 이동할 수 없도록 설정한다. y좌표는 x좌표와 마찬가지.. 2022. 7. 10.
백준(BOJ) 3111 검열(Python) 문자열 테크닉으로 해결할 수 있는 문제였다. 앞에서부터 stack(L1)에 문자를 하나씩 넣다가 L1의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop, 그 다음에는 새 stack(L2)에 뒤에서부터 문자를 하나씩 넣다가 L2의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 reversed(A)와 같으면 len(A)개 만큼 pop한다. 위의 모든 작업이 끝나면 L2에서 pop한 문자를 L1에 push하면서 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop해준다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collecti.. 2022. 7. 10.
백준(BOJ) 7344 나무 막대(Python) 간단한 그리디 문제. 문제를 풀기 위한 아이디어를 떠올리기 쉬웠던, 문제에 나온 대로만 하면 되는 문제였다. 입력받은 막대의 l, w 값을 l의 오름차순에 w의 오름차순으로 정렬하고, [[[0,0]]] 형태의 리스트를 만든다. 이 리스트를 L이라 하자. L은 가동되는 기계가 어떤 막대를 가공할 지를 담고 있을 것이다. L의 최종 개수는 기계의 개수이고, 이는 최소 작동 준비 시간일 것이다. 우리는 각 막대의 l, w 값을 L의 모든 원소의 마지막 원소의 0, 1번째 인덱스에 위치한 값과 비교할 것이다. 그리고 l=L3[k][-1][1]: L3[k].append(X) flag=1 break if not flag: L3.append([X]) print(len(L3)) 풀고 난 느낌은, 문제가 overrate.. 2022. 7. 9.
백준(BOJ) 17386 선분 교차 1(Python) 먼저 L1에서 L2의 두 점에 대해 CCW를 해본다. 그 때 두 점의 회전 방향이 같으면 두 선분은 교차하지 않지만, 두 점의 회전 방향이 다르면 두 선분이 교차하는 것이 아니라 CCW를 L2에서 L1의 두 점에 대해 해줘야한다. 그 때 두 점의 회전 방향이 같으면 두 선분은 교차하지 않는다. 코드는 다음과 같다. x1,y1,x2,y2=map(int,input().split()) x3,y3,x4,y4=map(int,input().split()) a=(x3-x2)*(y2-y1) b=(y3-y2)*(x2-x1) c=(x4-x2)*(y2-y1) d=(y4-y2)*(x2-x1) k1=0 k2=0 if a>b: k1=-1 elif ad: k2=-1 elif cf: k3=-1 elif eh: k4=-1 elif g 2022. 7. 9.
백준(BOJ) 11758 CCW(Python) 그냥 수학 문제다. P1, P2, P3에 대해 직선 P1P2의 방정식을 구하고, 거기에 x3를 대입해 구한 y값과 y3을 비교하면 끝이다. P3에서 P2를 중심으로 회전하되, 반직선 P2P1에 도달할 수 있는 가장 가까운 방식으로 회전해야 하기 때문이다. y값이 y3보다 크면 시계 방향, 작으면 반시계 방향, 같으면 일직선이다. 그림을 그려 표현하면 쉽지만, 귀찮기 때문에 생략하도록 하겠다. 코드는 다음과 같다. x1,y1=map(int,input().split()) x2,y2=map(int,input().split()) x3,y3=map(int,input().split()) a=(x3-x2)*(y2-y1) b=(y3-y2)*(x2-x1) if a>b: print(-1) elif a 2022. 7. 9.

티스토리툴바