목록Algorithm (30)

소근소근

[백준 BOJ 25097 Controlled Inflation gold2] C++, 그리디, Dynamic Programming

최근에는 백준이나 프로그래머스에서 푼 문제를 깃헙에만 업로드(백준허브 익스텐션 편하다...)하고, 간단히 문제풀이나 고민했던 것들을 깃헙 리드미에만 적었었다. 오랜만에 풀이를 적어보자고 결심했다 https://www.acmicpc.net/problem/25097 25097번: Controlled Inflation The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers, $N$ and $P$: the number of customers and the number of products each custom..
Algorithm 2023. 4. 12. 21:25
[백준 BOJ 14500 테트로미노 gold4] C++ DFS

- 총 5개의 테트로미노이고, 대칭과 회전을 포함하면 약 20개의 모양이 나온다. - 하나씩 다 구현할 수도 있지만, 경우의 수가 너무 많다... - 모든 점에서 dfs 를 depth 4 로 돌리는 방법으로 시작했다. - 하지만 dfs로 구할 경우, 아래 그림 처럼 5가지 중 4가지만 구할 수 있다. - ㅗ 이 모양에 대해서는 dfs로 구할 수 없다. - 그래서, 모든 점에 대해 dfs를 돌린 후, 나머지 도형 한개에 대해서만 구현을 해주는 것으로 풀었다. int N, M, ans; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,1,-1}; int score[501][501]; int visit[501][501]; bool chk_range(int x, int y) { if (..
Algorithm 2023. 3. 27. 00:03
[프로그래머스 - 무지의 먹방 라이브] Lv.4 c++

단순 구현은 쉬우나, 효율성 때문에 오래 걸린 문제. 무작정 k에 대해서 돌며 index를 구하면 터지게 되어 있음. k의 최대가 2*10^13 k초에 네트워크 에러가 나고, 그 뒤에 무엇을 먹어야 하는지 구해야 한다. 결국 간단하게는 `k+1 초에 몇 번 째 음식을 먹는지` 구하는 문제다. 위 그림처럼 표로 정리해보면, food_item[idx] 값 만 큼만 column 이 채워지는 것을 볼 수 있다. item의 모든 합보다 k+1 이 더 크다면, 이때는 먹을 음식이 이미 고갈 된 것이므로 -1을 리턴하는 것으로 먼저 전처리를 해주었다. while 문을 돌며 하나의 row씩 보면, 해당 row에 들어가는 k의 범위를 구하는 방식으로 접근했다. 일단 sorted에서 가장 작은 수 * len(food_it..
Algorithm 2023. 3. 26. 23:55
[프로그래머스] 경주로 건설

Lv3 . 프로그래머스 경주로 건설 (2020 카카오 인턴십) 문제 설명 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 그렇게 어려운..
Algorithm 2022. 5. 1. 21:01
[프로그래머스 - 오랜 기간 보호한 동물(2)] MYSQL , DATETIME , STRING

SELECT ID,NAME FROM (SELECT (O.DATETIME - I.DATETIME) AS PERIOD , I.ANIMAL_ID , I.NAME FROM ANIMAL_INS AS I, ANIMAL_OUTS AS O WHERE I.ANIMAL_ID = O.ANIMAL_ID ORDER BY PERIOD DESC) B(PERIOD,ID,NAME) LIMIT 2; 여기서는 두개의 테이블이 주어진다. ANIMAL_INS , ANIMAL_OUTS 는 각각 보호소에 들어온 동물 정보, 입양을 간 동물들의 정보가 담겨있다. 보호소에서 가장 오랜 기간 보호한 동물 2마리를 조회해야 한다. 두개의 테이블에서 같은 동물의 아이디는 같으므로 I.ANIMAL_ID = O.ANIMAL_ID 으로 JOIN 한 다음, D..
Algorithm 2022. 2. 6. 15:49
[프로그래머스 - 중성화 여부 파악하기] MYSQL, STRING DATE

SELECT * FROM ((SELECT ANIMAL_ID , NAME, 'O' FROM ANIMAL_INS WHERE SEX_UPON_INTAKE LIKE '%Spayed%' OR SEX_UPON_INTAKE LIKE '%Neutered%' )UNION (SELECT ANIMAL_ID , NAME, 'X' FROM ANIMAL_INS WHERE SEX_UPON_INTAKE LIKE '%Intact%' )) A(ANIMAL_ID , NAME, SEX_UPON) ORDER BY ANIMAL_ID UNION을 이용했다. 중성화 수술을 한 경우에는 SEX_UPON_INTAKE에 'Spayed' 나 'Neutered'가 포함된다. LIKE '%...%' 는 VALUE에 ...이 포함되는지를 확인한다. %는 여러..
Algorithm 2022. 2. 6. 15:41
[프로그래머스 - NULL 처리하기] MYSQL, IS NULL

NAME이 NULL이면 'No name'으로 , NULL이 아니라면 이름을 표시하는 문제이다. UNION을 사용해서 풀었다. SELECT ANIMAL_TYPE, NAME , SEX_UPON_INTAKE FROM ((SELECT ANIMAL_TYPE, NAME , SEX_UPON_INTAKE , ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NOT NULL) UNION (SELECT ANIMAL_TYPE, 'No name' , SEX_UPON_INTAKE , ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL)) A ORDER BY ANIMAL_ID 1. NULL인 경우는 SELECT에서 이름 대신 'No name' , 아닌 경우는 그대로 해서 두 개를..
Algorithm 2022. 2. 6. 15:36
[프로그래머스 - 입양 시각 구하기(2)] MYSQL , GROUP BY , DATETIME 추출

단순히 GROUP BY만 해서 출력한다고 생각해서 틀렸던 문제이다. 주어진 DB에서는 시간이 7~19 만 있는데 이 문제에서는 0~23까지 모두 출력해야 한다. 즉, COUNT가 0 이어도 출력해야 하는 것이었다. 계속 고민하다 모르겠어서 풀이를 검색해봤다. SET 으로 변수를 설정해서 증가시키면서 출력하면 되는 문제였다. SET 변수 설정은 몰랐어서 ㅎㅎ... SET @H := -1; SELECT @H := @H + 1 AS HOUR , (SELECT COUNT(*) FROM ANIMAL_OUTS WHERE HOUR(DATETIME) = @H ) AS COUNT FROM ANIMAL_OUTS WHERE @H < 23 SELECT 문에서 증가시켜주고, WHERE에서 종료 조건을 달아준다. 0~23까지 증..
Algorithm 2022. 2. 6. 15:29
이전 Prev 1 2 3 4 Next 다음