문제 링크 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/30/lessons/87946# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 경우, 언듯 보면 dp로 풀고 싶지만, 'ungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.' 에 주목해야한다. 이 말은, 곧 N=8이기에, 몇중 포문을 돌던, 몇번 반복하던, 답만 구하면 되고, 시간초과는 '절대' 발생하지 않는다. 그렇기에, dp를 찾을 생각을 배제하고, 모든 가능성을 dfs로 완전탐색했다. 매번 여태 찾은 개수, hp(남은 피로도)를 인..
https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 처음 단순히 생각하면 1명 처리 -> 처리 시간 입력, ...... n명 처리 -> 처리 시간 입력으로 입국 심사 횟수 N을 기준으로 O(N) 짜리 풀이를 생각했다. 하지만 이럴 경우, 10억회의 연산 발생으로 시간초과가 난다. (이 오답 풀이는 맨 아래에 첨부하겠다.) 따라서 O(N) 보다 빠른 풀이, 혹은 심사위원의 수 ( 10만 ) 으로 문제를 굴려야 하는..
