본문 바로가기

Algorithm/Programmers93

[2020 카카오 인턴십] 키패드 누르기 문제: https://programmers.co.kr/learn/courses/30/lessons/67256 시뮬레이션 문제입니다. 핸드폰 자판을 어떻게 좌표화가 하는 지가 중요한 문제였네요. 1, 4, 7의 경우는 왼손이 처리하도록 3, 6, 9의 경우는 오른손이 처리하도록 그 외의 경우에는 오른손과 왼손의 거리, 왼손잡이인지, 오른손잡이인지 따진 후 L,R을 찍어주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/kakao2020_01.cc 2020. 7. 25.
[코딩테스트 연습] 징검다리 문제: https://programmers.co.kr/learn/courses/30/lessons/43236 이분 탐색 문제입니다. 10억에 해당하는 distance를 선형 탐색하면 O(10억)으로 시간초과가 납니다. 그러므로 5만에 해당하는 바위 갯수를 이용해서 문제를 해결해야 합니다. 아이디어는 다음과 같습니다. 1. 임의의 바위 간의 거리를 정합니다. (mid) 2. 이 바위 거리를 정답으로 할 때 n개 이하의 돌을 제거할 수 있는 지 세봅니다. 3-1. 2번이 가능하다면 바위 거리를 정답후보로 저장하고, 바위 간의 거리를 증가 시켜봅니다. 3-2. 2번이 불가능하다면 바위 간의 거리를 줄여봅니다. 이런 식으로 이분 탐색을 하면 됩니다. 단, 2번에서 n개 '이하'의 돌에 적용할 수 있는 것은 예를.. 2020. 7. 24.
[코딩테스트 연습] 올바른 괄호의 갯수 문제: https://programmers.co.kr/learn/courses/30/lessons/12929?language=cpp 재귀문제입니다. 올바른 괄호의 조건은 크게 두 가지 입니다. 1. ( ) 쌍의 갯수가 맞아야 한다. 2. '(' 괄호가 ')' 보다 먼저 나와야 합니다. 즉, 사용할 '(' 괄호가 없을 때 ')' 괄호가 나오면 안된다는 뜻입니다. 괄호를 만드는 재귀함수는 2가지 케이스로 뻗어나갑니다. case1. 현재 깊이에서 + '(' 괄호 더하기 case2. 현재 깊이에서 + ')' 괄호 더하기 재귀함수이므로 기저 사례를 잘 적용해주고, 조건에 맞을 때만 호출할 수 있도록 함수를 작성하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/mast.. 2020. 7. 24.
[코딩테스트 연습] 2 x n 타일링 문제: https://programmers.co.kr/learn/courses/30/lessons/12900 DP 문제입니다. DP[N]: 2 x N개의 타일칸에 놓을 수 있는 방법으로 가정하겠습니다. 기저 사례부터 생각해보면, DP[1] = 1, 세로로만 놓을 수 있으므로 1 입니다. DP[2] = 2, 세로로 두 개, 가로로 두 개 놓을 수 있으므로 2입니다. 위 두 개가 기저 사례이고, N > 2 부터는 DP[N]에 대해 다음과 같은 성질이 성립합니다. 1. DP[N-1] 방법의 갯수 + 세로로 한 개 놓으면 DP[N]이 됩니다. 2. DP[N-2] 방법의 갯수 + 가로로 두 개 놓으면 DP[N]이 됩니다. 위 1, 2번 방법을 모두 더한 게 DP[N]의 가짓 수가 됩니다. 그러므로 DP[N] = .. 2020. 7. 22.

티스토리툴바