개발자 일기장.

문자열 압축 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..

최소 스패닝 트리 Problem? 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. Input 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 N번까지 번호가 매겨져 있다. 최소 스패닝 트리의 가중치가 -2,147,483,64..