문제 링크 https://school.programmers.co.kr/learn/courses/15008/lessons/121684 풀이 처음에는 완전탐색은 시간초과가 날 것 같아서 뭔가 로직을 써야하나? 생각하다 그냥 조합으로 가능성 전부 돌려서 찾았다. 조건만 정리하면 아래와 같다. - 각 종목마다 1명씩 대표를 뽑는다. - 한사람당 1개의 종목만 출전한다. 따라서, 전체 인원들 중, 각 종목(m개) 의 대표를 중복 없이 선택하면 된다. 단, 누가 어떤 종목을 채택하는지가 중요하기에 "순서 상관있이 선택하는 조합" 으로 생각하고 코드를 구현해도 된다. 따라서 comb라는 재귀함수를 통해 dfs 탐색으로 각 종목(depth)마다, 중복 없이 임의의 학생 1명씩을 선택하는 모든 가능성 중, 최솟값을 찾아..
https://school.programmers.co.kr/learn/courses/30/lessons/87946# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 경우, 언듯 보면 dp로 풀고 싶지만, 'ungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.' 에 주목해야한다. 이 말은, 곧 N=8이기에, 몇중 포문을 돌던, 몇번 반복하던, 답만 구하면 되고, 시간초과는 '절대' 발생하지 않는다. 그렇기에, dp를 찾을 생각을 배제하고, 모든 가능성을 dfs로 완전탐색했다. 매번 여태 찾은 개수, hp(남은 피로도)를 인..
해당 문제는 주사위 도면을 고정 시키고, 상,하,좌,우 이동시, 각 숫자가 어느 위치로 옮겨 지는지 하나하나 따져서 무식하게 풀었다. //original 2 4 1 3 5 6 //up 6 4 2 3 1 5 //down 1 4 5 3 6 2 //left 2 6 3 1 5 3 //right 2 1 3 6 5 4 포인트는 각 도면의 인덱스는 1,2,3,4,5,6 으로 그대로 고정되기에, 1번, 6번 인덱스 내의 값이 각각 바닥, 천장 값으로 고정되고, 각 움직임에 따라 실제 숫자 값만 바꿔주는 것이다. 정답 코드 #include using namespace std; // 2 //413 // 5 // 6 int arr[100][100]; int dice[7]; //1: 바닥, 6: 천장 int dx[4] = {..
이번 글에선, c++ 에서 순열과 조합을 재귀를 통해 구현하는 포맷에 대해 알려드리겠습니다. 혹시 next_permutation을 통한 풀이가 궁금하시다면, 아래 글을 참고해주세요. 순열과 조합 (C++) — 코딩이랑 이것저것 (tistory.com) 순열과 조합 (C++) [ n개의 숫자를 전부 사용해서 만들 수 있는 모든 순열의 갯수] ex) 1,2,2 가 input으로 들어오면 1,2,2 2,1,2 2,2,1 3가지가 나온다. 여기서 중요한 점은 "중복된 순열은 제거" 된다는 점이다. 1,2( 1th ) , 2( 2 codenme.tistory.com 1) 순열 nPm, 즉 n개의 값들 중, m개를 처럼 순서를 고려해서 선택한다. ex: (1,2) != (2,1) 입출력 예시 4 2 //4P2 12..
dfs로 전선 연결이 필요한 모든 프로세서 들이 전설을 이을 모든 경우의 수를 따져서 구했다. 여기서, 만약 해당 프로세서가 벽으로 도달하지 못하는 경우를 계산하여 백트래킹( 가지치기) 를 수행하였다. 추가로, 이 문제에선,'모두 연결 가능 할시의 최단 거리' 가 아니라, '최대한 많은 개수를 연결할 시 의 최단거리' 를 구해야한다. 따라서, dfs를 통해 해당 프로세서를 '상','하','좌','우' 로 연결하는 가능성에 더해, '해당 프로세서를 연결하지 않는 가능성' 도 체크해야한다. 예시 위와 같이 입력이 들어온 경우, 우리가 전선으로 연결해줘야하는, 파란 동그라미 표시를한 프로세서에 대해 전선의 연결 가능성을 확인해야한다. 하지만, 맨위의 파랑 원은, 다른 전선들이 연결되면, 필연적으로 벽에 닿을 ..
https://www.acmicpc.net/problem/18312 18312번: 시각 정수 N과 K가 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 모든 시각을 세는 프로그램을 작성하시오. 시각을 셀 때는 디지털 시계를 기준으로, www.acmicpc.net 문제 해답 #include using namespace std; #define hour 24 #define min 60 #define sec 60 int main() { int n, k; cin >> n >> k; long long total = 0; int answer = 0; long long end_time = (n + 1) * 60 * 60; for (int t = 0; t < en..
https://school.programmers.co.kr/learn/courses/30/lessons/157341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 쉬운 문제이지만, join 개념이 잡히지 않았다면 헷갈릴 수 있어 가지고 와봤다. 우선, CAR_RENTAL_COMPANY_RENTAL_HISTORY(이하 history) join CAR_RENTAL_COMPANY_CAR (이하 car) 테이블은 history 테이블이 car테이블의 PK를 FK로 가지고 있기에, 이를 가지고 join해야하기에 기본조건을 추가해야한다. 가끔 무의식 적으로 join..
1) SQL 쿼리 순서# 적는 순서SELECT - FROM - WHERE - GROUP BY - HAVING - ORDER BY - LIMIT# 실행 순서FROM - WHERE - GROUP BY - HAVING - SELECT - ORDER BY - LIMIT위와 같은 순서로 실행 되기에 select의 alias를 where 절에서 사용하는 등의 행동은 불가하다. (where이 select보다 먼저 수행된다.) 2) ININ(a,b,c): 어떠한 컬럼 값이 a,b,c 중 하나라면 select된다.SELECT CATEGORY,PRICE as MAX_PRICE,PRODUCT_NAMEFROM FOOD_PRODUCTWHERE (PRICE) IN (SELECT MAX(PRICE) FROM ..
