Doby's Lab

https://school.programmers.co.kr/learn/courses/30/lessons/131704 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Level: 2 Solved By: Stack, Implementation 오랜만에 프로그래머스 문제를 풀었습니다. 2~3문제 정도 푸니 순위가 80,000 정도 확 오르네요.. 무엇보다 프로그래머스는 항상 느끼지만 독해력과 구현력을 집중적으로 요구하는 듯합니다. order가 주어지면 이 배열을 우선 다른 배열로 바꾸어주었습니다. order가 index:순서, value:위치를 나타냈다면 이해하..

https://www.acmicpc.net/problem/6591 6591번: 이항 쇼다운 각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 231보다 작은 경우만 입력으로 주어진다. www.acmicpc.net Level: Silver III Solved By: Math 4번의 솔루션에 풀 수 있었습니다. 1) nCr = n-1Cr + n-1Cr-1의 특성을 활용하여 Top-Down DP로 풀려했지만 메모리 초과로 실패했습니다. 2) 10!이 INT_MAX보다 작은 것을 고려하여 10까지의 factorial을 구해놓고 f[n]/(f[n-k]*f[k])로 풀려했지만 OutOfBound로 실패했습니다. 3) n!/(r!*(n-r)!)이 (n*(n-1)*...*(n-r+1))/r!임을 알고, [1]..

https://www.acmicpc.net/problem/1146 1146번: 지그재그 서기 첫째 줄에 총 경우의 수를 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Level: Platinum V Solved By: DP, Math 해당 포스트(https://jeongboclass.tistory.com/57)의 풀이를 참고하였습니다. 이 문제는 보면 Brute-Force 하게 풀기에는 N의 Max가 100이라 불가능합니다. 그래서 어떠한 패턴이 있는 건지 찾아보려 했지만 알 수는 없었습니다. DP로 풀어야 할 거 같은데 감은 오지 않고, 풀이를 참고해야 했습니다. 풀이의 생각과 저의 생각의 가장 큰 차이점은 '어떤 수인지 신경을 쓰냐 안 쓰냐'의 문제였습니다. 저는 순열을 ..

https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net Solved By: Combinatorics, Math, DP 소문제가 2개라 유사한 문제 2개를 푸는 것 같았습니다. naive 하게 백트래킹으로 모든 순열을 구하기에는 O(N!)으로 시간 초과가 납니다. 그렇기 때문에 다음과 같은 특징을 찾아야 합니다. N = 4인 순열에서 3번째 순열을 찾으라고 하면 첫 순열이 {1, X, X, X}로 시작하는 것을 알고, 나머..

https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net Solved By: Math 문제를 해석하면 주어진 수가 몇 개의 2의 제곱수로 이루어져 있는지 묻는 문제였습니다. 이진수에 의하면 모든 수는 이진수로 표현 가능하기 때문에 이런 특성을 활용하여 아이디어를 떠올릴 수 있었습니다. #include using namespace std; int main(){ int n; cin >> n; int two = 64; int ans = 0; while(t..

https://www.acmicpc.net/problem/1213

https://www.acmicpc.net/problem/14401 14401번: 악덕 나라 남규 나라의 왕 zych는 도로 정비 계획을 만들고 있다. 남규나라의 도시는 2차원 평면에 존재하며, 각 도시는 (xi,yi)에 위치한다. 새롭게 고속도로를 만들어 모든 도시를 고속도로를 통하여 다른 www.acmicpc.net Solved By: Kruskal, CCW 좌표값이 존재하여 좌표 간의 거리를 구한 후, 최댓값을 구하기 때문에 Edge의 비용을 음수 값으로 바꾸어주고, 이미 있는 고속도로라면 두 노드를 union 하여 거리를 구한 Edge들을 Kruskal 돌리면 되는 간단한 문제일 줄 알았습니다. 하지만, 문제에서 "고속도로 하나하나는 다른 도시들을 거치지 않아야 하며"라는 조건이 있기 때문에 이를..

https://www.acmicpc.net/problem/1143 1143번: 경찰 첫째 줄에 마을의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 마을부터 경찰서를 설치하는데 드는 비용이 주어진다. 이 값은 1000보다 작거나 같은 자연수이다. 셋째 www.acmicpc.net Solved By: SCC 몇 달 전 이 문제를 시도했을 때와 이번에 시도했을 때 막혔던 부분의 코드를 비교해보니 똑같더군요. 하지만, 이번엔 관점을 좀 다르게 잡았습니다. SCC 코드에 문제가 있는 게 아닐까 싶어 코드를 뜯어보던 반면 이번엔 이전부터 같은 SCC 코드를 사용하는데 뭐가 문제겠냐 싶어서 평균값에 초점을 두었습니다. 이 문제를 푸는 방법은 SCC를 통해 어느 한 SCC의 indeg..