구현

ppparkta·2022년 3월 29일

알고리즘

목록 보기

2/10

*이 글은 2022년 1월~2월 노션으로 진행한 알고리즘 스터디를 옮긴 글입니다. 나동빈 저자 이것이 취업을 위한 코딩테스트다를 사용해 학습했습니다.

220204 구현 내용정리

<구현에서 다루는 내용>

완전탐색: 모든 경우의 수를 다 계산하는 해결 방법
시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형
구현 알고리즘을 다룰 때 완전탐색과 시뮬레이션 유형이 함께 출제되는 경우가 많으므로 구현 유형과 완전탐색, 시뮬레이션 유형은 비슷한 점이 많음

<구현 시 고려해야 할 메모리 제약사항>

C/C++ 정수형 종류에 따른 범위

정수형 종류	자료형의 크기	자료형의 범위
int	4byte	-2,147,483,648~2,147,438,647
long long	8byte	-9,223,372,036,854,775,808~9,223,372,036,854,775,807
biginteger(class)	가변	no

단, 검색 비허용하는 알고리즘 대회에서는 8byte이상의 범위를 요구하는 경우가 드묾
방향 사용해서 푸는 문제의 경우 dx/dy배열 미리 선언하면 연산하기 편함

220204 상하좌우

풀이
1. bool 타입 배열 만들어서 입력받은 n만큼 true로 만듦
2. 현재위치 가리키는 커서 생성
3. RLUD연산 만들어서 연산수행 후 현재 위치가 false면 연산 무시
4. true면 연산 수행(커서이동)
5. 문제: 연산 입력받을 때 문자를 어떻게 끊을 것인가?←구현문제인 이유인 듯
6. 일단 문자열 하나 받고 그냥 사이즈대로 반복하는 식으로 구현했는데 문제에서 요구하는건 숫자를 받지 않고 공백으로 구분하는 방식인듯. 수정이 필요한가...?

코드

#include<iostream>
using namespace std;

bool datas[100][100] = {};
class cursor {
public:
	int x;
	int y;
	cursor() {
		x = 0;
		y = 0;
	}
};

void r(cursor *c) {
	if (datas[c->x][c->y + 1]==true) {
		c->y += 1;
	}
}
void l(cursor* c) {
	if (datas[c->x][c->y -1 ] == true) {
		c->y -= 1;
	}
}
void u(cursor* c) {
	if (datas[c->x-1][c->y] == true) {
		c->x -= 1;
	}
}
void d(cursor* c) {
	if (datas[c->x+1][c->y ] == true) {
		c->x += 1;
	}
}

int main() {
	int n;
	string x;
	cin >> n >> x;
	cursor* c = new cursor();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			datas[i][j] = true;
		}
	}
	for (int i = 0; i < x.size(); i++) {
		switch (x[i]) {
		case 'R': r(c); break;
		case 'L': l(c); break;
		case 'U': u(c); break;
		case 'D': d(c); break;
		}
	}
	cout << c->x + 1 << " " << c->y + 1;
	return 0;
}

220206 시각 → 다른 방식으로도 풀어보기

풀이 완전탐색 해야하는 문제같음! 큰 수부터 경우를 차례대로 지우면서 경우가 하나도 남지 않을때까지 프로그래밍하는 방식으로 접근함
1. 시간:분:초 중 앞에서부터 3이 들어가는 수를 먼저 탐색함.
2. 시간에 3이 들어가는 경우 00분00초~59분59초까지 모두 3이 포함되므로 60*60의 경우가 생김
3. 시간에 3이 들어가는 경우를 제외하고 분에 3이 들어가는 경우→ 3,13,23,30,31,32,33,34,35,36,37,38,39,43,56 총 15*60의 경우가 생김.
4. 시간과 분에 3이 들어가는 경우를 제외하고 초에 3이 들어가는 경우→3,13,23,30,31,32,33,34,35,36,37,38,39,43,56. 15개 경우임. 45*15

코드

#include<iostream>
using namespace std;

int main() {
	int n,answer=0;
	cin >> n;
	for (int i = 0; i <= n; i++) {
		if (i == 3 || i == 13) {
			answer += 60 * 60;
		}
		else {
			answer += (15 * 60 + 45 * 15);
		}
	}
	cout << answer;
	return 0;
}

220206 왕실의 나이트

풀이
1. 문자열로 값 받아서 각 자리수대로 변수 x,y에 저장함(문자는 97빼고 1더해서)
2. 정답변수 만들어서 조건 맞을 때마다 1씩 더해줌
3. x,y를 다른 변수에 저장한 뒤 x값에 2 +-한 값이 범위 내인지 판단한 후 y값에 1+-한 값이 범위 내인지 판별→true면 정답에 1씩 더해줌
4. 같은 방식으로 y값에 2 +-한 값이 범위 내인지 ...
5. 정답변수 출력

코드(수정 전)

#include<iostream>
using namespace std;

int main() {
	int x, y, answer=0;
	string s;
	cin >> s;
	x = s[0] - 96;
	y = s[1];
	if (x - 2 >= 1) {
		if (y - 1 >= 1)answer += 1;
		if (y + 1 <= 8)answer += 1;
	}
	if (x + 2 <= 8) {
		if (y - 1 >= 1)answer += 1;
		if (y + 1 <= 8)answer += 1;
	}
	if (y - 2 >= 1) {
		if (x - 1 >= 1)answer += 1;
		if (x + 1 <= 8)answer += 1;
	}
	if (y + 2 <= 8) {
		if (x - 1 >= 1)answer += 1;
		if (x + 1 <= 8)answer += 1;
	}
	cout << answer;
	return 0;
}

코드(수정 후)

#include<iostream>
using namespace std;

int main() {
	int x, y, answer=0;
	string s;
	cin >> s;
	x = s[0] - 96;
	**y = s[1] - 48;**
	cout<<"문자열 처리 x:" << x << " y:" << y << endl;
	if (x - 2 >= 1) {
		if (y - 1 >= 1)answer += 1;
		if (y + 1 <= 8)answer += 1;
	}
	if (x + 2 <= 8) {
		if (y - 1 >= 1)answer += 1;
		if (y + 1 <= 8)answer += 1;
	}
	if (y - 2 >= 1) {
		if (x - 1 >= 1)answer += 1;
		if (x + 1 <= 8)answer += 1;
	}
	if (y + 2 <= 8) {
		if (x - 1 >= 1)answer += 1;
		if (x + 1 <= 8)answer += 1;
	}
	cout << answer;
	return 0;
}

틀린 이유
- 문자열을 숫자로 처리할 때 알파벳의 경우 잘 처리했는데 숫자는 문자열을 그대로 int형 변수에 갖다 씀. 그 결과 숫자의 아스키코드가 변수에 저장되었고 내가 짠 로직이 수행되지 않음.
- 알파벳을 처리할 때와 마찬가지로 0의 아스키코드 48을 빼줘서 문자열을 처리했음. a/A아스키코드는 외우고 있었는데 이제 0도 외워야할 듯 함... 다른 방법이 있을까?
- 서치해보니 sstream stl 사용하여 변환하는 방법이 나옴. 근데 이거 내 코드에 적용해보니까 쓰레기값나옴 -_-...
```
#include <iostream>
**#include <sstream>**

int main()
{
	int i = 0;
	std::stringstream ssInt("123");
	ssInt >> i;

	if (!ssInt.fail())
		std::cout << ssInt.str() << std::endl;

	return 0;
}
```

220206 게임 개발

풀이
- 구현방향 갈피가 안 잡혀서 인터넷 참고함
- 구현방식 이해 후 직접구현

코드(참고)

#include <iostream>
using namespace std;

int map[50][50];

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

int main(void) {
	int move = 1;
	int m, n, x, y, d;
	cin >> m >> n;
	cin >> x >> y >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		map[x][y] = 1;
		for (int i = 1; i <= 4; i++) {//4개 방향 회전
			int nd = (d + i) % 4; //탐색할 방향
			//탐색할 위치
			int nx = x + dx[nd];
			int ny = y + dy[nd];
			if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 0) { //전진 가능하다면 위치와 방향 업데이트
				d = nd;
				x = nx; y = ny;
				move++;
				break; //for문에 대한 break
			}
			if (i == 4) { // 모든 면이 바다라면
				d = nd; //바라보는 방향 유지
				nd = (nd + 2) % 4; //뒤로 갈 때의 방향 얻기
				nx = x + dx[nd];
				ny = y + dy[nd];
				if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 1) { //뒷방향도 바다라면
					cout << move;
					return 0;
				}
				else { //뒷 방향 갈 수 있다면
					x = nx; y = ny;
					move++;
				}
			}
		}

	}
}

ppparkta

겉촉속촉

이전 포스트

그리디

다음 포스트

구현

알고리즘

220204 구현 내용정리

220204 상하좌우

220206 시각 → 다른 방식으로도 풀어보기

220206 왕실의 나이트

220206 게임 개발

그리디

220612 그리디, 구현

0개의 댓글