대엉코딩

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/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;
}

www.acmicpc.net/problem/2776

1. 풀이방법

- 시간제한은 2초 

- N,M 모두 최대 1,000,000 이므로 M배열의 각각의 원소에 대해 N배열을 선형탐색하면 시간초과가 발생

- N배열을 정렬하고 (c++ stl에서 제공하는 sort함수는 O(nlogn)을 보장해줍니다.

- 그후 M배열 각각의 원소로 N배열에 대해서 이분탐색을 진행 하시면 됩니다.

- 재귀, 반복문 다 구현 가능하며 저는 이 문제는 while문으로 구현하였습니다.

2. 주의사항

- 시간초과

3. 나의코드

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



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t, n, m;
	cin >> t;
	while (t--) {
		cin >> n;
		vector<int> narr(n);
		for (int i = 0; i < n; i++) cin >> narr[i];
		sort(narr.begin(), narr.end()); // 정렬

		cin >> m;
		vector<int> marr(m);
		for (int i = 0; i < m; i++) cin >> marr[i];

		for (int i = 0; i < m; i++) { //수첩 2
			int lowindex = 0; int highindex = n - 1;
			while (1) {
				if (lowindex > highindex) { cout << 0<<"\n"; break;}
				int midindex = (lowindex + highindex) / 2;
				if (narr[midindex] == marr[i]) {cout << 1 << "\n"; break;}

				if (narr[midindex] > marr[i]) {
					highindex = midindex - 1;
				}
				else {
					lowindex = midindex + 1;
				}
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/2422

1. 풀이방법 

- 1~N까지의 모든 아이스크림 중 3개를 만드는 모든 조합을 골라서

- 이게 가능한지 (최악의 조합에 속하는 것이 없는 지) 를 확인 후 방법의 수를 증가시켜 주면되는 문제였습니다.

- 조합을 만드는 것은 어렵지 않았고, 처음에는 최악의 조합을 <pair<int,int>>로 만들어

- 반복문을 통해서 psice() 가능한 아이스크림조합인지를 확인 했었는데, 시간초과가 발생하였습니다.

- 반복문 탐색 중 정지 조건 break 를 걸어 주고 난 뒤 제출해도 역시 시간초과 였습니다.

- 그래서 이차원배열을 선언하여 두 아이스크림이 최악의 조합인지를 O(1) 시간에 확인할 수 있도록

- 수정하여 제출 하였더니 통과 되었습니다.

- 그래프 구현방법 중 인접행렬 방식( 두 노드가 인접했는지 확인하는 것이 매우 빠르다라는 장점)

- 으로 부터 나온 생각으로 구현하였습니다.

2. 주의사항

- 문제 자체는 쉬웠지만, 시간을 단축하는 부분에 있어 특이점이 있는 것 같아 포스팅으로 남깁니다.

3. 나의코드 

- 주석 부분은 반복문을 통한 탐색 부 입니다.

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

int N;
int M;
int t1, t2;
// vector<pair<int, int>> worstice;
bool wi[201][201];
vector<int> icearr;
int pscase = 0;

/*bool psice() {
	for (int i = 0; i < worstice.size(); i++) {
		int tmp = 0;
		for (int j = 0; j < icearr.size(); j++) {
			if (icearr[j] == worstice[i].first || icearr[j] == worstice[i].second) {
				tmp++;
			}
			if (tmp == 2) return false;
			if (icearr[j] > worstice[i].second) break;
		}
	}
	return true;
}*/
bool ps() {
	if (wi[icearr[0]][icearr[1]] == true || wi[icearr[0]][icearr[2]] == true
		|| wi[icearr[1]][icearr[2]] == true) return false;
	else return true;
}

void makeice(int index,int cnt) {
	if (cnt == 3) {
		if (ps()) {
			pscase++;
		}
		return;
	}
	for (int i = index; i <= N; i++) {
		icearr.push_back(i);
		makeice(i+1,cnt + 1);
		icearr.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2;
		// worstcase.push_back({t1,t2});
		wi[t1][t2] = true;
		wi[t2][t1] = true;
	}
	makeice(1,0);

	cout << pscase << "\n";

	return 0;
}

www.acmicpc.net/problem/1620

1. 풀이방법

- 포켓몬도감을 입력받아 찾으면 되는 문제입니다.

- 첫번쨰 문제는 입력이 숫자 일수도, 포켓몬 이름 일수도 있다는 것입니다.

- 이름의 경우 알파벳만으로 이루어져있다고 했으므로, 입력받은 문자열의 첫글자가 알파벳인지 숫자인지만

- 구분해서 구하여주었습니다.

2. 주의사항

- 처음에 그냥 선형탐색으로 짰는데, 이 경우 최대연산 수가 대략 10,000,000,000이 되므로 시간조건을 만족x

- 결국 이분탐색을 이용하고자 하였고 그러려면 알파벳순으로 정렬을 해야 하는데 , 그러면

- index가 섞이기 때문에 따로 알파벳입력이 들어왔을 떄를 위한 index도 가지고 있는 배열을 선언하였습니다.

- 숫자가 들어올 경우 vector<string> 을 통해 index를 구해서 바로 접근 하였고,

- 알파벳으로 들어올 경우 vector<pair<string,int>> 를 정렬해놓은 것을 통해 이분 탐색으로 찾았습니다.

3. 나의코드

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

vector<string> dokam;
vector<pair<string, int>> dokamname; //알파벳이 입력되었을 경우 이분탐색을 위한 !
string tmps;
void find(int bot, int top) {
	if(bot>top) return;
	int mid = (bot + top) / 2;
	if (tmps == dokamname[mid].first) { cout << dokamname[mid].second << '\n'; return; }
	else if (tmps < dokamname[mid].first) { find(bot, mid - 1); }
	else { find(mid + 1, top); }
}
bool compare(pair<string, int> &a, pair<string, int> &b) {
	if (a.first < b.first) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		dokam.emplace_back(s);
		dokamname.push_back({ s,i });
	}
	sort(dokamname.begin(), dokamname.end(), compare);
	while (m--) {
		int result = 0;
		cin >> tmps;
		if (tmps[0] >= '0'&&tmps[0] <= '9') { //숫자일경우
			int deci = 1;
			for (int i = tmps.length() - 1; i >= 0; i--) {
				result += deci * (int)(tmps[i] - '0');
				deci *= 10;
			}
			cout << dokam[result-1] << "\n";
		}
		else { //선형탐색으로는 시간초과 -> 이분탐색 진행
			find(0,n-1);
		}
	}

	return 0;
}