'PROGRAMMING/Algorithm' 카테고리의 글 목록 (4 Page)

[백준(BOJ)] 10809번: 알파벳 찾기 (C++)

📄 문제풀이 과정 소문자 아스키 값은 97부터 시작하므로, find 함수를 통해 알파벳이 S에 처음 등장하면 그 위치를 (문자 아스키 값 - 97) 인덱스의 값으로 저장했다. S에 나타나지 않는 문자의 경우에는 각 알파벳(97+i)이 S에 없다면 string::npos와 동일하므로 -1을 출력하도록 했다. 그 이외 경우에는 A[i] 값을 출력했다. 💻 코드 #include using namespace std; int main(){ string S; cin >> S; int A[26]={0,}; for(char c: S) A[(int)c - 97] = S.find(c); for(int i=0; i

PROGRAMMING/Algorithm 2021. 8. 7. 17:56

[백준(BOJ)] 10808번: 알파벳 개수 (C++)

📄 문제풀이 과정 소문자 a ~ z의 각 개수를 세는 것이므로, 소문자 a의 아스키 코드 값인 97을 각 문자의 아스키 값에서 빼서 인덱스를 구하고 카운팅을 해줬다. 💻 코드 #include using namespace std; int main(){ int A[26]={0,}; string S; cin >> S; for(char c: S) A[(int)c - 97]++; for(int i: A) printf("%d ", i); } 🖨 제출 결과

PROGRAMMING/Algorithm 2021. 8. 7. 17:21

[백준(BOJ)] 9012번: 괄호 (스택(stack), C++)

📄 문제풀이 과정 '(' 인 경우: 스택에 넣는다. (push) ')' 인 경우: 스택에서 하나의 '('를 꺼낸다. 만약 비어있는 경우, 괄호가 맞지 않기 때문에 false를 반환한다. 비어있지 않는 경우, 하나의 VPS가 만들어진 것이다. 한 스트링에 대해 각 문자마다 '('와 ')' 케이스에 대해 push 또는 pop을 반복한 후, 만약 스택이 비어있으면 모든 경우에 대해 VPS를 만족한 것이므로 YES를 출력하고, 스택이 비어있지 않은 경우에는 VPS를 만족하지 않은 것이므로 NO를 출력한다. stack의 empty()로 true 또는 false 반환하여 VPS 여부를 결정한다. 💻 코드 #include using namespace std; bool VPS(string str){ stack s; f..

PROGRAMMING/Algorithm 2021. 8. 7. 17:06

[백준(BOJ)] 10866번: 덱 (덱(deque), C++)

📄 문제풀이 과정 C++ STL deque를 사용해서 덱을 구현했다. BOJ 스택, 큐 문제와 방식이 동일하다. 💻 코드 #include using namespace std; int main(){ deque dq; int N; scanf("%d", &N); for(int i=0; i> ws, str); switch(str[0]){ case 'p': { if(str[1] == 'u'){ if(str[5] == 'f') dq.push_front(stoi(str.substr(str.find(" ") + 1))); else dq.push_back(stoi(str.substr(str.find(" ") + 1))); }else{ if(str[4] == 'f'){ if(dq.empty()) printf("-1\n")..

PROGRAMMING/Algorithm 2021. 8. 7. 15:57

[백준(BOJ)] 10828번: 큐 (큐, C++)

📄 문제풀이 과정 C++ STL queue를 사용해서 큐를 구현했다. 기타 구현 방법은 [백준(BOJ)] 10828번: 스택 과 동일하다. 💻 코드 #include using namespace std; int main(){ queue q; int N; scanf("%d", &N); for(int i=0; i> ws, str); switch(str[0]){ case 'p': { if(str[1] == 'u'){ q.push(stoi(str.substr(str.find(" ")+1))); }else{ if(q.empty()) printf("-1\n"); else{ printf("%d\n", q.front()); q.pop(); } } } break; case 's': printf("%ld\n", q.size..

PROGRAMMING/Algorithm 2021. 8. 7. 15:50

[백준(BOJ)] 10828번: 스택 (스택, C++)

📄 문제풀이 과정 C++ STL stack 을 사용해서 스택을 구현했다. 입력 시 push에서 whitespace 뒤에 숫자가 오기 때문에 getline()으로 입력받았고, std::cin >> std::ws 으로 newline을 무시하고 엔터 시 다음 스트링을 입력받도록 했다. switch문에서 p 문자인 경우에서 두 번째 문자로 push와 pop 구분했다. 스택이 비어있는 여부에 대해서는 삼항연산자를 사용해서 출력했다. 💻 코드 #include using namespace std; int main(){ stack s; int N; scanf("%d", &N); // N: # of instructions for(int i=0; i> std::ws, str); switch(str[0]){ case 'p'..

PROGRAMMING/Algorithm 2021. 8. 7. 15:08

[백준(BOJ)] 11652번: 카드 (정렬, C++)

📄 문제풀이 과정 1. 입력 값의 범위 "적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다." 수의 범위가 integer 범위보다 크고, 음수를 포함하기 때문에 헤더파일을 포함하여 int64_t 자료형을 사용했다. 입력 및 출력 시에도 "%d" 가 아닌 "%ld"를 사용한다. 2. 수의 빈도 음수를 포함하기 때문에, 인덱스를 수로 생각하고 값을 카운팅하는 방법을 사용할 수 없다. 따라서 map을 사용해서 key에는 수를, value는 수에 대한 빈도를 저장해서 입력을 받을 때마다 key에 대한 value를 카운팅했다. 저장 후 value 값이 가장 큰 것을 찾아서 max에 저장하고, value와 일치하는 key 값을 구해서 출력하도록 했다. 💻 코드 #include using namespa..

PROGRAMMING/Algorithm 2021. 8. 6. 20:20

[백준(BOJ)] 10989번: 수 정렬하기 3 (정렬, C++)

📄 문제풀이 과정 단순히 정렬하는 문제인줄 알고 qsort를 사용하려고 했으나, 메모리초과가 발생했다. 메모리 사용은 최대 8MB까지로, 메모리 사용에 유의해야 한다. 일반적으론 배열에 모든 입력을 저장해서 sorting을 진행하지만, 이 문제에선 메모리 문제를 해결하기 위해서는 배열에 입력 값을 저장하면 안 된다. 따라서 입력받을 때마다 해당 수를 인덱스로 해당 수에 대한 카운팅을 하도록 했다. 그럼 각 인덱스마다 수가 몇 번 나타나는지 알 수 있으므로 출력 시 인덱스에 대한 값만큼 반복하여 인덱스 값을 출력하도록 했다. 해당 sorting 방법은 카운팅 정렬 알고리즘이다. 또 주의할 점은, 배열 크기는 입력받는 값인 N이지만, 배열 크기를 N으로 잡거나 출력 시 N만큼 반복문을 돌리면 메모리초과 에러..

PROGRAMMING/Algorithm 2021. 8. 6. 19:06

[백준(BOJ)] 11004번: K번째 수 (정렬, C++)

📄 문제풀이 과정 오름차순 정렬 후 K번째 위치한 수를 출력하는 문제이다. 간단하게 qsort로 정렬 후 0번째부터 시작하므로 K-1 인덱스의 숫자를 출력하면 되겠다고 생각했는데, 런타임 에러가 발생해서 찾아보니 Quick Selection Sort를 이용하여 좀더 효율적인 알고리즘을 사용해야 해결할 수 있음을 알 수 있었다. Quick Selection 알고리즘은 임의의 숫자 배열에서 K번째로 작거나 큰 값을 찾을 때 사용하는 알고리즘으로, 모든 배열을 정렬하는 것이 아니라 partition 함수의 리턴 값과 K를 비교하여 partition을 나눌지 결정하는 방식으로 K번째 수를 찾는다. Quick Sort의 경우 평균 O(nlogn), worst case에 O(n^2)이지만, Quick Selecti..

PROGRAMMING/Algorithm 2021. 8. 4. 17:33

[백준(BOJ)] 10825번: 국영수 (정렬, C++)

#include #include #include #include using namespace std; class solution{ public: string name; int korean; int english; int math; solution(string a, int b, int c, int d){ name=a; korean=b; english=c; math=d; } }; bool compare(solution x, solution y){ if(x.korean == y.korean){ if(x.english == y.english){ if(x.math == y.math) return x.name y.math; } else return x.engl..

PROGRAMMING/Algorithm 2021. 3. 10. 11:20

[백준(BOJ)] 10814번: 나이순 정렬 (정렬, C++)

#include #include #include #include // std::stable_sort using namespace std; bool compare(pair a, pair b){ //if(a.first == b.first) return a.second > b.second; // 나이 같을 경우, 먼저 가입한 a가 앞에 return a.first > N; vector v; for(int i=0; i> x >> y; v.push_back({x,y}); } stable_sort(v.begin(), v.end()..

PROGRAMMING/Algorithm 2021. 3. 10. 11:19