[#135][알고리즘][면접] 코딩면접 준비하기
[알고리즘][면접] 코딩면접 준비하기
1. 문자열 거꾸로 출력하기1) String 사용 : reverse(str.begin(), str.end());
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string str;
getline(cin, str);
reverse(str.begin(), str.end());
cout << str << endl;
return 0;
}
| cs |
2) Stack 사용 : First In Last Out 특징을 활용
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<char> stk;
string str;
getline(cin, str);
for (int i = 0; i < str.length(); i++) {
stk.push(str.at(i));
}
for (int i = 0; i < str.length(); i++) {
cout << stk.top();
stk.pop();
}
return 0;
}
| cs |
2. 벡터에서 최대값 찾기
1) iterator 생성 : vector<int>::iterator it;
2) max_element로 찾기 : it = max_element(input.begin(), input.end());
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
//벡터 생성 (10, 8, 3, 1)
vector<int> input;
input.push_back(10);
input.push_back(8);
input.push_back(3);
input.push_back(1);
//iterator 생성
vector<int>::iterator it;
it = max_element(input.begin(), input.end());
cout << *it << endl;
return 0;
}
| cs |
3. 가장 큰 정사각형 찾기 (포스팅 보러가기)
사각형을 찾는 방법이 인상적...!
//정사각형 찾기
for(int i = 1; i < board.size();i++){
for(int j = 1; j < board[0].size(); j++){
if(copy[i][j] == 1){
copy[i][j] = min(min(copy[i-1][j-1], copy[i][j-1]),copy[i-1][j]) + 1;
answer = max(answer, copy[i][j]);
}
}
}
| cs |
4. 하노이의 탑 (포스팅 보러가기)
1) 재귀 이용
number는 원판의 수 / begin은 출발한 기둥 번호 / end는 도착한 기둥 번호
1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다. move(number-1, begin,pos);
2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다. answer.push_back({begin, end});
3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다. move(number-1, pos, end);
N개의 원판이동에 필요한 횟수 : 2N -1 번
void move(int number, int begin, int end){
if(number==1){
answer.push_back({begin,end});
}else{
int pos = 6 - begin - end;
move(number-1, begin,pos);
answer.push_back({begin, end});
move(number-1, pos, end);
}
}
| cs |
#include<iostream>
#include <stack>
using namespace std;
stack<int> stk;
void move(int a, int c, int n)
{
cout << a << " " << c << endl;
}
void hanoi(int n, int a, int b, int c)
{
bool done = false;
while (!done)
{
while (n > 1)
{
stk.push(c);
stk.push(b);
stk.push(a);
stk.push(n);
n--;
stk.push(c); // c와 b의 교환을 위해 임시로 저장
c = b;
b = stk.top();
stk.pop();
}
move(a, c, n);
if (!stk.empty())
{
n = stk.top();
stk.pop();
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
c = stk.top();
stk.pop();
move(a, c, n);
n--;
stk.push(a); // a와 b의 교환을 위해 임시로 저장
a = b;
b = stk.top();
stk.pop();
}
else
done = true; // 스택이 비면 끝
}
}
int main()
{
int i = 0, cnt = 0;
cin >> i;
hanoi(i, 1, 2, 3);
return 0;
}
| cs |
5. 진법 변환
6. 정렬
댓글
댓글 쓰기