코테

[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. (링크: https://leetcode.com/problems/trapping-rain-water/description/) 문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다. 이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다. 하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다. 풀이: 투 포인터 활용 투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..

[SQL] 조건에 부합하는 중고거래 댓글 조회 (프로그래머스)

프로그래머스 SQL LV1 문제중 가장 질문 게시판이 핫한 문제중 하나를 들고 와봤다. 이 문제는 두 테이블 (게시판 & 댓글)을 활용하여 쿼리를 작성하는 전형적인 join 과 관련된 문제이다. 이 문제는 DATE 형태만 제대로 작성하면 문제없이 원하는 결과물을 만들 수 있다. 올바른 DATE 포맷 사용하기 -> DATE_FORMAT() 함수 활용 SELECT b.TITLE, b.BOARD_ID, r.REPLY_ID, r.WRITER_ID, r.CONTENTS, DATE_FORMAT(r.CREATED_DATE, '%Y-%m-%d') AS CREATED_DATE FROM USED_GOODS_BOARD b INNER JOIN USED_GOODS_REPLY r ON b.BOARD_ID = r.BOARD_ID ..

[백준 9506] 약수 합 - 파이썬

백준 9506번 문제는 약수들의 합을 구해 완전수 (perfect number)인지 아닌지를 판별하는 문제입니다. 저는 다음과 같이 풀었습니다. while 문으로 exit (-1)전까지 입력을 받습니다. 1부터 n까지 for문을 돌면서, 나머지가 없는 즉, 모든 약수 (factor)를 리스트에 기록합니다. 약수의 합이 입력 값(n)과 같은지 확인하고 맞다면 형식에 맞춰 출력을 진행 if __name__ == '__main__': while True: n = int(input()) result = [] if n == -1: break else: for i in range(1, n): if n % i == 0: result.append(i) if n == sum(result): result = list(ma..

[백준 2563번] 색종이 - 파이썬

백준 2d array 부분 색종이 알고리즘에 대해 풀어보겠습니다. (https://www.acmicpc.net/problem/2563) 처음 이 문제를 접했을 때 들었던 생각은 각 색종이 area를 구하여 더함 교집합 영역을 구함 하나의 교집합 영역만 전체 area에 남겨두고, 나머지는 뺌 그런데 이렇게 처리하면 예외 케이스가 많이 생겨 너무 복잡도가 증가한다는 단점이 있었습니다. 단순하게 생각해보면, A라는 100 x 100 매트릭스가 있다고 가정했을때, 겹치든 겹치지지 않든, 색종이가 영역을 덮고 있다면 A[i][j] 의 값을 1로 설정하고 그렇지 않다면 0으로 설정하면 불필요한 예외 처리 없이 문제를 해결 할 수 있습니다. 정답 코드는 다음과 같습니다. if __name__ == '__main__..