대엉코딩

www.acmicpc.net/problem/17070

- 완전탐색을 문제 조건에 맞게 구현하여 경우의 수를 구하면 되는 간단한 문제이다.

- CASE는 방법에 따른 이동을 순열로 구하면 되는데 현재 파이프가 어떻게 놓여져 있는 지 에 따라 사용 가능한 이동방법이 다르므로 그것만 분류해주면 된다.

-direction 은 0은 가로, 1은 세로 , 2는 대각선이고

 case 1~7의 경우 문제에 표기된 그림의 순서 그대로 사용하였다.

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

int totalcount=0;
int housemap[17][17];
int N;
int x=1;
int y=2;
int dx[3] = { 0,1,1 }; //가로,세로,대각선이동
int dy[3] = { 1,0,1 };
int direction = 0; // 가로,세로,대각선 방향
void startsearch(int x,int y,int d) {
	if (x > N || y > N) return; //종료조건(미도착)
	if (x == N && y == N) { totalcount++; return; } //종료조건(도착
	if (d == 0) {
		if (housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[0], y + dy[0], 0); //case 1
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[2], y + dy[2], 2); //case 2
	}
	else if (d == 1) {
		if (housemap[x + dx[1]][y + dy[1]] != 1) 
		startsearch(x + dx[1], y + dy[1], 1); //case 3
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1)
		startsearch(x + dx[2], y + dy[2], 2); //case 4
	}
	else {
		if (housemap[x + dx[0]][y + dy[0]] != 1)
		startsearch(x + dx[0], y + dy[0], 0); //case 5
		if (housemap[x + dx[1]][y + dy[1]] != 1) 
		startsearch(x + dx[1], y + dy[1], 1); //case 6
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[2], y + dy[2], 2); //case 7
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> housemap[i][j];
		}
	}
	if (housemap[N][N]!=1) { startsearch(x, y, direction); }
	cout << totalcount << "\n";
	return 0;
}

www.acmicpc.net/problem/17281

- 모든 가능한 순열 case를 모두 구해서 야구 시뮬레이션을 돌려서 가장 큰 점수를 반환해주면 됩니다.

-순열 case만 제대로 모두 구한다면 야구게임 자체를 구현하는 것은 어렵지 않습니다.

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

int N;
bool playerordercheck[10];
int playerresult[51][10];
int playerorder[10];
bool location[4]; //1루 2루 3루 를 표시
int resultscore;
int maxscore;
void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for(int j=1;j<=9;j++){
			cin >> playerresult[i][j];
		}
	}
}
void resetlocation() { //1,2,3루 초기화
	for (int i = 1; i <= 3; i++) {
		location[i] = false;
	}
	return;
}
void getscorecheck(int num) {
	for (int i = 3; i >= 1; i--) {
		if (location[i] == true) {
			if (i + num >= 4) { location[i] = false; resultscore++; }
			else { location[i] = false; location[i + num] = true; } //주자 이동
		}
	}
	if (num >= 4) { resultscore++; return; } //홈런인 경우
	else { location[num] = true; return; }
}
int gamestart() {
	resultscore = 0;
	int outcount = 0;
	int playerpointer = 1;
	for (int i = 1; i <= N; i++) { //N이닝동안 반복
		outcount = 0; //이닝별 아웃카운터 초기화
		while (1) { //주자 한명씩 확인
			if (outcount == 3) {
				resetlocation(); //나가있던 주자들 모두 들어옴.
				break;
			}
			if (playerresult[i][playerorder[playerpointer]] == 1) { //1루타
				getscorecheck(1);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 2) {//2루타
				getscorecheck(2);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 3) {//3루타
				getscorecheck(3);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 4) {//4루타
				getscorecheck(4);
			}
			else { //아웃된 경우
				outcount++;
			}
			playerpointer++;
			if (playerpointer == 10) { playerpointer = 1; } //9번 주자까지 다 치면 다시 1번 주자
		}
	}
	return resultscore;
}
void P(int cnt) {
	if (cnt == 10) {
		int tmp = gamestart();
		if (maxscore < tmp) { //각 case가 확정되면 게임을 시작한다.
			maxscore = tmp;
		} 
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (playerordercheck[i] == true) continue;//아직 배정되지 않은 선수라면playerordercheck[i] = true;
		playerordercheck[i] = true;
		playerorder[i] = cnt;
		P(cnt + 1); //모든 순열case을 찾자
		playerordercheck[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	input();
	playerordercheck[4] = true; //4번타자는 1번으로 고정(문제조건) -이미 자리가 배정됨
	playerorder[4] = 1;
	P(2); //1명은 이미 자리 배정이 완료되었음으로... permutation(순열)
	      //순서를 고려해야함
	cout << maxscore << "\n";

	return 0;
}

vector는 오름차순 정렬 되어있어야합니다(이진탐색 기반이기 때문에)

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

그냥 모든 경우의 수를 입력 받은 후 (듣지 못하는 사람) 을 보지 못하는 사람을 입력받을 때 

듣지 못하는 사람 전체와 비교를 하면 시간 초과가 뜹니다 (n,m이 무려 500,000이기 때문에 )

그래서 오랜만에 binarysearch를 직접 구현하여 문제를 해결 하였습니다.

그리고 문제에서 사전 순 배열을 원하였으므로 중간에 sort를 사용하시면 됩니다.

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다. 

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

- 스택 의 LIFO 개념을 인지하기 위한? 문제 인 것 같다.

- 스택에는 오름차순으로 들어간다는 점.

- 저는 원하는 결과 수열을 처음에 입력 받아서 큐에 넣어서 하나씩 비교 하였습니다.

- 스택에 넣는 과정에서 큐의 front에 있는 값과 비교를 해서 같지 않으면 스택에 넣고

- 같으면 스택에 넣었다가 뺀다 (한번은 들어갔다 나와야함.)

- 그 후 뺐을때 queue에서도 pop을 해준다.

- 그리고 그 상태에서 stack.top() 값과 queue.front()의 값이 같다면 또 빼주어야 한다 스택 큐 모두에서

- 그래서 for문을 모두 돈 후에 스택이 비어 있으면 수열이 제대로 완성이 될수 있는 것이므로 성공이고

- 그렇지 않다면 스택을 이용해서 원하는 수열을 만들 수가 없는 것이다.

- 그것을 구분하여 출력해주면 된다.( 안되는 경우에 +,-가 아닌 NO만 출력해야 하므로

- 반복문을 돌면서 출력을 해주면 안된다. 그래서 vector<bool>에 push,pop이 일어날 때 마다

- 차례대로 넣어놓고 마지막에 수열이 완성될 수 있는경우 이를 이용하여 +,-를 출력하였다.

- 자료구조는 자신이 필요하다 싶은, 그리고 더 효율적일 것 같은 자료구조를 선택하면 될거 같다.

- 저도 더 컴팩트하고 쉬운 방법은 없는 지 생각해보겠읍니다.

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

- 입력받은 점을 x좌표 우선비교 하고 출력( 같을 경우는 y좌표를 비교하여 순서대로 출력)

- 문제는 매우 간단한데 

- int형 vector array를 선언해서 (2차원 배열 느낌)

- 입력받은 x,y 를 arr[x].push_back(y) 를 하여 일단 x값 대로 for문을 돌다가

- size가 1 일경우 -> 그대로 출력[0]번째(arr[i][0])

- size가 2 이상이면 -> 그 vector array를 sort하여(y값 오름차순 정렬) 순서대로 출력

@@ 비효율적이다...... 더 컴팩트하게 짤 수있을텐데.. 생각해볼게요.... @@

참조 타입 변수(레퍼런스) 는 별명과 같은 느낌이라고 보면 될 것이다.

c++의 포인터 와 레퍼런스의 차이점을 알아보자.

# 포인터는 null을 가리킬 수 있지만 참조 타입 변수는 null을 가리킬 수 없다.

   - 포인터를 초기화 하지 않거나 null을 가리키고 있는 포인터에 접근 했을 때

     발생하는 에러가 참조 타입 변수에서는 나타나지 않는다.

# 참조 타입 변수는 선언과 동시에 초기화 하지않으면 컴파일 오류가 발생한다.

# 포인터는 * , -> 등의 포인터 연산자를 통해서 접근 해야 하지만 참조 타입 변수는

   마치 지역변수 처럼 접근할 수 있다.

# 참조 타입 변수는 초기화 과정에서만 값을 할당 할 수 있고 이후에 다시 할당을

   시도 할 경우 컴파일 에러가 발생한다. 하지만 포인터 변수는 참조 대상을 언제든지 변경할 

   수 있다.