프밍노트

ctrl +, 또는 ctrl + t  전체 페이지중 이동

ctrl +. :빠른작업  리팩토링

ctrl +j :  자동완성 표시

ctrl + r +r : 함수나 변수 명을 한번에 변경

ctrl + k +d : 줄 자동 정렬

ctrl + k +c  : 주석 으로 변경

ctrl + k + u : 주석 해제 - 하나씩 해제

ctrl + m + o :  정의 부분만 보이기

f12 : 정의 탐색

shift +f12 : 모든 참조 찾기

디버그 중 중단점이후

f11 : 한단계씩 코드 실행 - 함수내부까지 들어감

f10 : 프로시저  단위 실행

cpp 로 백준 문제를 풀다보면 여러가지 팁을 얻을수 있는데

그중에 해당 코드를 볼수있는데

std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);

해당 코드들은 cpp 입출력 성능을 최적화 하기위해 사용되는 설정들이다.

std::ios::sync_with_stdio(false);

는 cpp iostream 과 c의 stdio 를 동기화 하는 설정을 해제한다.

기본적으로 cpp는 c의 printf scanf 등과 호환성을위해 동기화 되어있다.

동기화를 해제하면 cin과 cout 속도가 빨라지지만 printf scanf 와 같이쓸수없다.

std::cin.tie(0); 또는std::cin.tie(nullptr); 

cin과 out의 묶음을 해제한다

기본적으로 cin을 사용하기 전에 cout 버퍼를 flush 하는 동작이 묶여있는데 이를 해제한다.

입력받기전에 출력 버퍼를 비울필요가 없어져서 속도가 향상된다.

std::cout.tie(0) 또는 std::cout.tie(nullptr)

cout의 tie를 해제한다.

cin.tie(0)와 비슷한역활이다.

tie는 cpp의 입출력 스트림에서 두스트림을 묶어주는 역활을 하는데

cout<<"반가워"

cin>>name;

은  내부적으로 사이에 cout.flush 가들어간다. 

하지만 tie(0)을 해서 해제하면 사이에 flush없이 바로 입력을 받는다.

#include<iostream>
using namespace std;


int SugarSalt()
{
	int data = 0,answer=0;
	cin >> data;

	while (data!=0)
	{
		if (data % 5 == 0) {
			data -= 5;
			answer++;
		}
		else if (data - 3 >= 0) {
			data -= 3;
			answer++;
		}
		else {
			answer = -1;
			break;
		}
	}
	return answer;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(NULL);
	cout<<SugarSalt();

	return 0;
}

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다.

최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다.

해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.

간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면

프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,.

다시 문제로 돌아와

"켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.

코드르 보면서 설명해 보자

#include<iostream>
#include <queue>
#include<tuple>
#include<vector>
#include <unordered_map>
using namespace std;
unordered_map<int, vector<pair<int, int>>> Spninmap;
unordered_map<int, bool> maps;
//unordered_map<int, int> sp_map;
int gagungchi = 0;
int k = 0;
priorityqueue<pair<int, int>> q;
void minSpningTree() {
    int a = 0, b = 0;
    int n = 0, m = 0, v = 0;
    while (true)
    {
        Spninmap = *new unordered_map<int, vector<pair<int, int>>>();
        maps = *new unordered_map<int, bool>();
        gagungchi = 0;
        k = 0;
        cin >> a >> b;
        if (a == 0 && b == 0) return;
        //그래프로 섬들을 만들어준다.
        for (int i = 0; i < b; i++) {
            cin >> n >> m >> v;
            Spninmap[n].push_back(make_pair(-v, m));
            Spninmap[m].push_back(makepair(-v, n));
            k += v;
        }
        //시작위치 n 으로 잡고 갈수있는 간선들을 받아준다.
        for (auto i : Spninmap[n]) {
            q.push(i);
        }
        //현재위치 탐색완료
        maps[n] = true;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            if (maps[c.second] == true) continue;
            maps[c.second] = true;
            //전력 업데이트
            gagungchi += -(c.first);
            //현재 갈수있는 간선들 추가
            for (auto i : Spninmap[c.second]) {
            //갔던섬이면 빼주기
                if (maps[i.second] == true) continue;
                q.push(i);
            }
        }
        cout << k - gagungchi<<"\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(NULL);
    minSpningTree();
    return 0;
}

종이 자르기 문제

위처럼 종이가 주어지면 흰색 부분과 파란 부분을 분리하여 자르되

정사각형이 되도록  자르는게 목적이다.

해당 문제는 한칸씩 확인하며 정사각형을 측정한다면

틀렸을때 최적이 될 정사각형을 찾아야 하기에

중복 되는 탐색이 매우 많을 것 같은 느낌이다.

이문제는 모든 사각형을 정사각형으로 자른다가 핵심이라고 생각한다.

가장 큰 종이에서 나올 수 있는 최대 정 사각형은 4개 그 안에서도 4개로 오히려 쪼개면서 계산하는 것이다.

사실 문제에서 내용을 이미지로 간단하게 설명해준다.

위 이미지 순서대로 큰거 자르고 문제 있는 부분만 자르면서 들어가는식으로 풀면된다

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

vector<vector<int>> arrya;
int color[2] = {0,0};

//재귀함수
void Recursive(int size, int x, int y) {
	int  a = arrya[x][y];
	bool is_same = false;
	
    //해당 크기의 정사각형 완전탐색하며 문제있는지 확인
    for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arrya[i][j] != a)
			{
				is_same =true;
				break;
			}
		}
		if (is_same)break;
	}
    //정사각형 4개로 나눠서 재귀
	if (is_same) {
		size /= 2;
		Recursive(size, x, y);
		Recursive(size, x + size, y);
		Recursive(size, x, y + size);
		Recursive(size, x + size, y + size);
	}
	else {
    //다채워졌다면 사각형이니 +1
		color[a]++;
	}





}



void solution() {
	int size;
	cin >> size;
	arrya = vector<vector<int>>(size);

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			int z = 0;
			cin >> z;
			arrya[i].push_back(z);
		}
	}
	Recursive((size ), 0, 0);
	cout << color[0] << "\n"<<color[1];




}

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


	solution();
	return 0;
}

알고리즘의 기초 중 기초? 라고 볼수있는 flood fill 알고리즘을 알아보자

위키백과 에선 플러드필 혹은 시드필 이라고 명명다.

내생각엔 알고리즘 의 기본 내용은 정말 간단하다

영역을 탐색하고 조건에 맞게 채우면 끝이다.

위키백과에서 설명하는 gif 다.

https://en.wikipedia.org/wiki/File:Recursive_Flood_Fill_4_(aka).gif

4방향 상하좌우 만 순서대로 탐색하며 DFS로 재귀함수를 사용해서 탐색하였을때 위 gif 처럼 차오른다.

enum EMap
{
	Wall,
	Empty,
	Fill
};


// 현재위치에서 이동할 방향
int NextMover[4][2] = { {0,-1} ,{-1,0} ,{1,0},{0,1} };

//채우기 알고리즘 DFS
void FloodFill(vector<vector<EMap>>& map, int x, int y)
{
// 현재 위치 채워주기
	map[x][y] = EMap::Fill;
    
	for (const auto* Move : NextMover) {
	
    	int movex = x + Move[0],
			movey = y + Move[1];
	    //방향 이 배열을 나가지 않는지 확인
    	if (movex <0 || movex >= map.size() || movey < 0 || movey >= map[0].size()) continue;
	    //만약 비워져있다면 탐색 시작
    	if (map[movex][movey] == EMap::Empty) {
			FloodFill(map, movex, movey);
		}
	}

}


vector<string> images = { "■","□","◆"};


int main() {
	vector<vector<EMap>> VectorMap = {
		 {Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Wall,Wall}
		,{Empty,Empty,Empty,Wall,Empty} };

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}


	int PlayerX = 0, PlayerY = 0;
	FloodFill(VectorMap, PlayerX, PlayerY);

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}
}​

컴퓨터 그래픽스나 이미지 처리에서 특정 영역을 채우는 데 사용되는 알고리즘이다.

페인트 프로그램에서 특정 픽셀을 클릭했을 때 해당 색상을 기준으로 연결된 영역 전체를 새로운 색으로

채우는 기능에 사용할수있다

해당 알고리즘에서는 채우는게 목적이지만

BFS나 DFS 탐색으로 같은 영역을 탐색하는건 다른 알고리즘에서도 정말 많이쓰인다.

일전에 작성했던 석유시추 역시 BFS로 탐색하며 해당 영역을 찾아낸다.

간단하고 기초적인 알고리즘이지만 정말 많이 쓰인다.

https://programing-note.tistory.com/entry/%EC%84%9D%EC%9C%A0%EC%8B%9C%EC%B6%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4LV2

글쓴이는 일전에 다이렉트 x11로 땅따먹기 게임을 만들때 처음 사용했다.

석유 시추 bfs 로  석유를 미리 번호를 지어두는 작업이 필요하다고 생각한다.

그리고 좌측부터 1자로 내리면서  제일큰걸 확인해보면 되는문제라 생각한다.

해당문제라면

1 [ 0,0], [ 0,1] [ 0,2] [ 0,3] [ 0,4]....  12

2 [2,0] [ 2,1] [ 2,2] 3

....

재귀로 bfs 탐색을하며 해당처럼 데이터를 모아준다

모아두었기때문에 한번 건들인 석유를 두번 캐지않을수있다.

#include <string>
#include <vector>
#include <unordered_map>
#include<queue>
using namespace std;


static int const nextland[4][2]{ {0,1}, {1,0}, {-1,0}, {0,-1} };

//석유 룰 묶어주는 함수
void find_oil(vector<vector<int>>& land, int x, int y, int& oil_count, unordered_map<int, int>& oil_monny) {
	queue<tuple<int, int>> nextxy;
	nextxy.push(make_tuple(x, y));
	land[x][y] = oil_count;
	oil_monny[oil_count]++;
	while (nextxy.size() != 0)
	{


		tuple<int, int> nxy = nextxy.front();
		int xy[2]{ get<0>(nxy),get<1>(nxy) };
		nextxy.pop();


		int x, y = 0;
		for (auto arrow : nextland) {
			y = arrow[1] + xy[1];
			x = arrow[0] + xy[0];
			if (x >= 0 && x < land.size() && y >= 0 && y < land[0].size() && land[x][y] == 1) {
				land[x][y] = oil_count;
				oil_monny[oil_count]++;
				nextxy.push(make_tuple(x, y));
			}
		}
	}
	oil_count++;
}

int solution(vector<vector<int>> land) {
	int answer = 0;
	int oil_count = 2;
	unordered_map<int, int> oil_monny;

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[i].size(); j++) {
			if (land[i][j] == 1) {
            
            //석유를 한번에 모아주고 그 모은 석유의 벨류 탐색
				find_oil(land, i, j, oil_count, oil_monny);
			}
		}
	}


	for (int i = 0; i < land[0].size(); i++) {
		vector<bool>c(oil_count - 2);
		int b =0;
		for (int j = 0; j < land.size(); j++) {
        //아래로 내리면서 기름 있는땅 찾고 만약 탐색 안되었으면
			if (land[j][i] > 1 && (c[land[j][i] - 2] == false)) {
            //탐색완료 표시
				c[land[j][i] - 2] = true;
				// 현재 벨류 추가
                b += oil_monny[land[j][i]];
			}
		}
		if (answer < b) {
			answer = b;
		}
	}

	return answer;
}

알고리즘 문제 해결전략 1편 발췌

예전에 해당 책을 읽다 기억에 오래 남았던 문제 한가지가

해당문제다 결과값이  ㅡ2 이여야 할거같지만
위 이미지처럼 4294967294가 나온다.

해당값이 나오는 이유를 아래를 보기전에 생각해보자




a: unsigned char   , b: short
                   (a  + b ) :int    *  c : int
         (a+b) *c : int  + d unsigned int
           (a+b)*c+d : unsigned int

마지막 전체 수식의 답을 계산하는부분.
 d를 더하면서 전체 수식이 부호없는 정수형으로 변환 되는데 

-2 는 자료형에 담기에 너무작은 값이기 때문에 오버플로우가 일어나
값이 강제로 부호없는 정수로 캐스팅 되는 과정에서 큰값이 된다.

그렇기때문에 문제처럼 
unsigned를 쓸때 auto캐스팅을 조심하는게 좋다