개발자 일기장.

블록 이동하기 Problem? 문제 링크 : [2020 카카오 공채] 블록 이동하기 Solution bfs문제 bfs()를 통해 가능 경로를 탐색한다 핵심적인 내용은 아래의 그림을 보면서 참고 가정 isSafeTurn : 회전가능 여부확인 solution() : 문제 해결 코드 struct robot : queue에 넣을 구조체 turnDir : 회전하는 경우 이동 경로 safeTurn : 안전한 회전 여부 확인을 위한 위치 goDir : 회전하지 않는 경우 이동 경로 visited : 방문 여부 확인 N : 배열의 사이즈 Code(핵심 코드) int bfs(vector board, int y, int x) { queue q;// queue robot t(0, 0, 1, 0); q.push(t); vis..

문자열 압축 Problem? 문제 링크 : [2020 카카오 공채] 문자열 압축 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Solution 구현 문제 비교하는 문자열의 길이를 해당 문자열의 크기의 반부터 1까지 반복하며 문자열을 단순 비교한다. "비교하는 문자열의 길이"가 끝에 도달하기 전까지 반복한다. 특이사항으로 반복되는 횟수가 10번 이상인 경우 자릿수를 고민해줘야 한다. 가정 getSize() : 자릿수를 구하는 함수 solution() : 문제 해결 코드 slen : 전체 문자열의 길이 len : 비교하는 문자열의 길이 start_pos : ..

색종이 붙이기 Problem? 문제. Solution 브루트 포스 dfs를 통한 탐색 색종이 크기안에 빈칸(0)이 있는 경우나 색종이를 잘 붙인 경우는 효율적으로 다음 dfs를 설정한다. 가정 dfs() : 갈 수 있는 경로 탐색 board : 맵 confetti : 남은 색종이 파악 answer : 최소 경우의 답 보관 Code #include #include using namespace std; #define MAX 10 #define INF 999999999 int board[MAX][MAX];// map int confetti[6] = { 0, 5, 5, 5, 5, 5 };// confetti count(count per paper) int answer = INF, cnt = 0;// answer..

퍼즐 Problem? 문제. Solution 따로 어려웠던 부분 없이 쉬웠던 분제 배열 대신 string으로 bfs()를 사용하는 방법을 이용하면 간단한 문제이다. string으로 bfs()을 사용한다. 'set'을 이용해서 방문여부를 확인했다. 가정 bfs() : 갈 수 있는 경로 탐색 endStr : 원하는 답 visited : 방문여부 확인 dx, dy : 이동 방향 Code #include #include #include #include #include using namespace std; #define MAX 3 int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, -1, 0, 1 }; string endStr = "123456780"; set visited; int b..

별자리 만들기 Problem? 문제. Solution 최소 스패닝 트리를 만들기. loop를 돌면서 최소 스패닝 트리를 완성했다. (N이 100이하 이므로) 크루스칼(kruskal Algorithm)을 사용했다. 가정 getLength() : 길이 구하기 simpleFind() : 부모 찾기 simpleUnion() : 노드 이어주기 g_size : 해당 전체 노드 개수 xpos, ypos : input graph : graph parent : 부모 노드 유지 Code #include #include #include #include using namespace std; #define MAX 10201 int N, g_size; float answer = 0; int parent[MAX]; vector g..

도시 분할 계획 Problem? 문제. Solution 최소 스패닝 트리를 만든 후 가장 큰 cost를 가진 값을 빼면 해결되는 간단한 문제. 크루스칼(kruskal Algorithm)을 사용했다. 가정 simpleFind() : 부모 찾기 simpleUnion() : 노드 이어주기 graph : input parent : 부모 노드 유지 Code #include #include #include using namespace std; #define MAX 100000 + 1 int N, M, ans = 0; int parent[MAX]; vector graph; int simpleFind(int x) { if (parent[x] == x) return x; else return parent[x] = sim..