Hello Ocean! 🌼

[문제] 삼각형 모양으로 배치된 수들이 있다. 이 수들에 대해서 위에서부터 아래로 내려오는 경로를 만드려고 한다. 아래 줄로 내려갈 때 마다, 바로 아랫칸이나 한칸 오른쪽 아래칸으로 내려갈 수 있다. 지나온 경로상의 모든 수의 합의 최댓값을 구해라. [Input] C (testcase 수) 각 testcase마다 n (층의 개수) n줄에 걸쳐 삼각형 각 가로줄에 있는 숫자 입력 [Output] 각 testcase마다 최대 경로 숫자의 합 [풀이] 알고리즘은 위와 같다. dynamic programming을 사용하면, 모든 경로를 하나씩 살펴보지 않고, 바로 위에 칸과의 경우의수만 계산해주면 되기 때문에 복잡도를 크게 줄일 수 있다. 이 알고리즘의 복잡도는 O(n^2)이다. 좀 더 큰 input의 예시를 ..

[문제] 기호 1번으로 출마한 다솜이는 선거 전에 후보별 득표수를 미리 알 수 있다. 다솜이는 득표수를 미리 알아낸 후, 다른 후보를 찍는 사람들을 돈으로 매수해서 자신이 당선되게 하려고 한다. 다솜이가 매수해야 할 사람의 최솟값을 구해라. [Input] N(후보의 수) 둘째 줄 부터 각 후보의 득표수가 N줄에 걸쳐서 입력된다. [Output] 매수해야 할 사람의 최솟값 [풀이] 완전탐색 우선 가장 기본적인 방법으로 접근해보자. 전체 후보의 득표수가 votesNum[] 안에 순차적으로 저장되어 있다고 하자. 후보가 3명이고 각 후보의 예상 득표수가 5,7,7이었다고 하자. voteNum[]에서 max 위치를 구하고, 다솜이(기호 1번)가 최댓값이 아닐 경우 해당 max 위치에서 1을 빼고, 그 표를 다솜..

1. memset() - 알고리즘 문제 해결 전략 책에서 이 방법을 사용하였다. memset(arr,value,size) 와 같이 사용한다. 이 방법은 vs에서는 헤더파일 없이 잘 실행되지만, 백준에 제출할 때 추가적으로 memory.h를 include해줘야 하는 번거로움이 있다. 2. fill(), fill_n() - memset대신 사용할 수 있다고 친구가 알려줬다. https://namwhis.tistory.com/entry/C-%EB%B0%B0%EC%97%B4-%EC%B4%88%EA%B8%B0%ED%99%94-stdfill-stdfilln-%EC%A0%95%EB%A6%AC C++ 배열 초기화 std::fill, std::fill_n .. 정리 BAEKJOON ONLINE JUDGE를 시작하게 된 ..

[문제] 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. [풀이] 첫 번째. 문제 갈래에도 DP가 명시되어 있기 때문..

[문제] 회전하는 벨트 위에 위와 같이 초밥들이 있다. 벨트 위에는 같은 종류의 초밥이 여러개 있을 수 있다. 손님은 초밥을 골라서 먹을 것이다. 1. 연속으로 k접시를 먹을 경우, 할인된 가격을 지불한다. 2. 각 고객에게 초밥 종류 중 하나가 쓰여진 쿠폰을 발행하고, 손님이 1번 행사에 참가할 경우 해당 초밥 1접시를 무료로 제공한다. 벨트 위에 해당 초밥이 없을 경우 새로 만들어 제공한다. 손님은 위의 행사에 참여하여 최대한 다양한 종류의 초밥을 먹으려고 한다. [input] 벨트에 놓인 접시의 수 N ( 2 ≤ N ≤ 30000 ) 초밥의 가짓수 d ( 2 ≤ d ≤ 3000 ) 연속해서 먹는 접시의 수 k ( 2 ≤ k ≤ 3000 (k ≤ N) ) 쿠폰번호 c ( 1 ≤ c ≤ d ) N d ..

지금까지 python으로 알고리즘 공부를 해왔다. python은 복잡한 문법이 없고, C에 비해 입출력, 배열다루기에 편해서 만족스럽게 사용하고 있었다. 하지만 어려운 문제를 풀게 되면서 python으로 풀게되면 시간초과가 일어나는 상황을 겪게 되었다. 앞으로 더 어려운 문제를 풀게 되었을 때도 같은 상황이 반복될 것 같아서 C++로 갈아타기로 했다. visual studio code를 사용하려고 했으나, C++을 사용하는게 꽤나 복잡해 보여서, 무겁긴 하지만 따로 설정이 필요 없는 visual studio를 사용하기로 했다. C만 배우고, C++은 제대로 배워본 적이 없어서, C++만의 문법을 익히려면 꽤나 시간이 걸릴 것 같다.