본문 바로가기

PS99

[Algorithm] 이중 포문 조정 - 구간합 개요 시간복잡도 줄이는 법을 학습하면서 해본 정리 코드트리를 참고하였다! 어떤 배열에서 특정 합을 만족하며 가장 크기가 큰 구간의 크기를 찾기 위해 완전탐색을 하면 다음과 같다. 완전탐색 - O(N**3) # 이 배열에서 특정 구간을 골라서, # 합이 10이 넘지 않아야 하고, # 배열의 크기가 가장 커야 한다. 이때의 배열 크기는? arr = [0,6,3,2,4,9,1] n = len(arr) target=10 # 무식하게 구해보기 for i in range(1, n+1): for j in range(i, n+1): total = 0 for k in range(i, j+1): total += arr[k] if total target : break ans = max(ans, j-i+1) *이 경우, j는.. 2024. 4. 17.
[백준/1063] 킹 | 구현 실수 방지를 위한 경우의 수 체크하기 킹 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 알고리즘 킹이 움직인다. 이때 체크해야할 조건은 다음과 같다. 격자 안에서만 움직여야 한다. 돌이 있는 곳으로 움직일 경우, 돌과 함께 움직여야 한다. 이때 돌 또한 격자 안에서 움직여야 한다. 돌이 격자 밖으로 나가는 경우도 체크하되, 이때 킹이 격자 내에서 움직인다면 상관없이 움직인다 이를 코드로 나타내면 다음과 같다. # 격자 내에서 해결해야한다. if (0 2024. 3. 31.
[백준/5671] 호텔 방 번호 | 중복값 개수 세기(딕셔너리와 SET) 5671 호텔 방 번호 5671번: 호텔 방 번호 선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004호와 같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지 www.acmicpc.net 알고리즘 범위에 해당하는 숫자들이 자릿수마다의 중복되는지 체크하면 된다. 같은 값이 있는지 확인하는 방법으로는 딕셔너리를 떠올렸고 아래와 같이 중복 체크를 해주었다. for item in hotel: d={'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0} flag=True for s in str(item): if s in d.keys(): d[s] += 1 f.. 2024. 3. 17.
[백준/1068] 트리 1068 트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 알고리즘 1. 이 문제는 부모가 인덱스, 해당 인덱스의 자식을 리스트로 부여한다. # index: 부모, 값: 자식 # 노드의 범위가 0 ~ n-1인 경우 for i in range(n): # root인 경우 if tree[i] == -1 : continue else: graph[tree[i]].append(i) 이렇게 표현하는 이유는 DFS 탐색 구현을 좀 더 직관적으로 평소와 같이 할 수 있기 때문이다. 예컨대 dfs(i)로 시작해서 자식.. 2024. 3. 6.
[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS 바이러스 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력에서 직접 연결되어 있는 쌍이 주어진다. 더보기 1 2 2 3 1 5 5 2 5 6 4 7 1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다. 이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다. 양방향 그래프를 2차원 리스트로 정의 graph = [[] for _ in range(n+1)] for _ in range(m): x,y=map(int, input().split()) graph[x].append(y) graph[y]... 2024. 3. 5.
[백준/22232] 가희와 파일 탐색기 가희와 파일 탐색기 22232번: 가희와 파일 탐색기 첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다. 2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열 www.acmicpc.net 알고리즘 정렬이 순서대로 이어져야 하므로 lambda를 활용하였다. 또한, 2 번째 조건은 까다로워서 정렬함수 말고 직접 교체해주었다. 전체 코드 import sys;input=sys.stdin.readline n,m=map(int, input().split()) jo_test = [input().rstrip() for _ in range(n)] ext = set(input().rstrip() for .. 2024. 2. 28.
[프로그래머스] 자동차기록에서 장기/단기 대여 구분하기 | DATEDIFF, SQL IF문 개요 이 문제의 핵심은 대여 시작일이 2022년 9월이어야 한다. ➡️ date_format 함수로 DATE형 원하는 형식으로 수정하기 장기/단기 기간은 30일이 기준이다. ➡️ datediff 함수와 if문 이용하기 DATEDIFF 날짜의 차이를 일(day)로 환산해주는 함수. datediff(date1, date2) 계산은 date1 - date2로 진행된다. 음수는 0으로 도출된다. IF문 if문은 SELECT와 WHERE 절에 사용할 수 있다. IF문 if(조건, 참일 때 결과, 거짓일 때 결과) if(datediff(end_date,start_date) 2024. 2. 23.
[프로그래머스] 자동차 종류 별 특정 옵션이 포함된 자동차 수 구하기 | LIKE 사용법 개요 SQL의 LIKE문은 주로 쿼리문 WHERE와 함께 사용되며, 일치하는 컬럼을 찾을 때 사용한다. 해당 문제처럼, 컬럼에 다양한 정보가 있을 때 '통풍시트', '열선시트', '가죽시트' 등 특정 내용을 걸러내야 하는 경우에 사용하기 좋다. LIKE 사용법 -- A로 시작하는 문자 찾기 -- where 컬럼명 like 'A%' -- A로 끝나는 문자 찾기 -- where 컬럼명 like '%A' -- A를 포함하는 문자 찾기 -- where 컬럼명 like '%A%' -- A로 시작하는 두 글자의 문자 찾기 -- where 컬럼명 like 'A_' -- 첫 번째 문자가 'A'가 아닌 모든 문자열 찾기 -- where 컬럼명 like '[^A]' -- 첫 번째 문자가 'A' or 'B' or 'C'인 .. 2024. 2. 11.
[백준/1107] 리모컨 리모컨 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 이 문제는 세 가지 함정이 있다ㅠㅠ 해당 블로그에서 잘 짚어주셨고, 이를 참고하여 문제해결에 반영하였다. 시작값(100)에서 +, - 버튼 조작으로 타겟 채널로 이동 vs 숫자 버튼을 통해 타겟 채널로 이동 고장난 버튼이 없을 때, 입력을 받지 않음 차이의 최솟값을 구하는 게 최선이 아닐 수 있음 알고리즘 1. 시작값(100)에서 타겟값까지의 차이 해당 문제의 예시에도 잘 나와있듯이, N = 100인 상황일 때는 당연히 리모컨을 조작하지 않아도 된다. 2. 고장난 버튼이 없을 때 입력을 받지 않음 m의 범위는 0 ~ 10이므로, .. 2024. 2. 11.
[프로그래머스] 131530. 가격대 별 상품 개수 구하기 문제 PRODUCT 테이블에서 만원 단위의 가격대 별로 상품 개수를 출력하는 SQL 문을 작성해주세요. 이때 컬럼명은 각각 컬럼명은 PRICE_GROUP, PRODUCTS로 지정해주시고 가격대 정보는 각 구간의 최소금액(10,000원 이상 ~ 20,000 미만인 구간인 경우 10,000)으로 표시해주세요. 결과는 가격대를 기준으로 오름차순 정렬해주세요. group by기본 문제다. 문제를 잘 보면 만원 단위의 가격대 별로 상품 개수를 출력해야 한다. 상품 개수는 예시에 잘 나와있듯이 product_id를 집계 함수로 잘 세어주면 된다. 만원 단위의 가격대 별로 조작하기 위해서는, 현재 DB에 저장된 price 값을 조정하고, GROUP BY해야한다. SQL Integer 조작 14000, 23000 이런.. 2024. 2. 10.
[백준/7576] 토마토 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 알고리즘 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다. 시작점을 미리 queue에 넣어서 방문할 수 있도록 한다. 1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다. 이 부분을 print로 찍어보면 다음과 같이 나온다. 일단 queue에 익은 토마토(1)의 위치를 모두 append 해.. 2024. 2. 4.
[프로그래머스] 조건에 부합하는 중고거래 댓글 조회하기 문제 USED_GOODS_BOARD와 USED_GOODS_REPLY 테이블에서 2022년 10월에 작성된 게시글 제목, 게시글 ID, 댓글 ID, 댓글 작성자 ID, 댓글 내용, 댓글 작성일을 조회하는 SQL문을 작성해주세요. 결과는 댓글 작성일을 기준으로 오름차순 정렬해주시고, 댓글 작성일이 같다면 게시글 제목을 기준으로 오름차순 정렬해주세요. sql 문제를 풀 때는 원하는 결과값이 어떤 것인지?에 대해 먼저 파악해야 한다. 그리고 이 결과를 도출하기 위한 세부적인 연산에 대해 고민한다. 먼저, BOARD 테이블은 게시글에 대한 정보를 담고 있고, REPLY 테이블은 그 게시물의 첨부파일 정보를 담고 있다.(쉽게 생각해서 댓글이다. REPLY 테이블의 필드값을 통해 유추할 수 있다.) 이러한 정보를 보.. 2024. 2. 3.

티스토리툴바