https://programmers.co.kr/learn/courses/30/lessons/49994

문제 설명
U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기
위의 조건에 따라서 간선을 움직이며 총 방문 길이를 구하는 문제.
지하철역으로 따지면 지하철역을 방문했냐는 것을 묻는게 아닌 총 역에서 역을 간 횟수(길이)를 구하는 문제

	해당 숫자들이 움직인 거리이며 만약 노드로 체크를 했다면 (0,1)좌표에 방문을 했다고 표시를 한다.
	해당 8,9는 이미 왔던 곳이기 때문에 방문길이 플러스 하지 않는다.

조건
1. 방문 했던 노드 간선을 다시 간다면 방문 길이에 포함 되지 않는다.
2. x(-5.5) y(-5,5) 범위 내에서만 움직일 수 있다.

문제 풀이
당연히 실수로 각 노드를 visit배열로 처리해서 풀었음..ㅠ (리뷰를 보니 다 똑같이 실수를 했음)
1. 방문 간선을 체크한다.(4차원 배열로 처리)
2. 방문가능한 노드 검사 (x,y 좌표 -> 0미만 11초과 X)
*-5->0으로 0,0가 맨왼쪽이라는 가정하에 풀었음) 따라서 시작점은 5,5 

방문 간선 체크 방법(사차원 배열처리)

map[시작x좌표][시작y좌표][도착x좌표][도착y좌표] = 1
map[도착x좌표][도착y좌표][시작x좌표][시작y좌표] = 1

코드

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

bool map[11][11][11][11] = {false,};
int solution(string dirs) {
    int answer = 0;
    int curX = 5;
    int curY = 5;
    for(int i =0 ; i < dirs.size(); i++){
        char dir = dirs[i];
        if(dir == 'U') {
            if(curY+1 < 11) {
                if(map[curX][curY][curX][curY+1] != 1) {
                    // 간선의 방문여부를 체크해야 하기 때문에 양방향 다 방문으로 체크
                    map[curX][curY][curX][curY+1] = 1;
                    map[curX][curY+1][curX][curY] = 1;
                    answer++;
                }
                curY++;
            }
        }

        else if(dir == 'D') {
            if(curY-1 >= 0) {
                if(map[curX][curY][curX][curY-1] != 1) {
                    map[curX][curY][curX][curY-1] = 1;
                    map[curX][curY-1][curX][curY] = 1;
                    answer++;
                }
                curY--;
            }
        }

        else if(dir == 'L') {
            if(curX-1 >= 0) {
                if(map[curX][curY][curX-1][curY] != 1) {
                    map[curX][curY][curX-1][curY] = 1;
                    map[curX-1][curY][curX][curY] = 1;
                    answer++;
                }
                curX--;
            }
        }

        else if(dir == 'R') {
            if(curX+1 < 11) {
                if(map[curX][curY][curX+1][curY] != 1) {
                    map[curX][curY][curX+1][curY] = 1;
                    map[curX+1][curY][curX][curY] = 1;
                    answer++;
                }
                curX++;
            }
        }
    }
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/12905

문제 설명
1로 구성된 가장 큰 정사각형의 넓이를 구하는 문제이다.

위와 같은 경우 답은 9이다.

문제풀이 방법
***DP문제****
우측 맨밑 좌표를 기준으로 넓혀가는 느낌...!

1. 0이면 패스한다.
2. 1이 나오면 왼쪽, 위, 왼쪽 대각선의 요소들을 검사한다.

Step1
- 1이 나오면 왼쪽, 위, 왼쪽 대각선의 요소들을 검사한다.
- 왼쪽, 위, 왼쪽 위 대각선에 값이 없으면 pass
- 0이 나오면 X
- 왼쪽, 위, 왼쪽 위 대각선에 값이 1이면 검사했던 값의 최소 값에서 +1 해준다.

Step2
- 해당 값은 정사각형의 한 번의 길이가 된다. 따라서 제곱을 하면 닶.

점화식
board[i][j] = min(board[i-1][j],board[i[[j-1],board[i-1][j-1]) +1;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[1001][1001] = {0,};
int solution(vector<vector<int>> board)
{
    int answer=board[0][0];
    int max = -987654321;
    for(int i = 1 ; i < board.size() ; i++){
        for(int j = 1 ; j < board[i].size() ; j++){
            if(board[i][j]==0)
                continue;
            if(board[i][j]==1){
                board[i][j] = min({board[i-1][j],board[i-1][j-1],board[i][j-1]})+1;
            }
            
            if(board[i][j] > max) {
                max = board[i][j];
            }
        }
    }
    if(max==-987654321){
        answer = board[0][0];
    }else{
        answer = max*max;
    }
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    //cout << "Hello Cpp" << endl;

    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/87390

문제설명

• n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
• i = 1, 2, 3, …, n에 대해서, 다음 과정을 반복합니다.
• 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
• 1행, 2행, …, n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
• 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], …, arr[right]만 남기고 나머지는 지웁니다.

문제 풀이
1. 말이 어렵지만 위의 시뮬레이션처럼 구현하게 되어있음. 해당 시뮬레이션의 각 좌표는 max(r,c)+1 임
2. 평탄화 했을 시 각 행렬은 i/n, i%n으로 나타낼 수 있음.

소스코드

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

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    for(long long i = left ; i<=right ; i++){
        answer.push_back(max(i/n,i%n)+1);
    }
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/17680

문제설명

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
cache hit일 경우 실행시간은 1이다.
cache miss일 경우 실행시간은 5이다.

LRU(Least Recently Used) 알고리즘

시도) 네이버 로그인

캐시 메모리에 있을 경우

시도) aaa.com 시도

캐시 메모리에 없을 경우

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.cache hit일 경우 실행시간은 1이다.cache miss일 경우 실행시간은 5이다.1. 만약 cachSize가 0이면 전체 시티*5
2. 소문자로 모두 변경
3. 해당 값을 찾으면 해당 값을 지워주고 새로 추가해주며 answer++ 해준다.
4-1. 해당 값을 못찾았는데 cache가 여유있다.  그냥 pushBack, answer+5
4-2. 해당 값을 못찾았는데 cache가 없다. 맨 처음 값 삭제 후 pushBack, answer+5

소스코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    if(cacheSize == 0){
        answer = cities.size()*5;
        return answer;
    }
    vector<string> cache;
    for(int i =0; i<cities.size();i++){
        string check = cities[i];
        transform(check.begin(),check.end(),check.begin(),::tolower); //소문자 변환
        auto it = find(cache.begin(), cache.end(), check);
        //찾으면 it(이터레이터가 끝까지 안가면 해당 값을 찾은 것)
        if(it != cache.end()){
            cache.erase(it);
            cache.push_back(check);
            answer++;
        }else{
            //캐시에 빈자리 있음
            if(cache.size() < cacheSize){
                cache.push_back(check); //마지막에 넣어준다.
            //캐시에 빈자리 없음 
            }else{
                cache.erase(cache.begin()+0); // 젤 처음 지우고
                cache.push_back(check); //마지막에 넣어준다.
            }
            answer+=5;
        } 
    }
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/12981

문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
그냥 끝말잇기임.
사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

문제풀이
1. 맵 형식으로 구현
2. 처음부터 틀린 경우는 없으므로 tank부터 맵에 넣고 시작
3. 맵에 단어가 이미 있거나 뒷 단어의 맨앞 글자와 현재단어의 맨뒷 단어 비교
4. 리턴 방식 : 

map 자료구조 사용

ex) ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]

return 방식
1. 사람 구하기 : (i%n)+1
2. 순서 구하기 : (i/n)+1

소스코드

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
vector<int> solution(int n, vector<string> words) {
    map<string, int> word; //map형식으로 구현
    word[words[0]]++;
    for(int i=1; i<words.size(); i++){
    //이미 단어가 있거나, 앞 뒤 단어 비교 틀린 것 찾기
        if(word[words[i]] || words[i].front() != words[i-1].back())
            return {(i%n)+1,(i/n)+1};
        word[words[i]]++;
    }
    return {0, 0};
}

형 변환 정리

www.acmicpc.net/problem/2580

참고 :yabmoons.tistory.com/88

코드

• Step1) ROW, COL 배열에 각각 True, False값을 넣어준다
  • ROW[i][map[i][j]]=true
    • 각 행에 사용한 숫자(=map[i][j]))를 체크해준다
  • COL[j][map[i][j]]=true;
    • 각 열에 사용한 숫자를 체크한다.
  • Square[(i/3)*3 + (j/3)][map[i][j]] = true
    • (i/3)*3 + (j/3)
      
      • (i,j)가 상위 표에서 어느 위치에 있는지 알려줌
        • ex) (4,2)
          • (4/3) * 3+ 2/3 = 3 번째 위치
        • ex) (7,7)
          • (7/3)*3 + 7/3 = 8번째 위치
  • dfs에서의 cnt
    • int x = cnt/9;
      • cnt=0~8
        • x=0
        • y=0~9
      • cnt= 9~17
        • x=1
        • y=0~9
      • cnt=18~26
        • x=2...
        • y=0~9...
    • 따라서 cnt=81 이란 것은 (0,0)부터 (9,9)까지 다 돈 것이다.
• 중요한 검색 로직!!

if (map[x][y] == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
			{

• 재귀 로직
  • 들어갈 수 있는 가장 작은 i 값을 넣고 다 뺀뒤에 다 그다음 값을 넣고 돌리고 하는 식..!

row[x][i] = true;
col[y][i] = true;
square[(x / 3) * 3 + (y / 3)][i] = true;
map[x][y] = i;
dfs(cnt + 1);
map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
square[(x / 3) * 3 + (y / 3)][i] = false;

• map[i][j] = 0 을 만났을 때
• 해당 가로줄 검사
• 해당 세로줄 검사
• 해당 블럭(9개중1개) 검사
  • 가능한 숫자 입력

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 9
/*
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0  
*/

using namespace std;

void solution()
{

}
int map[9][9];
bool row[9][9];
bool col[9][9];
bool square[9][9];
void Print()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}



void dfs(int cnt)
{//cnt : 
	int x = cnt / 9;//x좌표
	int y = cnt % 9;//y좌표
	if (cnt == 81)
	{
		Print();
		exit(0);
	}

	if (map[x][y] == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false)
			{
				row[x][i] = true;
				col[y][i] = true;
				square[(x / 3) * 3 + (y / 3)][i] = true;
				map[x][y] = i;
				dfs(cnt + 1);
				map[x][y] = 0;
				row[x][i] = false;
				col[y][i] = false;
				square[(x / 3) * 3 + (y / 3)][i] = false;
			}

		}

	}
	else dfs(cnt + 1);




}
int main()
{
 


	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> map[i][j];
			if (map[i][j] != 0)
			{
				row[i][map[i][j]] = true; //i번째 가로줄에 n라는 숫자가 이미 존재합니다.
				col[j][map[i][j]] = true; //j번째 세로줄에 n라는 숫자가 이미 존재합니다.
				square[(i / 3) * 3 + (j / 3)][map[i][j]] = true; //a번째 사각형에 b라라는 숫자가 이미존재합니다.

			}
		}
	}

	
	dfs(0);

	return 0;
}

int<->String

• int-> string
  • string str = to_string(num;
• string -> int
  • int num = stoi(str)

String<->char 

• char ->string
  • string str(ch)
• string ->char
  • strcpy(ch, str.c_str()); //쓸일딱히없음.

char<->int

• char -> int
  • int num = ch-'0';
• int ->char

	//string -> int
	string s1="123";
	int n1 = stoi(s1);
	//int - >string
	int n2=100;
	string s2 = to_string(n2);


	//char->string
	char ch1[] = { "jiji" };
	char *ch2 = "123";
	string s3(ch1);
	string s4(ch2);

	//string ->char
	char ch[100];
	string a = "I wanna go to bed";
	strcpy_s(ch, a.c_str());
 

	//char -> int
	char ch3='100';
	int num = ch3 - '0';