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/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를 통..
