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/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 핵심 아이디어는 "사전 순" "맨하튼 거리" 이다. 맨허튼 거리란? 좌표계에서 (x1,y1) 에서 (x2,y2)로 이동할때, 최단거리는 무조건 |x1-x2| + |y1-y2|라는 내용이다. 이 문제는, "장애물" 과 같은 상황이 없다. 따라서 최단거리를 별도의 알고리즘으로 찾을 필요가 없이, 맨허튼 거리로 찾으면 된다. 사전순이란 결국, 앞에 있는 문자가 사전순으로 높다면, 뒤에서 아무리..
https://school.programmers.co.kr/learn/courses/30/lessons/150367# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 제대로 읽어봐야하는 문제이다. 이 문제는 결국에 '0'으로 표현되는 '더미 노드' 아래의 모든 자식 노드 역시 '더미 노드' 라면 표현 가능한 수인 것이다. 주어진 수를 이진수로 변환하고, root 부터 시작해서 자신의 양쪽 자식이 더미노드( 0 )인지 체크하고, 만약 '0'이라면 해당 자식 노드 하위의 모든 노드가 '0' 인지 체크하면 된다. 보통의 이진트리는 아래와 같이 표현된다. ..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한 사항에서 이모티콘은 최대 8개, 할인의 종류는 4개이다. 8개 이모티콘에 대한 모든 할인의 경우의 수는 4*4*....*4 = 4^8 만큼의 경우의 수를 구하면 된다. 이 4개의 할인 경우의 수를 0,1,2,3 이라는 캐릭터에 담아서, 8자리 문자열에 저장하는 것으로 경우의 수를 표현했다. ex) 01010101 -> 1째 == 10%,2째 == 20%,....8째 == 20% dfs를 통..
문제 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)] 하지만, 주..
https://school.programmers.co.kr/learn/courses/30/lessons/67259# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이요약: 다익스트라, 구조체 코드 #include #include #include #include using namespace std; int dw[4]={1,-1,0,0}; int dh[4]={0,0,1,-1}; int dist[1000][1000][2]; int INF = 98765432; struct edge { int cost; int w; int h; bool vertical; //우..
https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 효율성 테스트가 존재하고, 투포인트로 풀어야 시간초과가 발생하지 않는다. 우선, 투포인트를 사용하지 않아 틀린 풀이를 확인해보자. 오답 풀이(시간 초과) #include #include #include #include #include using namespace std; map ma; pair getLen(){ int min=987654321,max=-987654321; for(aut..
https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 처음 단순히 생각하면 1명 처리 -> 처리 시간 입력, ...... n명 처리 -> 처리 시간 입력으로 입국 심사 횟수 N을 기준으로 O(N) 짜리 풀이를 생각했다. 하지만 이럴 경우, 10억회의 연산 발생으로 시간초과가 난다. (이 오답 풀이는 맨 아래에 첨부하겠다.) 따라서 O(N) 보다 빠른 풀이, 혹은 심사위원의 수 ( 10만 ) 으로 문제를 굴려야 하는..
