본문 바로가기

분류 전체보기

 (336)
백준 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에 ..
프로그래머스 - 등굣길(C++) 처음 봤을 때는 응? 이거완전 BFS인데... 라고 생각했으나 일단 (왜인지는 몰라도) 테케 정확도도 통과하지 못했다. 이후에는 문제 분류인 DP로 풀어나갔다. 그러나 얼추맞는 것 같은데 이상하게 통과가 안되서 알아보니 학교의 위치는 m,n 이었다 ! 이 때문에 테스트 케이스를 어느정도 통과했으나 아직 예외가 존재했고 예외를 찾는데는 얼마안걸렸지만 구현이 좀 걸렸다. 일단 풀이 방법은 다음과 같다. 1. x, y 에서 x가 0이거나 y가 0이면 모두 DP[x][y] 는 1이다. 최소로 갈 수 있는 값이 1개 밖에 없다. 2. DP[x][y] 는 현재 위치의 왼쪽과 위의 합이다. 왜냐면 집이 왼쪽 위에 있기 때문이다. 여기까지가 기본이다. 3. 1번에서 [0,1], [0,2] , [0,3] 중 0,2 가 ..
프로그래머스 - 징검다리 건너기(C++) 문제를 보고 든 생각은 이번에도 구현보다는 효율성 문제겠구나 싶었다. https://school.programmers.co.kr/learn/courses/30/lessons/64062 첫번째 생각 : 한 번씩 돌려보면서 -1 하고 돌이 0이되면 0의 갯수확인 -> 당연히 시간초과다. 돌의 최대가 2억이다. 두번째 생각 : 주어진 배열을 오름차순으로 정렬한다. 그리고 0번부터 n번까지 돌려보며 0의 갯수를 확인한다. 이때 첫번째와 달리 정렬된 0번부터 바로 stones를 0으로 정해서 숫자를샌다. 이러면 시간복잡도가 O(N^2) 이기때문에 정확도테스트에선 통과하지만 효율성 테스트를 한개도 통과할 수 없다. 세번째 생각 : 드디어 이분탐색이 떠올랐다. "어 설마.." 하면서 생각은 났지만 구체적으로 구현방법..
프로그래머스 - 단속카메라(C++) 탐욕법으로 분류된 문제이지만 사실상 그냥 구현이라고 봐야할 것 같다. 우선 항상 이런 문제를 보면 정렬을 떠올려야한다. 결과는 같지만 차가 들어오는 순서에 따라 연산이 달라지기 때문이다. 먼저 이 문제는 들어오는 첫번째 들어오는 시간을 기준으로 오름차 정렬하고 푸는게 가장 편하다. 1. i번 차의 나가는 지점을 기준으로 정해둔다. 2. i+1번 차가 들어오는 지점이 현재 기준점보다 오른쪽이다. 즉 기준 카메라로 커버할 수 없으면 카메라를 한개 추가하고 현 i+1번 차의 시작점으로 기준을 다시 잡는다. 3. i+1 번 차가 나가는 지점이 기준점보다 왼쪽이거나 같다. 즉 기준 카메라로 커버할 수 있다. 그럼 카메라의 위치를 i+1번이 나가는 지점으로 바꾼다. 왜냐하면 카메라로 많은 차를 커버해야하기 때문이다..

티스토리툴바