문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 최대한 중복이 많이 발생하는 구간마다 카메라를 설치해나가면 된다. 시작 시간, 종료시간이 작은 순서로 정렬한 뒤, 현재 route와 다음 route 사이에 중복 구간이 존재하는지 확인한다. 만약 존재한다면, 현재 구간과 새롭게 편입한 route의 중복 구간을 구한 뒤, 다음 route를 통해 또다시 중복구간이 형성되는지 확인한다. 최대한 많은 자동차가 겹칠 수 있는 중복기간..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 dfs의 특성을 활용하여 사전순으로 완전 탐색을 진행할 수 있다. 따라서, 탐색 순서에 따라 진행하던 중, 찾고자하는 string이 나오면 해당 string의 순서를 리턴하면 된다. dfs를 통한 사전순 완전탐색으로 순서 계산 #include #include #include using namespace std; string words="AEIOU"; string ans_str..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 dp[a][b]를 시작점에서 (a,b) 지점까지 도달하는 경로의 가짓수라고 가정하자. 시작점에 1을 넣고(제자리에 있는 것 ==1개의 경로) dfs or bfs로 완전탐색을 수행한다. ( 이때, 아래 or 오른쪽으로만 이동하기에, 왔던 길을 되돌아올 일은 없다.) 만약 a,b라는 지점에서 두개의 분기점이 만난다면, (a-1,b) 와 (a,b-1) 지점이 만나게 된다. (아래 ..
https://school.programmers.co.kr/learn/courses/15008/lessons/121686# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 우선, 아무 생각 없이 우선순위, 실행 시간, 입력 들어온 순서, 실행 순서 가 낮은 순으로 우선순위 큐에 넣고 그대로 pop()해가며 답을 구하면 될 줄 알았지만, 이렇게는 해결할 수 없다.( 만약 첫 프로그램이 5초에 종료 되었는데, 가장 우선순위가 높은 프로그램이 8초에 시작한다고 5~8초에 아무도 실행하지 않는 반례가 발생한다.) 즉, 프로그램의 priority가 높고,..
문제 링크 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/157341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 쉬운 문제이지만, join 개념이 잡히지 않았다면 헷갈릴 수 있어 가지고 와봤다. 우선, CAR_RENTAL_COMPANY_RENTAL_HISTORY(이하 history) join CAR_RENTAL_COMPANY_CAR (이하 car) 테이블은 history 테이블이 car테이블의 PK를 FK로 가지고 있기에, 이를 가지고 join해야하기에 기본조건을 추가해야한다. 가끔 무의식 적으로 join..
https://school.programmers.co.kr/learn/courses/30/lessons/157339 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 적절 히 조건을 분기한 뒤, subquery를 통해 구했다. select ccdd.car_id , ccdd.car_type, truncate ( (ccdd.daily_fee*(100-ccdd.discount_rate)/100)*30,0 ) as fee from (select car_id,daily_fee, discount_rate,crcc.car_type # 할인 후에 50~200만 사이인 차 ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 이 문제를 처음 보고선, 단순하게 시작점부터 각 노드간의 최단 거리를 모두 찾고, 그 중 가장 긴 거리의 수를 고르려고 했다. 이 방법엔 2가지 솔루션이 있다. 1) 시작점에서 각 노드간의 거리를 다익스트라로 구하기: [ V*O(V^2) == O(V^3) ] 2) 플로이드 와샬로 각 정점들간의 최단 거리 모두 구한 뒤, 시작점에서 각노드간 최단거리만 사용하기 [O(V^3)] 하지만, 주..
