프로그래밍-기본기/알고리즘(문제풀이)

처음 이 문제를 보았을 땐 set만 이용해서 풀 수 있을거라 생각했다. set에 넣은 값이 있으면 count를 증가시킨 후 maxCount를 최종적으로 리턴하면 해당 3개의 케이스는 풀 수 있었다. #include class Solution { public: int lengthOfLongestSubstring(string s) { set sets; int count = 0; int maxCount = 1; if(s.size() == 0){ return 0; } for(int i = 0 ; i < s.size();i++){ if(sets.find(s[i]) != sets.end()){ maxCount = max(count, maxCount); count = 1; continue; } sets.insert(..

풀이. #include #include #include #include class Solution { public: string longestCommonPrefix(vector& strs) { string answer = ""; size_t shortest_length = strs[0].length(); // 첫 번째 문자열의 길이로 초기화 for (const auto& str : strs) { shortest_length = std::min(shortest_length, str.length()); } for(int i = 0 ; i < shortest_length; i++){ char firstStr = strs[0][i]; for(int j = 1 ; j < strs.size(); j++){ // s..

해당 문제는 연산자 오버로딩에 대한 개념만 있으면 쉽게 풀 수 있다. int N; vector v; void Intput() { cin >> N; for (int i = 0; i > x >> y; v.push_back({ x,y }); } } 입력은 x,y를 받아준다. 순서는 y 오름차순을 기준으로하고 y가 같다면 x값을 비교한 뒤 오름차순 한다. bool operatorVector (const pair& a, const pair& b) { if (a.second == b.second) { return a.first < b.first; } return a.second < b.second; } 정렬 조건으로 만들어줄 비교 함수 하나를 만들어주었다. void ..

해당 문제는 Stack으로 풀면 간단하다. 0이 들어올 때, pop을 해주면 된다. int N; stack s; void Intput() { cin >> N; for (int i = 0; i > data; if (data == 0) s.pop(); else s.push(data); } } 이후 스택에 쌓인 수 만큼 합산 해주고 출력해주면 된다 void Solution() { int sum = 0; while (!s.empty()) { sum += s.top(); s.pop(); } cout > N; for (int i = 0; i > data; if (data == 0) s.pop(); else s.push(..

해당 문제는 그리디 알고리즘 ( 탐욕법 )으로 풀 수 있다. 간단히 해당 알고리즘을 적용하여 풀이 법을 그림으로 살펴보자면 일단 N이 11이라고 가졍했을 때, 5로 먼저 뺄 수 있는지 확인 후 5로 뺄 수 있으면 빼준다. 이후 (11-5)가 다시 5로 먼저 뺄 수 있는지 확인하고 뺄 수 있다면, 또 빼준다. (11-5-5)가 다시 5로 먼저 뺄 수 있는지 살펴본다. 뺄 수 없으니 이제 3으로 뺄 수 있는지 살펴본다. 뺄 수 없으니, 다시 (11-5)로 돌아가서 3으로 뺄 수 있는지 살펴본다. 뺄 수 있으니 (11-5-3)이 5로 뺄 수 있는지 살펴본다. 뺄 수 없으니, 3으로 뺄 수 있는지 살펴본다. 뺄 수 있다. 해당 값이 0이면 위로 타고타고 올라가서, 얼마나 거쳤는지를 알려주면 된다. 코드로 구현해..

1 11 66 286 1001 3003 8008 19448 43758 92378 1 10 55 220 715 2002 5005 11440 24310 48620 1 9 45 165 495 1287 3003 6435 12870 24310 1 8 36 120 330 792 1716 3432 6435 11440 1 7 28 84 210 462 924 1716 3003 5005 1 6 21 56 126 252 462 792 1287 2002 1 5 15 35 70 126 210 330 495 715 1 4 10 20 35 56 84 120 165 220 1 3 6 10 15 21 28 36 45 55 1 2 3 4 5 6 7 8 9 10 문제를 표로 나타내보자면 위와 같다. 맨 아래를 0층에선 아파트에는 0층부터..

이번 문제는 여지껏 배웠던 C++ 지식을 최대한 활용하여 풀어봤다. 우선은, 기존 main에 다 때려박았던 걸 조금 분리 해볼 생각이었다. #pragma once #define interface struct __interface ISol { virtual void Solution() = 0; virtual void Intput() = 0; virtual void Solved() = 0; }; ISOl 인터페이스를 하나 만들어줬고 #pragma once #include "ISol.h" class Sol: public ISol { void Solution() override; void Intput() override; void Solved() override; }; 해당 ISOL 인터페이스를 상속 받도록 S..

해당 문제를 이해하기엔 내용이 잘 이해가 되지 않아 접근 방법을 보고 푼 문제이다. 일단 접근 방법에 대해선 그림으로 설명하고 풀이 과정에 대해 설명해보고자 한다. 예시 입력을 그림으로 표현해보았다. 우선 우린 저 배열에서 4가 나올 나올 때 까지 오름차순으로 저 주황색 막대기에 넣어줘야 한다. 4가 나올 때 까지, Push만을 반복하다가. 4가 나오면 PoP을 해준 뒤 다음 배열에 있는 것을 바라본다. 곧바로 POP을 해주면된다. 이 때, 6을 바라보아야 하는데, 이 때 3과 4는 사용했고 5,6만 들어갈 수 있다. 대충 문제의 접근 방법은 저 그림들로 설명이 가능하다 그럼 이것을 코드로 생각을 해보아야 하는데. 가장 먼저, 어떤 변수들을 사용할 지를 생각해보는 것이다. Input N, Array, 막..

해당 문제는 DP 알고리즘으로 풀었다. 물론, 이렇게 푸는 것 보다 소인수분해의 성질을 이용하면 쉽게 풀 수 있다고 하는데. 약간의 자존심? 때문에 어떻게든 DP로 풀어보겠다고 여러가지 시도를 해보면서 알아낸 것들을 적고자 한다. 1. C++에서 long long 타입은 20! 까지만 구할 수 있다. 물론 unsigned 시 65! 까지 구할 수 있지만 그 이후로는 불가능하다. 이를 해결하기 위해선 C++에선 따로, String으로 변환하고 자르고 붙이는 노가다를 해줘야 했고. 지원해주는 공식 라이브러리 조차 없다보니, 차후 이런 비슷한 문제가 나왔을 때 풀기가 너무 어려울거라 생각했다. 하여, BigInteger를 공식으로 지원하는 C#, JAVA 중 C#으로 구현해보았다. using System; u..

해당 문제는 2진 탐색 알고리즘으로 풀 수 있다. 입력 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다. 입력에선 랜선의 개수 K, 필요한 랜선의 개수 N, K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이를 받아야 한다. 이 때, 중요한 것은 2의31승 - 1 즉 21억 int의 최대값을 의미한다. 이는 K가 10,000이 입력되고 각 줄 마다 랜선에서 int의 최대값 ( 약 21억 ) 을 모두 더..