algorithm's People
algorithm's Issues
[C++] BOJ 2178 (행렬의 이해)
- 행렬을 탐색할 때는 상,하가 x, 좌,우가 y이다.
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
for (int dir = 0; dir<4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] != '1' || dis[nx][ny] != -1) continue;
Q.push({nx, ny});
dis[nx][ny] = dis[cur.first][cur.second] + 1;
}
- 위의 코드와 같이 BFS 탐색이 진행 되는데, for문을 처음 돌 때, 현재 위치에서 (1,0)을 증가시킨다. 아래로 한칸 이동하겠다는 뜻이다.
- 위의 코드는 아래, 오른쪽, 위쪽, 왼쪽 순으로 탐색한다.
[C++] BOJ11659
ios::sync_with_stdio(0);
cin.tie(0);
로 시간 초과가 나서 복습합니다.
사실 이거 쓰라고 해도 그냥 안 쓰는 경우가 많았는 데, 써야할 필요성을 느꼈습니다.
ios::sync_with_stdio(0);
= printf와 cout은 각각의 스트림을 가지고 있는 데, 이를 동기화하는 과정, 이 키워드를 사용하면 두 함수를 섞어서 사용하면 안된다.
cin.tie(0);
= cin을 하기전 무조건 cout을 버퍼를 비우고 시작하는 데, 이를 처리하지 않는 코드이다.
ex)
cout << "Enter name;"
cin >> name;
cin.tie(0)
를 하게 되면 cout을 flush 하지 않기 때문에, "Enter name"을 출력하지 않고 cin을 처리합니다.
(cout의 버퍼가 가득 차거나 수동으로 flush 해야합니다.)
[C++] BOJ1406, LinkedList
- 연결리스트에서 연결리스트 삭제 시 유의점
list<char> LL;
auto t = LL.begin();
LL.erase(t); // 이 부분과 같이 삭제를 진행하면 안됨. t는 여전히 삭제된 부분을 가리키고 있음
t = LL.erase(t); // 이 부분과 같이 삭제 후 t를 갱신하여야 합니다.
- 삽입 시 주의점
list<char> LL;
auto t = LL.end();
LL.insert(t, 0); // t의 **앞에** 0을 삽입하겠다는 의미입니다.
[C++] BOJ15649 (back tracking)
- 그래프의 DFS의 개념을 포함하는 듯 하다.
- 게임의 선택지에서 선택하고 진행하다가 잘못됨을 감지하면 선택하는 부분을 다시 로드해서 게임을 또 진행하는 그런 느낌!
주석을 달아놓은 코드를 보면서 이해하는 게 가장 빠를 듯!
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10]; //선택한 숫자를 담을 배열
bool isused[10]; // 탐색했는지 확인할 배열
void func(int k) {
if(k == m) { //base condition
for(int i = 0 ; i<m; i++) {
cout << arr[i] << ' ';
cout << '\n';
return;
}
for(int i = 1; i<=n; i++) {
if(!isused[i]) { // arr[i]를 순서대로 채우다가 채워지지 않은 부분이 발견되었을 때,
arr[k] = i; // i의 값, 처음에 n으로 입력한 limit값에 기반하여 For문으로 넣음
isused[i] = 1; // 사용했다는 표시를 해줌
func(k+1); // 계속 파고 들어가면서 모두 탐색하고 함수 빠져 나오면
isused[i] = 0; //이슈의 [i]를 false 해줌, 새로 넣기 위해
//k+1 .. k+1.. 들어갈 때마다 isused를 true하고 false하고를 반복할 거임.
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
C++ BOJ7576 (BFS 응용)
- 저번에와 같이 잘못했던 방식으로 cnt를 두고 cnt++; 지속하고 cnt 값을 반환하면 되겠다 했는데,
- 마찬가지로 단방향이 아닌 경우에 같은 날 익은 토마토가 다른 날 익은 것처럼 처리되기 때문에, 답이 산으로 가버림
- 결국 마지막에 익은 토마토 (가장 익는데 오래 걸린 토마토를 찾으면 전부 토마토가 익은 것이기 떄문에 거리 구하기랑 똑같다.)
for (int i = 0; i<n; i++) {
for (int j = 0; j<m; j++) {
cin >> board[i][j];
if (board[i][j] == 1)
Q.push({i,j});
if (board[i][j] == 0)
vis[i][j] = -1;
}
}
- 그리고 위의 코드와 같이 제일 처음에 초기화 할 때, board[i][j]가 0일 때만 vis[i][j]를 -1로 초기화 해줌으로써,
- 나중에 탐색할 때 >= 0 조건을 걸어서 익을 수 없는 토마토를 거를 수 있다.
그리고 행렬 자꾸 헷갈리는데 가로길이가 m 세로길이가 n으로 주어지면 행렬을 탐색할 땐 아래와 같이 해야 한다.
for (int i = 0; i<n; i++) {
for (int j =0; j<m; j++) {
if (vis[i][j] == -1) {
cout << -1;
return;
}
ans = max(vis[i][j], ans);
}
}
[C++] BOJ11729 {Recursive} (Tower of Hanoi)
수학적 귀납법에 대한 정의
- a = k일때 성립함을 가정
- a = k+1일때 도 성립함을 증명
- 2,3의 결과로 모든 경우에 대해 성립함을 증명하는 방법
hanoi에 적용
- 1개의 원판을 a에서 b로 옮길 수 있다 // base condition
- n-1개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 가정
- n개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 성립
void BOJ11729::hanoi(int a, int b, int n) { // n개의 원판을 원하는 곳으로 옮긴다.
if (n == 1) { // base condition;
cout << a << ' ' << b << '\n';
return;
}
hanoi(a, 6-a-b, n-1); // n-1개를 빈곳으로 옮긴다.
cout << a << ' ' << b << '\n';
hanoi(6-a-b, b, n-1); // 빈 곳에서 목적지로 n-1개를 옮긴다.
}
아직 아리송하지만 오늘은 어제에 비해 좀 많이 이해했다.
[C++] BOJ10828 (스택의 구현)
- BOJ10828
- 구현은 크게 어렵지 않았으나, 문제의 조건들이 많아 구현안한 부분이 있었음
else //top
{
if(St.empty())
cout << -1 << '\n'; //이 부분을 구현을 안해서 틀렸음
else
cout << St.top() << '\n';
}
- stack 구현에 주의사항으로는
top()
,pop()
을 할 때 꼭empty
를 통해 비어있는지 확인할 것! - 비어있는 데 top(), pop()을 실행할 경우, 런타임 에러가 발생할 수 있음.
[C++] BOJ10866(Deque)
Deque 구현시 유의사항
- tail이 항상 뒤에 있기 때문에 size를 절대값으로 반환하거나, tail - head로 접근한다.
else if (s == "size") {
cout << tail - head << '\n';
}
- 아래의 else if문 내의 else문을 삽입하지 않아 항상 tail--가 실행 돼서 틀렸다.
else if (s == "pop_back") {
if (tail - head == 0)
cout << -1 << '\n';
else {
cout << arr[tail-1] << '\n';
tail--;
}
}
- 위의 코드에서 push_back할때는 값을 추가하고 tail을 증가하기 때문에 값에 접근할 때는 tail-1로 접근하여야 한다.
- 반대로, push_front의 경우 head를 먼저 이동시키고 값을 추가하기 때문에 arr[head]로 값에 접근해도 된다.
- push_front, push_back을 다르게 구현한 이유는 같은 방식으로 구현하면 제일 처음에 같은 인덱스에 값이 들어가거나,
초기화 해놓은 처음 인덱스에 값이 비어버리게 된다.
[C++] BOJ1926 (BFS의 구현)
-
그림의 수를 Num, 최대 크기를 mx로 두고 알고리즘을 풀었는 데,
-
Queue에 값을 넣을 때마다 단순히 mx++를 진행하였다. mx는 연속해서 진행 되는 것이 아님에도 (새로운 그림에 들어갈 때마다 초기화 해주어야 한다.)
-
잘못된 코드
int num = 0, mx = 0;
for (int i = 0; i < width; i++)
for (int j = 0; j < height; j++)
cin >> board[i][j];
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (vis[i][j] || board[i][j] == 0) continue;
num++;
queue<pair<int, int>> Q;
vis[i][j] = 1;
Q.push({i,j});
while(!Q.empty()) {
area++;
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx > width || nx < 0 || ny > height || ny < 0) continue;
if (vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx,ny});
mx++; // 해당 부분이 잘못 되었다. BFS의 시작점을 제외하곤 모두 ++를 하게 된다.
}
}
}
}
- 올바른 코드
for (int i = 0; i < width; i++)
for (int j = 0; j < height; j++)
cin >> board[i][j];
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (vis[i][j] || board[i][j] == 0) continue;
num++;
queue<pair<int, int>> Q;
vis[i][j] = 1;
Q.push({i,j});
int area = 0; // BFS가 새로 시작될 때마다 새로운 변수를 주고,
while(!Q.empty()) {
area++; //pop할때마다 area를 크기를 늘리면 된다.
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx > width || nx < 0 || ny > height || ny < 0) continue;
if (vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx,ny});
}
}
mx = max(mx, area); //BFS가 끝나게 되면 area와 현재의 최댓값을 비교하여 큰 값으로 갱신한다.
}
}
C++ BOJ 2178 (나의 잘못된 풀이)
- 처음엔 아래의 코드와 같이 문제를 해결했고,
int distance = 0;
while(!Q.empty()) {
distance++;
pair<int,int> cur = Q.front(); Q.pop();
for (int dir = 0; dir<4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] != '1' || dis[nx][ny] != -1) continue;
Q.push({nx, ny});
dis[nx][ny] = distance;
}
}
cout << dis[n-1][m-1];
4 6
101111
101010
101011
111011
- 위와 같이 문제가 주어질 때 BFS를 10번 실행할 때까지는 문제가 없다. 왜냐면 단방향이니까 하지만, 문제는 아래처럼 될때이다.
2 -1 9 10 11 12
1 -1 8 -1 12 -1
2 -1 7 -1 -1 -1
3 5 6 -1 -1 -1
- 위의 결과 처럼 단방향이 아니라 11번째 시행할 때와 같이 오른쪽과 아래에 있으면,
- 아래쪽 12에 대한 BFS를 진행하고 13을 기록하고
2 -1 9 10 11 12
1 -1 8 -1 12 -1
2 -1 7 -1 13 -1
3 5 6 -1 -1 -1
- 오른쪽 12에 대한 BFS를 진행하고 14를 기록한다. (14를 기록해야하지만 14를 기록할 수 있는 공간이 없다.)
2 -1 9 10 11 12
1 -1 8 -1 12 -1
2 -1 7 -1 13 -1
3 5 6 -1 -1 -1
- 따라서 다음 13에 대한 BFS를 실행할 때, 15가 기록되버리고 만다.
2 -1 9 10 11 12
1 -1 8 -1 12 -1
2 -1 7 -1 13 15
3 5 6 -1 15 -1
올바른 코드는 아래처럼 현재 위치에 기록된 값 +1 만큼을 dis[nx][ny]에 기록하는 것이다.
dis[nx][ny] = dis[cur.first][cur.second] + 1;
[C++] BOJ11328
for (auto e: s1) {
arr[e-'a']++;
}
for (auto e: s2) {
if (arr[e-'a'] == 0) {
result = "Impossible\n";
break;
}
}
- 반례
abc aaa
- 첫번째 문자열(s1)에서 a가 기록 된 적이 있음
- 두번째 문자열(s2)에서 "a만" 탐색함.
- a는 당연히 있으니까 0이 안나옴. 로직상 문제가 없음.
- 하지만 두번째 문자열(s2)엔 b,c 또한 있어야 한다.
[C++] Array range-based loop
range-based loop
for ( element : array )
cout << element;
ex)
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
for (auto e: arr)
cout << e; // 1,2,3,4,5,6,7,8,9,10
auto는 타입 추론
[C++] BOJ10845 (Stack)
스택의 구현
- 크게 어려운 부분은 없었으나
int MX = 1000005;
int data[MX];
int head = 0, tail = 0;
if (command == "back") {
if (tail - head != 0) cout << data[tail-1] << '\n';
else cout << -1 << '\n';
}
- 가장 마지막 원소에 접근할 때는 tail-1이다!
- tail은 항상 마지막 원소 다음을 가리키고 있기 때문에 값이 비어있다. (혹은 쓰레기값이 들어있지렁이)
[C++] DFS의 구현
- DFS는 아래와 같이 구현하고, BFS와 달리 Queue대신 Stack을 사용한다.
int board[502][502];
int vis[502][502];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int m = 7, n = 10;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int, int>> St;
vis[0][0] = 1;
St.push({0,0}); // *1
while(!St.empty()) {
auto cur = St.top(); St.pop();
for (int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
St.push({nx,ny});
}
}
}
- 자꾸 *1 부분 BFS나 DFS나 구현할 때 깜박하는 데, 저거 안하면 애초에 시작도 안된다.
[C++] BOJ4949 (stack의 활용)
- BOJ4949 구현은 어렵지 않았는데 아래의 코드에서
ios::sync_with_stdio(0);
cin.tie(0);
while (1) {
string input;
getline(cin, input);
if (input == ".") break;
stack<char> st;
bool isVaild = true;
for (auto c: input) {
if (c=='(' || c == '[') {
st.push(c);
}
else if (c == ')') {
if (st.empty() || st.top() != '(') {
isVaild = false;
break;
}
st.pop(); // *1
}
else if (c == ']') {
if (st.empty() || st.top() != '[') {
isVaild = false;
break;
}
st.pop(); // *2
}
// st.pop() *3
}
if (isVaild == false || !st.empty()){
cout << "no" << '\n';
}
else {
cout << "yes" << '\n';
}
}
- *3번만 처리해서 문제가 생김!
- *1 *2번으로 따로따로 ) 들어올때만 pop() 해야 하는 데,
- 들어오지 않았는 데도 pop()을 해버려서 와장창 오답이 나옴.
- (), {} 다루는 문제였는 데, 나도 그걸 좀 잘 보자...
[C++] BOJ1629 (재귀, 귀납적 사고)
if (b == 1) return a % m; //base condition
ll val = POW(a, b/2, m); //*1
val = val * val % m;
if (b%2 == 0) return val;
return val * a % m;
- 모든 재귀는 base condition이 있어야 한다. (무한루프를 돌지 않기 위함인 듯함, 주석 부분이 base condition)
- 귀납적 사고를 해야한다. (위의 코드 *1 POW(a, b/2, m) 부분인 듯함, 아직 자세히 이해 못함)
- a^2n = a^n * a^n이니까 POW(a, b/2, m) 이렇게 작성한 듯 함.
- k승을 계산했다는 것은 POW(k)는 POW(k/2)를 가지고 있으니까
- func(k)가 k, k-1, k-2 ... 1을 출력하면 func(k+1)는 k+1 k k-1 ...1을 출력한다. 를 역으로 발상한 듯 하다.
- 아직 잘 모르겠음.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.