목록알고리즘/프로그래머스 (19)
개발자 김수진
[문제] programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr [풀이] 특별한 알고리즘을 사용해서 해결해야되는 문제일줄 알았는데 내가 가장 많이 다루었던 DFS 알고리즘을 사용해 해결하는 문제라는게 놀라웠다. 한..
[문제] programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr [풀이] Union-Find 알고리즘을 사용해서 풀었다. (Union-Find 알고리즘 : https://tnwlswkd.tistory.com/33 ) 고객이 원하는 방이 아직 배정받지 않은 방이라면 해당 고객에게 배정해주고 map에 다음 칸의 방으로 초기화한다. 이미 배정받은 방이라면 Find 함수를 통해 해당 방을 기준으로 다음 방에서 비어있는 방을 찾아 배정해준다. 또한 배열이 아닌 맵을 사용한 이유는 k의 범위가 1 이상 10^12 이하이므로 배열을 사용하면 10^12 크기의 배열을 선언하여 메모리 부족이 발생하게 된다. 항상 Union..
[문제] programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr [풀이] 반복문을 사용해 한 명씩 보내면서 구할 수 있다. 하지만 stones 배열의 길이가 200,000이므로 시간초과가 발생하여 효율성 부분에서 틀린다. 따라서 이분 탐색을 사용하여 찾아가는 방식으로 하였다. (이분탐색 정리 : https://tnwlswkd.tistory.com/112 ) stones 배열에서 left는 1, 가장 큰 값으로 right를 초기화 한다. 중간 값을 구해가면서 left, right 값을 조절하여 건널 수 있는 학생수의 최댓값을 찾는다. mid를 기..
[문제] programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr [풀이] 앞쪽에 위치한 원소일수록 집합에 가장 많이 포함되어 있어 따라서 원소가 나온 내림차순 횟수를 정렬하여 가장 많이 나타난 원소부터 answer에 insert [코드] #include #include #include #include using namespace std; bool cmp(pair a, pair b..
[문제] programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr [풀이] next_permutation 함수를 사용해 완전탐색으로 풀었다. 먼저 vector에 숫자와 연산자를 구분해서 담아줬다. 그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다. 우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식..
[문제] programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr [풀이] 1,4,7을 누를경우 왼손 3,6,9를 누를 경우 오른손 나머지는 현재 왼손, 오른손의 위치를 기준으로 가까운 손으로 누르도록 구현 만약 거리가 같다면 왼손잡이,오른손잡이인지 확인하고 이에 맞게 누르도록 [코드] #include #include us..
[문제] programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [풀이] 에라토스테네스의 체 , next_permutation, set를 모두 공부할 수 있는 문제 에라토스테네스의 체는 어떤 수가 소수인지 아닌지 판별할 때 사용된다. 1. 소수를 판별할 만큼 배열을 할당하고 배열을 자기 자신으로 초기화한다. 2. 2부터 자기 자신에 해당하는 것을 제외하고 배수들은 모두 0으로 바꿔서 소수에서 제외시킨다. #defin..
[문제] programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr [풀이] input으로 숫자 number와 number에서 제외할 숫자의 개수인 k가 주어진다. number에서 k개의 숫자를 제거하여 만들 수 있는 최댓 값을 구하면 된다. 처음에는 DFS를 사용하여 모든 경우에 대해 다 확인해봤는데 생각해보니 number의 길이가 1부터 1,000,000까지이다. 그래서 다른 방법을 생각해보니 number의 시작부터 큰 수를 골라 총 number.size()-k의 숫자를 골라서 answer로 return 하면 된다. 1. number의 처음부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다. 2..