본문 바로가기

분류 전체보기

 (403)
프로그래머스 - 야근지수(C++) https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 풀며 생각의 순서는 이러했다. 1. 내가 잘 하는 문제 유형으로 바꿀 수 있을까? dfs, bfs 등등 2. 아니라면 뭘로 바꿀 수 있을까. 이 문제는 우선 가장 최소화 시키는 것이 목적이다. 그리고 n이 백만으로 크다. 그렇다면 DP, 이분탐색, 파라메트릭을 사용할 수 있을까? 3. 모두 아닌 것 같은데 그렇다면 단순 구현인가? 4. 단순 구현이라 하면 어떤 자료구조를 사용할 수 있을..
백준 1477번 휴게소 세우기 (C++) 이번에 이분탐색을 열심히 풀어보고 있다. 이 문제는 언뜻보면 DP인가 싶기도 하다. 만약 이 문제를 이분 탐색이라는 키워드를 못보고 풀었다면 아마 이분탐색이라는 것을 알아차리기까지 오랜 시간이 걸렸을 것 같다. 풀이는 다음과 같다. 1. 먼저 새워져있는 휴게소들을 정렬한다. 2. 정렬된 휴게소들 간의 거리를 저장해둔다. 3. 이분탐색으로 lo = 0 hi = L 로 정한다. 4. 갱신조건은 휴게소 간의 거리를 mid로 나눈 값을 보는 것이다. 만약 mid로 나누어 떨어지면 휴게소가 100, 200에 새워져있다고 하자. 그런데 mid가 50이면 150 지점에 한개만 새우면 되는데 2개를 새울 것이다. 이 경우를 방지하기 위해 나누어 떨어질 경우는 휴게소를 한개 지워준다. 5. 만약 휴게소를 M만큼 지었거나..
이분 탐색의 이해 이분탐색은 간단하게 절반씩 줄여나가며 값을 찾는 방법이다. 논리는 중학생도 이해할 수 있는 간단한 로직이다. 그러나 문제를 풀다보면 lo < hi 인지 lo
백준 2512번 예산(C++) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 어려운 문제는 아니지만 파라메트릭의 입문용으로 괜찮은 문제라고 본다. 먼저 이 문제는 hi, lo를 설정하는 것이 간편하다 반드시 가장 큰 cost를 갖는 도시의 예산을 넘을 수 없다. 그러므로 hi 는 가장 큰 예산으로 low 는 0으로 잡고 이분탐색을 진행한다. 체킹같은 경우는 만약 지금 분배 예산이 도시의 예산을 넘는다면 도시의 예산을, 그렇지 않다면 분배 예산을 더하여 마지막 총 액수..
프로그래머스 - 네트워크(C++) https://school.programmers.co.kr/learn/courses/30/lessons/43162# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 봤을 땐 행렬을 그대로 두고 그래프 순회로 풀 수 있을 것 이라고 생각해서 백준의 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc..
백준 14699번 관악산 등산(C++) https://www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net DP 문제 분류를 못봤으면 풀지 못했을 것 같다.ㅠ 겉보기엔 그래프 탐색 문제로 보인다. 그러나 쉼터의 높이가 백만까지 가능하고 쉼터 수도 무려 5000개나 되기 때문에 이 문제를 일반 그래프 탐색으로 풀면 시간초과가 난다. 일반적인 그래프 탐색도 할 줄 알아야한다. 문제를 잘 파악하는 것이 중요하다. 먼저 중요 키 포인트는 더 높은 곳으로만 올라가야하는 것이다. 즉 가장 높이 있..
프로그래머스 - 최고의 집합(C++) https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 문제다. 코딩테스트 1번이 딱 이정도로 나오는 느낌. 다만 처음 읽으면 어떻게 해야할지 감이 안잡힐 수 있다. 먼저 최고의 집합이 되려면 N개의 숫자의 합이 S가 되어야한다. 즉 N개의 숫자들은 N이 3이라고하면 (N-2, 1, 1), (N-3, 1, 2) ... 이런식으로 매우 많다. 그리고 두번째 조건인 곱했을 때 최대가 되게 하려면 각 원소들간의 차이가 없어야한다. 즉 원소들은 (S ..
백준 12869번 뮤탈리스크(C++) https://www.acmicpc.net/problem/12869 대학 친구의 추천으로 풀어보았다. 처음에는 조합을 순서대로 DFS 넣어보았는데 시간초과가 났다. 그리고 고민하다가 문제 분류를 보니 생각지도 못했던 다이나믹 프로그래밍이 보였다. 그걸 보고도 " 엥, 이걸 어캐 DP로 저장하누,,?" 생각했고 부끄럽게도 검색을 통해 아이디어를 가져왔다. DP[a][b][c] 이런 형태로 저장하면 되었다. 즉 이 문제는 dfs + dp 문제이다. dfs dp는 어렵지만 잘만하면 문제를 깔끔하고 멋지게 풀 수 있다. dfs로 순회하면서 갱신은 dp로 체크하며 더 방문할지 말지 정하는 것이다. dfs + dp dfs + 백트래킹 은 매우 중요하다. 1. -9 -3 -1 순서대로 dfs 순회한다. 2. dp에 ..

티스토리툴바