1일1알

스택 자료구조를 사용하여 해결할 수 있는 문제이다. 문제를 풀고 다른 사람들의 풀이법을 보니 많은 사람들이 스택을 쌓으면서 답을 구해서 문제를 해결하였다. 나의 풀이법은 스택을 전부 쌓은 뒤에 제거해나가면서 문제를 해결하는 방법이다. 스택을 쌓으면서 문제를 해결하는 방법이 훨씬 간단하고 효율적인 방법인 것 같다. 접근을 잘못해서 풀이가 복잡하고 푸는데 오랜 시간이 걸린 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; struct compare { bool operator()(..

연속으로 k개의 초밥을 먹고 쿠폰에 쓰여있는 초밥까지 먹었을 때 최대 몇 가지의 초밥을 먹을 수 있는지를 구하는 문제이다. 우선 마지막 초밥에서 처음 초밥으로 이어지기 때문에 초밥의 정보를 저장하는 배열에 처음부터 k-1개만큼 더한 배열을 만들었다 예제의 입력을 예로 들면 7 9 7 30 2 7 9 25 의 배열에 k-1 즉 3개를 처음부터 더한 배열 7 9 7 30 2 7 9 25 7 9 7 을 만들었다. 이렇게 하면 마지막 원소 25부터 4개를 먹었을 때 25 7 9 7로, 마지막에서 처음으로 돌아가는 것과 같다. 그리고 unordered_map을 로 만들고 k개만큼을 슬라이딩 윈도우 방식으로 탐색하면서 새로운 초밥이 들어오면 초밥을 추가하고, 원래 있던 초밥이 또 들어오면 해당 초밥의 개수를 증가시..

객체지향의 시작 절차지향 : 함수의 호출 순서대로 순차적으로 진행되는 프로그램, 유지보수가 어렵다는 단점이 있다. 객체지향 : 객체를 중심으로 진행되는 프로그램 class를 이용하여 객체를 만들 수 있다. class Knight //객체를 만들기 위한 틀 (붕어빵 틀) { public int hp; public void Move() { //move } } Knight myknight1 = new Knight(); //객체1 (붕어빵 1) Knight myknight2 = new Knight(); //객체2 (붕어빵 2) 만들어진 객체(붕어빵) 은 class (붕어빵 틀) 에 있는 속성들을 가지고 있다. myknight1.hp = 100; //100의 체력을 가진 기사 myknight2.hp = 150; ..

조금 특이한? dp 문제이다. 우선 점화식을 세울 때 생각한 것은 어떤 날이든 첫째 날과 둘째 날의 떡의 개수로 분해할 수 있다는 것이다. 예를 들어 5번째 날은 3번째 날 + 4번째 날이고, 3번째 날은 1번째 날 + 2번째 날, 4번째 날은 2번째 날 + 3번째 날.. 이런 식으로 밑으로 내려가면서 최종적으론 1번째 날과 2번째 날의 떡의 개수의 조합으로 나타낼 수 있다. 그림으로 나타내면 이런 식으로, 5번째 날은 최종적으로 2 * 1번째 날, 3* 2번째 날의 떡의 개수로 나타낼 수 있다. 하지만 숫자가 주어질 때마다 이런 식으로 계속 분해하면 시간이 오래 걸리기 때문에 bottom-up 방식으로 해결하기로 생각했다. pair을 이용하여 dp배열을 만들었는데, 첫 번째 원소는 첫 번째 날 떡의 개..

주어진 알파벳들을 오름차순으로 정렬하고 백트래킹을 이용하여 해결할 수 있는 문제이다. 오름차순으로 정렬된 알파벳들을 중복되지 않게 순서대로 탐색하였으며, 종료 조건은 정답을 저장하는 배열의 크기가 암호의 크기와 같을 때 종료하도록 설계하였다. 한 가지 주의해야할 점은 암호는 한 가지의 모음과 두 가지의 자음이 필수적으로 있어야 한다. 따라서 정답을 출력할 때 그것을 확인하고 출력을 해야 한다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int l, c; void BT(vector v, vector..

bfs탐색으로 풀 수 있는 문제인데 숫자 n이 1이 되기까지의 숫자들의 정보를 저장해야 하는 문제이다. 우선 최솟값은 bfs탐색을 하면서 쉽게 구할 수 있고, 자신의 이전 값을 저장하는 parent 배열을 만들었다. bfs탐색을 진행하면서 자신의 이전 값을 parent 배열에 저장하고, 숫자가 1이 되면 1부터 parent 배열을 통해 값이 n이 될 때까지 역추적? 하면서 값을 하나씩 저장한다. 저장된 정보를 역순으로 출력하면 n에서 1이 되는 과정의 숫자들이 출력된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long..