대엉코딩

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

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

2. 주의사항

- 조건으로 인한 시간초과

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}

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

1. 풀이방법

- N의 숫자의 범위가 큰편입니다.

- O(N^2)은 100,000,000 시간제한 0.5초에 타임리밋 걸릴 수 있습니다.

- 투포인터를 이용해 한번의 순회로 해결했습니다.

- 단, 이는 A[i]가 자연수 (음수 아님) 조건이 있기 때문에 사용할 수 있습니다.

2. 주의사항

- 문제 조건을 정확히 파악해야 합니다.

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int N, M;
vector<long long> arr;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	long long tt;
	for (int i = 0; i < N; i++) {
		cin >> tt;
		arr.push_back(tt);
	}
	int tmpsum = arr[0];
	int resultcount = 0;
	int sp = 0;
	int ep = 0;
	while (1) {
		if (tmpsum == M) {
			resultcount++;
			tmpsum -= arr[sp];
			sp++;
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum < M) {
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum > M) {
			tmpsum -= arr[sp];
			sp++;
		}
	}
	cout << resultcount;
	return 0;
}

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

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

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

1. 풀이방법

- 처음에는 단순 dfs로 접근하긴 했지만 (오랜만에 풀이라 일단 접근했음)

- 하면서도 분명 제대로 구현되도 시간초과가 뜨거나 스택오버플로우가 날 것 이라 생각했습니다.

- 처음시도는 역시나 시간초과

- 시간초과라면 dp테이블을 이용해보자는 생각 !

- 아, 근데 오랜만에 푸니까 dp적 머리가 잘 돌아가지 않아서 고생을 좀 했습니다....

- 우선 테이블을 모두 -1 처리를 하고 visit이 이미 true인 곳에 다시 오면 그건 싸이클이므로

- -1을 출력 (무한정 왔다리갔다리 가능)

- dp가 -1이 아닐경우 기존에 저장되어 있는 수와 현재의 루트에서 +1 (한번 더 이동) 해서 더 많은 이동횟수로 업데이트

- dfs +dp 라고 할 수 있겠네요. dfs는 간단한 수준이라 생략하겠습니다.

2. 주의사항

- 시간초과

3. 코드

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
using namespace std;

int N, M;
int ground[50][50];
int dp[50][50];
bool visited[50][50];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


void Input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        string inputs;
        cin >> inputs;
        for (int j = 0; j < inputs.length(); j++){
            if (inputs[j] == 'H') ground[i][j] = 0;
            else ground[i][j] = inputs[j] - '0';
        }
    }
}

int DFS(int x, int y){
    if (x < 0 || y < 0 || x >= N || y >= M || ground[x][y] == 0) return 0;
    if (visited[x][y] == true) // 무한반복이 가능
    {
        cout << -1 << endl;
        exit(0);
    }
    if (dp[x][y] != -1) return dp[x][y]; // 바로 dp 테이블에서 리턴

    visited[x][y] = true;
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++){
        int tx = x + (ground[x][y] * dx[i]);
        int ty = y + (ground[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(tx, ty) + 1);
    }
    visited[x][y] = false;
    return dp[x][y];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Input();
    memset(dp, -1, sizeof(dp)); //dp 테이블 초기화
    cout << DFS(0, 0) << endl;
    return 0;
}

오늘은 프로그래머스 해쉬문제를 풀면서 하나 알게된 사실이 있습니다..

c++ algorithm 라이브러리 sort()를 이용할 경우

문자열은 사전 순으로 정렬이 된 결과가 나옵니다.

unordered_map의 경우 잘 안써와서 미숙한데, 그래도 알아두어야 겠다 생각하여 따로 작성해서 

게시글로 올려야 겠네요....! 

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

	return 0;
}

** 잘못된 내용이 있으면 알려주세요 **

www.acmicpc.net/problem/17143

1. 풀이방법

- 비교적 간단한 구현 문제입니다.

- 1단계가 낚시왕의 이동, 2단계가 낚시, 3단계가 상어의 이동입니다.

- 1,2 단계는 매우 쉽고, 3단계에서 최대 상어의 마리수 M =10000이고, 한번에 이동할 수 있는 칸은 최대 1000칸 이므로

- 한칸씩 상어를 이동시킬 경우 10000000 에, 다른 부가적인 작업들이 들어가면 시간초과 가능성이 있다고 판단하여

- 문제의 사진을 잘 분석해 보면 한칸씩 이동시키는 것이 어떤 수가 되었을 때 정확히 같은방향, 같은 자리로 오는지를 

- 파악해보면, ( 2 * ((R or C)-1) ) 칸을 움직이면 같은방향을 가지면서 같은 자리로 이동합니다.

- 즉 최종으로 한칸씩 이동시킬 fixedmovecount= speed % ( 2 * ((R or C)-1) ) 만큼만 한칸 씩 이동시키면 됩니다.

2. 주의사항

- 모듈러연산을 활용한다 정도?

- 문제도 짧고 헷갈릴만한 단어도 딱히 없었습니다...

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
int R, C,M;
struct shark {
	int speed, dir, ssize,num;
};
vector<shark> sea[102][102];
vector<pair<int, int>> sharkvec; // 상어들의 위치 저장
bool sharkdie[10001]; // 상어 살았는지 여부 조사
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
int sharksum;

void inputs() {
	cin >> R >> C>>M;
	int r, c, s, d, z;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> s >> d >> z;
		sharkvec.push_back({ r,c });
		sea[r][c].push_back({ s,d - 1,z,i });
	}
}
void getshark(int f) {
	for (int i = 1; i <= R; i++) {
		if (!sea[i][f].empty()) {
			sharksum += sea[i][f][0].ssize; //잡음
			sharkdie[sea[i][f][0].num] = true;
			sea[i][f].pop_back();
			return;
		}
	}
	return;
}

void moveshark() {
	vector<shark> tmpsea[102][102];
	for (int i = 0; i < M; i++) {
		if (sharkdie[i]) continue; //죽었으면 보지않음

		int x = sharkvec[i].first; int y = sharkvec[i].second;
		int tmps, tmpd, tmpz;
			tmps = sea[x][y][0].speed;
			tmpz = sea[x][y][0].ssize; //크기
			tmpd = sea[x][y][0].dir;


		int fixexmovecount;
		if (tmpd <= 1) { // 세로이동
			fixexmovecount = tmps%(2*(R - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (x == R) { tmpd = 0; }
				if (x == 1) { tmpd = 1; }
				x += dx[tmpd];
			}
		}
		else { //가로이동
			fixexmovecount = tmps%(2*(C - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (y == C) { tmpd = 3; }
				if (y == 1) { tmpd = 2; }
				y += dy[tmpd];
			}
		}
		sharkvec[i].first = x; sharkvec[i].second = y;
		if(tmpsea[x][y].empty()) tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i }); //아무도 없으면 그냥 삽입
		else { //다른 상어가 있으면 큰놈이 작은놈을 잡아먹는다
			if (tmpsea[x][y][0].ssize < tmpz) {
				sharkdie[tmpsea[x][y][0].num] = true; // 기존에 있던놈 잡아먹힘
				tmpsea[x][y].pop_back();
				tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i });
			}
			else { //넣으려던놈이 잡아먹힘
				sharkdie[i] = true;
			}
		}
	}
	for (int t = 1; t <= R; t++) {
		for (int k = 1; k <= C; k++) {
			sea[t][k] = tmpsea[t][k];
		}
	}
	return;
}
/*void watchshark() {
	cout << "\n";
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (sea[i][j].empty()) cout << 0 << " ";
			else cout << sea[i][j][0].num+1 << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int fm = 1; fm <= C; fm++) { // 낚시꾼의 위치 (1초당)
		getshark(fm);
		moveshark();
	}
	cout << sharksum;


	return 0;
}

www.acmicpc.net/problem/17822

1. 풀이방법

- 구현문제입니다.

- circular의 특성만 체크 해서 0이 될경우 M으로 바꿔주고 M+1이 될경우 1로 바꿔주는 것에 신경써주고,

- 문제에서 구현하라는 대로 하시면 됩니다.

- bfs를 통해서 인접한 수 들을 모두 지워주었습니다.

2. 주의사항

- 평균에 대한 특별한 언급이 없어서( 나머지는 버린다던가...) 

- 그냥 double형으로 선언하여 평균을 구해주었더니 맞았습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int N, M, T; // 반지름, 원판당 수, T번 회전시킨다.
int circle[51][51]; // 몇번째 원/ 몇번째 수
bool visited[51][51]; //bfs를 위한 
queue<pair<int, int>> tmpq;
int xi, di, ki;
int xdk[51][3];
bool checkexist = false;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
double tmpsum, tmpn;
bool neighbor = false;

//번호가 xi의 배수인 원판을 di방향(0-시계,1-반시계) ki칸 만큼 회전
void inputs() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> circle[i][j];
		}
	}
	for (int i = 1; i <= T; i++) {
		cin >> xdk[i][0] >> xdk[i][1] >> xdk[i][2];
	}
}
bool boundcheck(int x) {
	return (x >= 1 && x <= N); //원의 범위
}
void rotate(int r) {
	for (int k = 0; k < xdk[r][2]; k++) {
		for (int i = 1; i <= N; i++) {
			if (i % xdk[r][0] != 0) continue; // xi의 배수인 원판만 회전

			int tmpnum;
			if (xdk[r][1] == 0) { // 시계방향
				tmpnum = circle[i][M];
				for (int j = M; j >= 2; j--) {
					circle[i][j] = circle[i][j - 1];
				}
				circle[i][1] = tmpnum;
			}
			else { //반시계방향
				tmpnum = circle[i][1];
				for (int j = 1; j < M; j++) {
					circle[i][j] = circle[i][j + 1];
				}
				circle[i][M] = tmpnum;
			}
		}
	}
}
void initvisit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visited[i][j] = false;
		}
	}
}
void bfs(int x, int y) {
	visited[x][y] = true;
	tmpq.push({x,y});
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (ty == 0) ty = M; //circular
				if (ty == M + 1) ty = 1;
				
				if (boundcheck(tx) && !visited[tx][ty] && circle[tx][ty] == circle[x][y]) {
					tmpq.push({ tx,ty });
					visited[tx][ty] = true;
					neighbor = true;
					circle[tx][ty] = 0; //지우기
					checkexist = true;
				}
			}
		}
	}
	if (neighbor == true) {
		circle[x][y] = 0; 
	} //하나라도 존재하면 여기도 지우기 (시작점)
}
void getsum() {
	tmpsum = 0; tmpn = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] != 0) {
				tmpsum += circle[i][j];
				tmpn++;
			}
		}
	}
}
/*void watchcircle() {
	cout << "\n";
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << circle[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs(); //원판 셋팅
	for(int a=1;a<=T;a++) {
		rotate(a); //회전
		getsum(); // 전체 존재의 수와 그들의 합
		if (tmpn == 0) { cout << 0; return 0; }
		initvisit();
		checkexist = false; // 인접하면서 같은 수가 하나라도 존재하는지 체크
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				neighbor = false; //이웃이 하나라도 있으면 삭제되고 아니면 지워지지 않음
				if (circle[i][j] != 0 && visited[i][j] == false) {
					bfs(i, j);
				} // 인접
			}
		}
		if (checkexist == false) { //인접한 수가 존재하지 않을 때
			double avg = tmpsum / tmpn;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if (circle[i][j] == 0) continue;

					if (circle[i][j] > avg) {
						circle[i][j]--; continue;
					}
					else if (circle[i][j] < avg) {
						circle[i][j]++; continue;
					}
				}
			}
		}
	}
	int resultsum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			resultsum += circle[i][j];
		}
	}
	cout << resultsum;
	return 0;
}