반응형 Problem Solving155 백준 2515 : 전시장 https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net [ 문제풀이 ] 최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 이 문제 역시 이들을 기반으로 접근하였다. 먼저 그리디이다. 그리디는 매 순간의 선택이 최적해라는 것이 보장되어야 하는데 이는 성립하지 않는다는 것을 반례를 통해 쉽게 찾을 수 있다. 다음으로 파라메트릭 서치이다. 구하고자 하는 금액을 이분 탐색을 시도하면서 진행해야 하는데 현재 key값인 금액이.. 2021. 8. 17. 백준 1727 : 커플 만들기 https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net [ 문제풀이 ] 최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 처음에는 그리디로 접근하였는데 틀렸습니다가 나와서 DP로 해결하였다. 먼저 dp 테이블을 다음과 같이 정의하자. dp[i][j] : (1~i)까지의 남자와 (1~j)까지의 여자를 커플 매칭했을때 성격 차이 최소값 그렇다면 점화식은 어떻게 될까? 남자(i), 여자(j)의 수가 같다면 모두 커플이 이루어져야.. 2021. 8. 16. 백준 16988 : Baaaaaaaaaduk2 (Easy) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net [ 문제풀이 ] 전형적인 삼성 스타일의 문제로 바둑돌 2개를 둘 수 있는 모든 경우의 수에 대해서 죽일 수 있는 상대 돌의 개수를 찾아주면 되는 문제이다. 바둑돌 2개를 두는 방법은 백트래킹 기반의 조합으로 구해주면 된다. 상대 돌의 갯수를 찾는 방법은 2인 돌에서 시작하여 dfs를 통해 방문할 수 있는 모든 2인 돌을 탐색하면서 0(빈 공간)을 만나지 .. 2021. 8. 15. 백준 1275 : 커피숍2 https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net [ 문제풀이 ] 전형적인 세그먼트 트리를 이용해서 구간합을 구하는 문제이다. 세그먼트 자료구조를 공부하였다면 쉽게 해결할 수 있다. 세그먼트 트리 자료구조를 모르거나 공부하고 싶다면 아래 글을 참고하길 바란다. https://sorjfkrh5078.tistory.com/14?category=1007493 세그먼트 트리(Segment Tree) 이번에 배워볼 자료구조는.. 2021. 8. 14. 백준 1300 : K번째 수 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net [ 문제풀이 ] N이 최대 100000이기 때문에 모든 수를 구해서 정렬한다면 TLE가 발생할 것이다. 이를 현재 숫자가 key라고 할때, key 보다 작거나 같은 수가 k개 이상인지를 판단하는 결정 문제로 변환하여 파라메트릭 서치를 활용하면 해결할 수 있다. 이때 주의해야할 점은 구한 수가 key랑 같다고 끝내버리면 안 된다. 왜냐하면 현재 수인 key가 실제 존재.. 2021. 8. 12. [프로그래머스 SQL] 헤비 유저가 소유한 장소 https://programmers.co.kr/learn/courses/30/lessons/77487 코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr [ 문제풀이 ] GROUP BY 절과 HAVING 절을 활용할 수 있는지 묻는 문제이다. 이를 활용하여 헤비 유저의 HOST_ID를 추출한 후 기존의 테이블과 비교해 주면 된다. 비교는 IN 함수를 사용해 주면 된다. IN 함수는 다른 SELECT 문도 활용할 수 있다는 장점이 있다. SELECT ID, NAME.. 2021. 8. 11. [프로그래머스 SQL] DATETIME에서 DATE로 형 변환 https://programmers.co.kr/learn/courses/30/lessons/59414 코딩테스트 연습 - DATETIME에서 DATE로 형 변환 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [ 문제풀이 ] DATE_FORMAT 함수를 사용할 수 있으면 간단하게 해결할 수 있는 문제이다. SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME, '%Y-%m-%d') AS '날짜' //%m과 %M.. 2021. 8. 11. [프로그래머스 SQL] 오랜 기간 보호한 동물(2) https://programmers.co.kr/learn/courses/30/lessons/59411 코딩테스트 연습 - 오랜 기간 보호한 동물(2) ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [ 문제풀이 ] 두 테이블을 JOIN 하여 시간 차이가 큰 튜플을 2개 뽑아주면 되는 문제이다. SELECT I.ANIMAL_ID, I.NAME FROM ANIMAL_INS AS I JOIN ANIMAL_OUTS AS O ON I.ANIMAL.. 2021. 8. 11. [프로그래머스 SQL] 중성화 여부 https://programmers.co.kr/learn/courses/30/lessons/59409 코딩테스트 연습 - 중성화 여부 파악하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [ 문제풀이 ] 조건문을 통해 원하는 컬럼을 처리를 할 수 있는지 묻는 문제이다. 조건문에 자주 사용하는 방법은 IF 문과 CASE WHEN 문이다. 주의해야 할 점은 LIKE 함수는 OR 연산을 적용하지 않는다. 즉, IF 문에서 LIKE 함수를.. 2021. 8. 11. 이전 1 2 3 4 5 6 ··· 18 다음 반응형