알고리즘5 [C++, Hash] 프로그래머스 전화번호 목록 문제 풀이 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 | 프로그래머스 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 r programmers.co.kr 풀이 코딩테스트에서 해시관련 문제가 좀 약한 느낌이 들어서.. 2019. 12. 10. [C++,DP] 백준 2294번 동전2 문제풀이 문제링크 백준 2294번 동전2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net DP문제를 하나 더 풀어보았다. 어려운 듯하면서 쉬운 듯 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include #include #include using namespace std; int main(){ int N,K; cin.. 2019. 3. 8. [C++,DP] 백준 9465번 스티커 문제풀이 문제 링크 백준 9465번 스티커 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net "1로 만들기"와 같은 유형의 DP 문제이다. 처음에 in-place로 알고리즘을 짜려다 꼬여서 자꾸 오답이 나오길래 각설하고 그냥 따로 배열을 하나 더 만들어서 짜서 A.. 2019. 3. 4. [C++,DP] 백준 1463번 1로 만들기 문제풀이, DP와 분할정복의 특징 문제링크 백준 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다시 복습하는 DP문제이다. 다시 DP 개념부터 집고 넘어가야겠다. DP(Dynanic Programing)란? 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 방법을 말하며 여기서 DP의 Dynanic은 개발자가 아무 의미없이 붙인 거라고 한다... 큰 문제를 해결하기 쉽게 여러 개의 쉬운 부분 문제들을 풀어 해결하는 방법 정도로만 이해하면 될 것 같다. 분할정복이랑 비슷한 개념이기는 하나 분할정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션.. 2019. 2. 26. [C++] 백준 2309번 일곱난장이 문제풀이 문제 링크 백준 2309번 일곱난장이 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net DP관련 문제인 줄 알았더니 알고보니 짐승공격 문제였다. ㅎㅎㅎ 항상 9개가 입력되고 7개의 답안이 출력된다는 점에 착안해서 9개 중에 골라낼 가짓수 2개를 모두 하나하나 대입하여 제외하고 나머지 7개의 합이 100이 되는지 판단하는 문제이다. vector와 sort함수를 이용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 .. 2019. 2. 14. 이전 1 다음
