씅의 기록하는 개발노트

문제출처

https://www.acmicpc.net/problem/17140

문제풀이

R연산과 C연산을 반복하여 a[r][c]의 값이 k가 몇번째에 나오는지 출력하는 문제입니다. (100번 이상 연산이 필요할 시 -1 출력)

R연산과 C연산은 row기준인지 column기준인지에 따라 방향만 바뀌므로 R연산 기준으로 풀이하겠습니다.

코딩하기 전에 제가 생각한 알고리즘은 다음과 같습니다.

1. rowSize와 columnSize를 통해 R연산 C연산 구분

2. 100번 초과시 프로그램 종료

-- 연산로직

3. 함수 호출마다 새로운 사이즈가 결정된다. 때문에 R연산은 newColSize에 갱신하여 전역변수인 colSize를 갱신한다.

4. 새로운 행마다 열에 대해 어떤 숫자가 몇개 있는지 카운팅한다.

4-1) 카운팅한 숫자를 0을 제외하고 벡터에 카운팅한 개수와 해당 숫자를 넣어준다. 이때 pair를 sorting할 때 first값을 기준으로 정렬되는 특징을 활용해 카운팅한 개수를 first에 저장한다.

4-2) vector는 pair이기 때문에 새로 등록할 크기는 vector사이즈의 2배이다. 모든 행에 대해 실행할 때마다 큰 값을 newColSize에 저장한다.

4-3) vector를 순회하면서 a배열을 갱신해주고 사이즈가 줄어들 경우 0으로 저장한다.

이 문제는 단순 구현만 해주면 되는 문제입니다. 때문에 생각을 위와 같이 하나씩 정리한 뒤 소스를 작성하는게 좋습니다. 특히 이 문제에서는 rowSize와 colSize가 계속 늘어났다 줄어들기 때문에 이 처리를 잘 해줘야 하며 sorting시 사용자 함수를 사용하던지 first값 기준으로 정렬되는 특징을 사용할 수 있어야 합니다. 아무래도 시뮬레이션 문제는 직접 손으로 그려보고 문제를 파악한뒤 로직을 어떻게 구현할 것인지 먼저 구상하는게 문제풀이에서 가장 중요한 것 같습니다.

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17140/BOJ_17140/boj17140.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int r, c, k, rowSize = 3, colSize = 3;
int a[100][100];
int numberCount[101];
void init() {
	cin >> r >> c >> k;
	r--, c--;
	for (int y = 0; y < 3; y++) {
		for (int x = 0; x < 3; x++) {
			cin >> a[y][x];
		}
	}
}
void rCalc() {
	int newColSize = 0;

	for (int y = 0; y < rowSize; y++) {
		memset(numberCount, 0, sizeof(numberCount));
		vector<pair<int, int> > v;
		for (int x = 0; x < colSize; x++) numberCount[a[y][x]]++;

		for (int i = 1; i <= 100; i++) {
			if (numberCount[i] == 0) continue;
			v.push_back(make_pair(numberCount[i], i));
		}
		
		sort(v.begin(), v.end());
		int curColSize = v.size() * 2;
		newColSize = max(newColSize, curColSize);

		int xIndex = 0;
		for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++) {
			a[y][xIndex] = it->second;
			a[y][xIndex + 1] = it->first;
			xIndex += 2;
		}
		for (int x = curColSize; x < colSize; x++) a[y][x] = 0;
		
	}
	colSize = newColSize;
}
void cCalc() {
	int newRowSize = 0;
	
	for (int x = 0; x < colSize; x++) {
		memset(numberCount, 0, sizeof(numberCount));
		vector<pair<int, int> > v;
		for (int y = 0; y < rowSize; y++) numberCount[a[y][x]]++;

		for (int i = 1; i <= 100; i++) {
			if (numberCount[i] == 0) continue;
			v.push_back(make_pair(numberCount[i], i));
		}

		sort(v.begin(), v.end());
		int curRowSize = v.size() * 2;
		newRowSize = max(newRowSize, curRowSize);

		int yIndex = 0;
		for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++) {
			a[yIndex][x] = it->second;
			a[yIndex + 1][x] = it->first;
			yIndex += 2;
		}
		for (int y = curRowSize; y < rowSize; y++) a[y][x] = 0;
	}
	rowSize = newRowSize;
}
void solve() {
	int ans = 0;
	while (1) {
		if (ans > 100) {
			cout << -1 << "\n";
			break;
		} else if (a[r][c] == k) {
			cout << ans << "\n";
			break;
		}
		if (rowSize >= colSize) rCalc();
		else cCalc();
		ans++;
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	solve();
	return 0;
}

문제출처

https://www.acmicpc.net/problem/15685

문제풀이

정말 어려웠던 문제였다. 문제풀이의 핵심은 세대가 증가할 때 마다 방향전환의 규칙성을 찾는것이 핵심이다.

0 (동쪽)방향을 기준으로 예시를 들어보면 이해하는데 조금 더 편하다.

0세대 : 0

1세대 : 0 1

2세대 : 0 1 | 2 1

3세대 : 0 1 2 1 | 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 | 2 3 0 3 2 3 2 1

예시를 보면 알 수 있듯이 1세대에서 2세대의 방향정보를 만드는 규칙은 마지막 부분 +1을 추가하는 것이다. 2세대에서 3세대를 만들때도 같은 규칙을 사용한다. 하지만 +1을 계속하면 {0,1,2,3}의 인덱스가 깨지므로 +1한 값의 %4를 해주면 해당 세대의 방향정보를 알 수 있다.

그다음부터는 정말 단순한 구현이다. 이때 문제에서는 꼭지점을 기준으로 드래곤 커브를 그리고 있다. 이 기준을 단순 2차원 배열로 바꾸어 계산해 주면 된다. 2차원 배열에 표현하기 때문에 (x,y) <= 100인 조건은 (x,y) <= 101로 변환하여 풀이한다.

개인적으로 저 규칙을 알아내는것이 매우 힘들었다. 시간이 지나고 다시 풀어봐야 겠다.

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_15685/BOJ_15685/boj15685.cpp

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 101;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
int n, y, x, d, g;
int map[MAX][MAX];
int solve() {
	cin >> n;
	while (n--) {
		cin >> x >> y >> d >> g;
		vector<int> dir;
		dir.push_back(d);
		map[y][x] = 1;
		for (int i = 0; i < g; i++) {
			int dirSize = dir.size();
			for (int j = dirSize - 1; j >= 0; j--) {
				dir.push_back((dir[j] + 1) % 4);
			}
		}
		for (int i = 0; i < dir.size(); i++) {
			y += dy[dir[i]];
			x += dx[dir[i]];
			if (y < 0 || x < 0 || y >= MAX || x >= MAX) continue;
			map[y][x] = 1;
		}
	}
	int ret = 0;
	for (int r = 0; r < MAX - 1; r++) {
		for (int c = 0; c < MAX - 1; c++) {
			if (map[r][c] == 1 && map[r + 1][c] == 1 && map[r][c + 1] == 1 && map[r + 1][c + 1] == 1) {
				ret++;
			}
		}
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout<<solve();
	return 0;
}

문제출처

https://www.acmicpc.net/problem/17142

문제풀이

연구소에 이어 조금 예외가 추가된 문제이다. 기본적으로는 완전탐색을 통해 풀면 된다 생각되었다.

소스코드 작성에 앞서 문제 풀이 방법은 다음과 같이 생각해봤다.

1. 활성화할 바이러스를 선택한다(selectVirus)

- 선택한 바이러스가 m개라면 바이러스를 퍼트린다.

2. 바이러스를 퍼뜨릴때 모든 경우를 다 사용해야 하기 때문에 새로운 2차원 배열을 생성한다.

- 활성화할 바이러스를 큐에 담는다.

- 문제에서 제시한 조건을 따라 벽이거나 이미 바이러스가 전파된 경우를 제외하고 바이러스를 전파한다.

3. 활성화된 바이러스로 퍼지는데 걸리는 시간을 구한다.

- 이때 입력으로 받은 map이 빈칸이고 새로운 timeMap이 초기 값이라면 바이러스가 완전히 퍼지지 않은것으로 판단한다.

- 활성화된 바이러스는 제외해야하기 때문에 map이 0인 것만 카운팅한다.

4. 이후 return 받은 결과값이 최대값과 같다면 바이러스를 모든 빈 칸에 전파할 수 없는 경우이므로 -1을 출력하고 이외의 경우 최소값을 출력한다.

생각보다 시간이 많이 걸렸다. 처음 90%대에서 자꾸 틀렸습니다가 나왔는데 활성화된 바이러스를 제외하지 않아서 였다. 백준 게시판의 반례모음집을 보고 어디서 잘못됬는지 파악할 수 있었다.

소스 작성전에 예외없이 알고리즘을 짤 수 있도록 습관을 더 길러야겠다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
// 2020/04/12 14:55 문제풀이 시작 -> 16:40 문제풀이 완료
struct VIRUS {
    int y, x;
};
bool isAllSpread;
int n, m, ans=987654321;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int map[50][50];
vector<VIRUS> virus, selected;
void init() {
    cin>>n>>m;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {
            cin>>map[y][x];
            if (map[y][x] == 2) virus.push_back({y,x});
        }
    }
}
int spreadVirus() {
    isAllSpread = 1;
    queue<VIRUS> q;
    int timeMap[50][50];
    memset(timeMap, -1, sizeof(timeMap));

    for (int i=0; i<selected.size(); i++)  {
        q.push(selected[i]);
        timeMap[selected[i].y][selected[i].x] = 0;
    }

    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

        for (int i=0; i<4; i++) {
            int ny=y+dy[i];
            int nx=x+dx[i];

            // out of bound
            if (ny<0 || nx<0 || ny>=n || nx>=n) continue;

            // 벽 or 이미 바이러스 퍼진 경우
            if (map[ny][nx] == 1 || timeMap[ny][nx] != -1) continue;

            q.push({ny, nx});
            timeMap[ny][nx] = timeMap[y][x] + 1;
        }
    }

    int time=0;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {

            // 전부 전파하지 못한 경우
            if (map[y][x] == 0 && timeMap[y][x] == -1) {
                isAllSpread=0;
                return 987654321;
            }
            // 활성화 하지 않은 바이러스는 제외
            else if (map[y][x] == 0) {
                time = max(time, timeMap[y][x]);
            }
        }
    }
    return time;
}
void selectVirus(int index) {
    if (selected.size() == m) {
        int time = spreadVirus();
        if (isAllSpread) ans = min(ans, time);

        return;
    }

    for (int i=index; i<virus.size(); i++) {
        selected.push_back(virus[i]);
        selectVirus(i+1);
        selected.pop_back();
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    selectVirus(0);
    if (ans == 987654321) cout<<"-1"<<"\n";
    else cout<<ans<<"\n";
    return 0;
}

문제출처

https://www.acmicpc.net/problem/14888

문제풀이

 재귀함수를 이용한 완전탐색 문제입니다. n의 최대값이 11이므로 완전탐색이 가능하다고 판단되어 완전탐색으로 풀이하였습니다.

숫자 순서는 변하지 않고 연산자 우선순위도 적용되지 않기 때문에 현재까지 계산한 값과 연산자를 통한 계산을 해주면 되는 문제입니다. 처음에 최대값, 최소값을 0xfffffff으로 초기화 했는데 틀렸습니다가 나왔다. 문제를 잘 읽어보면 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 라는 문구를 보아 10억으로 초기화 해서 해결했습니다.

 저같은 실수를 하신 분들을 위해 반례 하나 적어두겠습니다.

5

100 100 100 100 10

0 0 4 0

소스코드

#include <iostream>
using namespace std;
int n, mx=-1000000000, mn=1000000000;
int a[100], oper[4];

void solve(int curSum, int depth) {
    if (depth == n) {
        mx = curSum > mx ? curSum : mx;
        mn = curSum > mn ? mn : curSum;
        return;
    }

    if (oper[0] > 0) {
        oper[0]--;
        solve(curSum + a[depth], depth+1);
        oper[0]++;
    }
    if (oper[1] > 0) {
        oper[1]--;
        solve(curSum - a[depth], depth+1);
        oper[1]++;
    }
    if (oper[2] > 0) {
        oper[2]--;
        solve(curSum * a[depth], depth+1);
        oper[2]++;
    }
    if (oper[3] > 0) {
        oper[3]--;
        solve(curSum / a[depth], depth+1);
        oper[3]++;
    }
}

void init() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>a[i];
    for (int i=0; i<4; i++) cin>>oper[i];
    solve(a[0], 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    cout<<mx<<"\n"<<mn<<"\n";
    return 0;
}

문제 출처

https://www.acmicpc.net/problem/9012

문제 풀이

문자열을 확인하면서 "("인 경우 stack에 push

만약 문자열이 ")"이고 stack이 비어있다면 VPS가 아니라고 판단.

stack이 비어있지 않다면 top에 "("인지 확인한뒤 pop

모든 문자열을 확인한 뒤 stack이 비어있다면 VPS 비어있지 않으면 VPS가 아니라고 판단할 수 있다.

이 문제는 stack이 아닌 카운팅하면서 문제를 풀 수도 있으며 두가지 방법 모두 O(N)의 복잡도를 가진다.

소스 코드

//
//  main.cpp
//  BOJ_9012
//
//  Created by sw on 18/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>

using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin>>t;
    
    while (t--) {
        string input;
        cin>>input;
        stack<char> st;
        
        for (int i=0; i<input.size(); i++) {
            if (input[i] == '(') {
                st.push(input[i]);
            } else {
                if (!st.empty() && st.top() == '(') {
                    st.pop();
                } else {
                    st.push(')');
                    break;
                }
            }
    }
        if (st.empty()) cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
        
    return 0;
}

문제 출처

https://www.acmicpc.net/problem/1874

문제 설명

스택 성질에 대해 이해가 필요한 문제입니다. 처음에 고민하다가 입력받은 숫자가 나올때까지 push하다가 입력받은 숫자가 나오면 pop해주면 쉽게 풀 수 있는 문제입니다. idea가 필요했던 문제!

소스 코드

//
//  main.cpp
//  BOJ_1874
//
//  Created by sw on 17/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    int num[n];
    vector<char> ret;
    stack<int> st;
    
    for (int i=0; i<n; i++) cin>>num[i];
    
    int idx=0;
    for (int i=1; i<=n; i++) {
        st.push(i);
        ret.push_back('+');

        while (!st.empty() && st.top() == num[idx]) {
            idx++;
            st.pop();
            ret.push_back('-');
        }
    }
    
    if (!st.empty()) cout<<"NO"<<"\n";
    else for (auto c : ret) cout<<c<<"\n";
    
    return 0;
}

[문제 출처]

https://www.acmicpc.net/problem/15649

1부터 N까지 자연수중 길이가 M인 순열을 출력하는 문제입니다.

[순열 ?]

 순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식입니다. 즉 순서가 존재하는 열인 것이죠.

c++기준 next_permutation / prev_permutation과 같은 STL함수를 통해 쉽게 구현할 수 있습니다. 

[문제풀이]

 완전 탐색을 통해 문제를 풀이합니다. DFS방식으로 basecase조건 충족시 출력을 하고 함수에서 나오는 방법입니다. 이때 visit배열로 방문여부를 체크하여 중복 값이 사용되는 것, 다시말해 같은 수를 여러번 고르는 경우를 방지하면 됩니다.

[소스코드]

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> v;
bool visit[9];
void solve(int cnt) {
	if (cnt == m) {
		for (int i=0; i<v.size(); i++) cout<<v[i]<<" ";
		cout<<"\n";
		return;
	}
	
	for (int i=1; i<=n; i++) {
		if (visit[i]) continue;
		visit[i] = 1;
		v.push_back(i);
		solve(cnt+1);
		visit[i] = 0;
		v.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	solve(0);
	return 0;	
}

문제출처

https://www.acmicpc.net/problem/13460

문제풀이

 삼성 역량테스트 기출문제 입니다.

문제에서 원하는 답은 보드를 상,하,좌,우 방향으로 기울였을때 빨간구슬만을 구멍으로 빼낼 수 있는 최소횟수입니다. 이때, 파란구슬은 빠지면 안되고 보드는 총 10번 이하로 움직여야 합니다. 출력은 목적을 달성하는 최소횟수이고 파란구슬이 빠지거나 보드를 10번이상 움직였다면 -1을 출력하면 됩니다.

문제이해를 위해 예제를 따라해보면 더 쉽게 이해하실 수 있습니다.

예제를 따라하면 처음에 왼쪽으로 움직이고 다음번에 오른쪽으로 움직인경우 구슬의 위치가 같은 것을 알 수 있습니다. 또한 같은 방향으로 반복적으로 움직여도 구슬의 위치에는 영향을 받지 않는다는 것을 알 수 있습니다.

즉, 같은방향 혹은 이전방향과 반대방향으로 움직일 경우는 제외해도 됩니다. (구슬의 위치가 같다면 이러한 경우에 해당됩니다.)

문제풀이 과정은 다음과 같습니다.

1.  빨간공을 움직입니다.

2. 파란공을 움직입니다.

3. 파란공이 구멍으로 빠진경우 잘못된 경우이므로 제외합니다.

4. 빨간공과 파란공의 위치가 중복된 경우 공의 위치를 재조정합니다.

    만약 빨간공이 3칸, 파란공이 2칸이동했다면 빨간공의 위치를 이동방향 기준으로 1번 뒤로 되돌립니다.

    예를 들어 # . . R B #일때 왼쪽으로 기울인다면 공의 위치가 겹치기 때문에 # (R,B) . . . # 와 같은 상태입니다.

    이 경우 빨간공이 2칸, 파란공이 3칸움직였기 때문에 파란공을 오른쪽으로 1번 되돌려야 정상적인 좌표를 가지게 됩니다.

5. 이과정을 반복하면서 빨간공만 빠지고 움직인 횟수가 10번이내라면 횟수를 출력하고 이외의 경우에는 -1을 출력합니다.

소스코드

문제풀이

 일반적인 bfs로 풀이 하였다. 큐에 소요시간 정보와 현재 위치를 저장한 구조체를 넣어 문제를 해결했다.

하지만 여기서 다음 파이프의 조건을 판단할때 반대로 생각해야 한다는 것이 매우 중요했다. 이 문제의 핵심 포인트이다!! 

계속 지체되었던 부분인데 현재 위치에서 오른쪽으로 간다고 가정한다면, 다음위치의 파이프는 왼쪽이 뚫려있어야 한다! 

소스코드

문제풀이

상당히 어렵게 푼 문제이다. 단순히 구현하는 문제(시뮬레이션)인데 공유하는 BC가 있을경우 선택을 잘 해야한다.

유저 a와 b의 경로를 2차원 배열에 저장하고 이동이 끝나면 시작위치의 좌표를 재조정한다.

이때 1) 유저 a만 충전하는 경우 2) 유저 b만 충전하는 경우 3) 유저 a,b 모두 충전하는 경우

총 3가지로 나누어 처리하였다.

소스코드