| 개념
🌝 1e9 (1 * 10^9)
왜 1000000007(1e9+7)로 나눈 나머지를 고집할까?
- int는 4바이트(32비트)로 -2^31에서 2^31-1만큼 표현할 수 있습니다.
이는 -2147483648 ~ 2147483647입니다. 이는 2e9로 근사할 수 있습니다.
- long long은 8바이트(64비트)로 -2^63에서 2^63만큼 표현할 수 있습니다.
- 연산에서 2e9에 근사하는 값들의 연산을 한다면 Overflow가 될 수 있습니다.
그렇기에 2^30에 근사하는 값을 가져야 합니다. 이는 1e9에 가까운 값 중에 소수인 1e9+7을 사용하는 것입니다. 이 값은 곱해도 long long의 범위를 넘지 않는다는 장점 또한 가지고 있습니다.
출처 : https://www.facebook.com/algoguide/posts/1117664551755294/
🌝 Char : "문자 -> 숫자" & "숫자 -> 문자" 변환
출처 : 11001.tistory.com/14
🌝 String : "문자 -> 숫자" 변환
#include <string>
stoi();
🌝 '아스키코드'로 변환
#include <iostream>
using namespace std;
int main() {
char n;
cin >> n;
cout << n - 0;
return 0;
}
🌝 대문자 & 소문자 변환
🌝 소숫점 자리 지정 출력
double answer = 7.52458;
// -- 소수점 지정 후, 출력
cout << fixed;
cout.precision(3);
for(auto a : answer) cout << a << "%" << endl;
문제 예시 : 백준 4344 평균은 넘겠지
🌝 find( ) 함수 & substr( ) 함수
문제 예시 : 프로그래머스 전화번호 목록
🌝 중복 제거하는 algorithm STL의 unique()
unique는 두 개의 포인터로 작동합니다. 두 포인터의 이름은 first와 result입니다.
result가 가리키고 있는 값과 first가 가리키고 있는 값이 다르다면 result를 한 칸 옮기고 거기에 first가 가리키는 값을 덮어 씌우는 라이브러리입니다.
#include <algorithm>
cout << s << ' '; // ---> baekjoon
unique(s.begin(),s.end()); // 중복 제거
cout << s << endl; // ---> baekjonn 로 출력된다.
// 그래서 모든 중복을 "정확히" 제거하기 위해서는 아래와 같이 사용한다.
s.erase(unique(s.begin(),s.end()), s.end()); ---> baekjon
🌝 String으로 입력된 숫자 중 가장 큰 수 찾기
sort( )함수 내 bool compare( ) 함수 넣기
#include <algorithm>
using namespace std;
bool compare(string a, string b){
return a + b > b + a ? true : false;
}
string solution(vector<int> numbers) {
vector<string> temp;
for(auto n : numbers) temp.push_back(to_string(n));
sort(temp.begin(), temp.end(), compare);
return temp;
}
문제 예시 : 프로그래머스 가장 큰 수
🌝 직사각형 좌표 찾기
🌝 vector를 배열로 생성해서 2차원 동적 배열형태로 사용하기 (🥕)
예시 1) BFS dkanxmstmdgml.tistory.com/194
예시 2) DFS dkanxmstmdgml.tistory.com/193
#include <iostream>
#include <vector>
using namespace std;
// 총 7개의 노드가 인접한 노드를 가질 수 있도록.
int number = 7;
int arr[8];
vector<int> v[8];
int y;
void dfs(int n){
if(arr[n]) return; // 현재 노드를 방문했다면 함수 끝내기
arr[n] = true; // 방문처리
cout << n << ' ';
// 재귀
for(int i = 0; i < v[n].size(); i++){
y = v[n][i];
dfs(y);
}
}
int main() {
// 1과 2을 연결
v[1].push_back(2);
v[2].push_back(1);
// 1과 3을 연결
v[1].push_back(3);
v[3].push_back(1);
// 2와 3을 연결
v[2].push_back(3);
v[3].push_back(2);
// 2와 4을 연결
v[2].push_back(4);
v[4].push_back(2);
// 2와 5를 연결
v[2].push_back(5);
v[5].push_back(2);
// 3과 6을 연결
v[3].push_back(6);
v[6].push_back(3);
// 3과 7을 연결
v[3].push_back(7);
v[7].push_back(3);
// 4과 5을 연결
v[4].push_back(5);
v[5].push_back(4);
// 6과 7을 연결
v[6].push_back(7);
v[7].push_back(6);
for(int i = 0; i < 8; i++){
for(int j = 0; j < v[i].size(); j++){
cout << v[i][j] << ' ';
}
cout << endl;
}
dfs(1);
return 0;
}
vector v에 push_back된 값들.
1차원으로 선언 후, 2차원으로 동적 할당한 뒤 아래처럼 접근 가능
for(int i = 0; i < v[n].size(); i++){
y = v[n][i];
dfs(y);
}for
🌝 C++의 priority_queue STL은?
최대 힙으로 구현되어 있다.
예시 1)
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
while(!q.empty()) {
cout << q.top() << ' ';
q.pop();
}
cout << '\n';
}
int main() {
priority_queue<int> q;
const auto data = {1,8,5,6,3,4,0,9,7,2};
for(int n : data)
q.push(n);
print_queue(q);
// 출력 결과 : 9 8 7 6 5 4 3 2 1 0
priority_queue<int, vector<int>, greater<int>>q2(data.begin(), data.end());
print_queue(q2);
// greater<int> 사용 & 출력 결과 : 0 1 2 3 4 5 6 7 8 9
}
예시 2) 최소 힙으로 구현하기 위해서 '-'를 붙여준다.
#include <iostream>
#include <vector>
#include <priority_queue>
using namespace std;
/*
* 코드 참고 : https://github.com/ndb796/python-for-coding-test/blob/master/9/2.cpp
*/
int n, m, start;
vector<pair<int, int>> graph[100001];
int d[100001]; // 최단 거리 테이블
void dijkstra(int start){
priority_queue<pair<int, int>> pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({0, start});
d[start] = 0;
while(!pq.empty()){
// 가장 최단 거리 짧은 노드 꺼내기
int dist = -pq.top().first; // 현재 노드의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
if(d[now] < dist) continue; // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
for(int i = 0; i < graph[now].size(); i++){
int cost = dist + graph[now][i].second();
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if(cost < d[graph[now][j].first]){
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].fisrt));
}
}
}
}
int main() {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for(int i = 0; i < m; i++){
int a, b, c;
cin a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back(make_pair(b, c));
}
d[100001] = {1e9,};
dijkstra(start);
for(int i = 1; i <= n; i++){
if(d[i] != 1e9) cout << d[i] << " ";
}
return 0;
}| 문제
🌚 문자열
*** 문자열 문제풀 때, 생각해보는 풀이 순서 ***
** 1차원 배열(문자열) + 2차원 배열(정수&문자열) 다루기 **
SWEA 개념 정리
- 팰린드롬 dkanxmstmdgml.tistory.com/665
- 패턴매칭 dkanxmstmdgml.tistory.com/666
- 백준 : 놀라운 문자열 (문자열의 D쌍 구하기)
dkanxmstmdgml.tistory.com/529?category=745759
- 백준 : 문자열 (두 문자열의 차이 구하기)
dkanxmstmdgml.tistory.com/533?category=745759
- 혼자 공부 : 문자열 속 같은 문자 찾기
dkanxmstmdgml.tistory.com/526?category=745759
- 백준 : 알파벳 찾기 (풀이) **
for문에서 'a'부터 'z'까지 반복할 수 있음을 꼭 기억하기.
- 백준 : 단어 공부 (풀이) ** 다시 풀기
> 대문자 & 소문자 변환
🌚 Stack & Queue 문제 모음
- 다리를 지나는 트럭
- 기능 개발
🌚 힙
- 더 맵게
🌚 해시
- 전화번호 목록
: 해시 풀이 또는 substr 이용 가능한 문제
- 완주하지 못한 선수 (🥕)
: phone_book[ i ][ j ] // 1차원 벡터-> 2차원 동적 배열로 사용 예제
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
bool solution(vector<string> phone_book) {
bool answer = true;
unordered_map<string, int> map;
// map 초기화
for(int i = 0; i < phone_book.size(); i++)
map[phone_book[i]] = 1;
//map.insert({phone_book[i], 1}); 도 가능
for(int i = 0; i < phone_book.size(); i++) {
string temp = "";
// phone_book 원소 길이만큼 하나씩 체크
for(int j = 0; j < phone_book[i].size(); j++) {
temp += phone_book[i][j]; // string 하나씩 잘라서 temp에 저장
//--- ** 아래 그림 참고해서 이
// 만약 temp != phone_book[i]가 없다면
// phone_book[i]가 119일 때, map[temp]가 true가 된다. -> 틀린 답이 출력됨.
// map[temp]은 위의 값을 예외처리 해준다.
// 119 -> 119, 234, 119283 중 119 == 119, 119 != 119283 이므로 후자에서 break가 된다.
if(map[temp] && temp != phone_book[i]){
answer = false;
break;
}
}
}
return answer;
}
// 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=cpp ✔cout << phone_book[ i ][ j ] << ' ' << temp << endl -->> 1 1 1 11 9 119 |
→ |  |
🌚 DFS & BFS
( 는 다시 풀어보기 )
- 이코테
1) 음료수 얼려먹기
2) 미로 탈출
- 백준 > www.acmicpc.net/step/24
1) DFS와 BFS (silver Ⅱ) - 풀이
2-1) *** 토마토 ( silver I ) - 풀이
> 범위 잘 지정해서 풀기 & 입력받을 때, queue 활용(아래와 같이 1이 여러 개일 경우)
2-2) 토마토 ver 2 - 풀이
> 3차원 배열 활용 문제
3) 숨바꼭질 - 풀이
(이런 것도 bfs로 풀 수 있구나 했던 문제)
4) 바이러스 - 풀이
5) 유기농 배추 - 풀이
6) ***벽 부수고 이동하기 - 풀이
++ )
...ㅎ 4/25 삼성 코테 어떡하지... 이제까지 풀었던 bfs, dfs랑 차원이 다른 어려움이당..
백준에서 좀 문제에 익숙해지나 했는데,
차원이 다르게 어렵다...
언제 다시 올지 모르는 기회이니 시험장 가서 떨지 말고, 최선을 다하고 와야지
- 프로그래머스 > programmers.co.kr/learn/courses/30/parts/12421
'OLD_알고리즘 > 개념 & 문제 정리' 카테고리의 다른 글
| 📌알고리즘 / 자료구조 / STL (0) | 2021.05.10 |
|---|---|
| 삼성 SW 역량 테스트 대비 문제 추천(A형 & 3급 신입 공채) (0) | 2021.04.20 |
댓글