이러한 문제류는 이제 dfs든 bfs로 풀기 쉬워졌다 이문제의 경우 자신을 기준으로 상하좌우로만 이동 할 수있기때문에 깊이우선 탐색으로 풀어 보았다 이문제는 어차피 단지의 개수를 세야 하기때문에 모든점을 한번에 다방문하면서 개수를 셀수 있는 dfs를 사용하였다. 이문제의 핵심 부분은
이문제는 요즘 나의 경악스러운 알고리즘 실력에 실망하던차에 내가 빠르게 풀 수 있는 문제였다. 아직 고수가 되긴 멀었지만 빨리 이런 문제쯤은 10분만에 해치울 수 있는 파워 프로그래머가 되고 싶다!!!!!
이 문제의 경우 여러방식으로 풀 수 있다. 나의 경우 일반적으로 성능이 나쁘지 않은 BFS를 사용해서 풀었다
자 이문제를 풀때는 처음 1인애를 만나면 루프를 돌면서 자신을 기준으로 갈 수 있는 모든 점들을 BFS로 접근하여 visited배열에 마킹합니다 visited 배열이 1로 마킹되면 다시 해당하는 곳을 접근 하지 않습니다 이렇게 빨간색으로 체크 된 1을 root로 나머지 1로마킹된 애들이 BFS 로서 빨갛게 1로 마킹된 애들부터 같은색깔안에 있는 영역으로 접근합니다.
#include <iostream>
#include <queue>
using namespace std;
bool cabbage[52][52];
int visited[52][52];
int main() {
int T; //테스트 케이스의 개수
int M, N, K;//M:가로길이 N:세로길이 K: 배추가 심어져있는 위치의 개수;'
cin >> T;
queue<pair<int, int>> bfsQueue;
for (int i = 0; i < T; i++) {
cin >> M >> N >> K;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}
int countnum = 0;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
if (visited[j][k] == 1 && cabbage[j][k]==1)
continue;
else if(visited[j][k]==0 && cabbage[j][k]==1){
countnum += 1;
cabbage[j][k] = 1;
bfsQueue.push(pair<int, int>(j, k));
while (!bfsQueue.empty()) {
int firstn,secondn;
firstn = bfsQueue.front().first;
secondn = bfsQueue.front().second;
bfsQueue.pop();
if (firstn >= 1) {
if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
bfsQueue.push(pair<int, int>(firstn - 1, secondn));
visited[firstn - 1][secondn] = 1;
}
}
if (secondn >= 1) {
if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
bfsQueue.push(pair<int, int>(firstn, secondn - 1));
visited[firstn][secondn - 1] = 1;
}
}
if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
bfsQueue.push(pair<int, int>(firstn + 1, secondn));
visited[firstn + 1][secondn] = 1;
}
if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
bfsQueue.push(pair<int, int>(firstn , secondn+1));
visited[firstn][secondn + 1] = 1;
}
}
}
}
}
cout << countnum << '\n';
}
}
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}
일단 이부분은 각 케이스의 접근할때 배열들을 초기화 한후 양배추가 위치한곳을 1로 체크해줍니다
프로그래머스를 풀면서 느끼고 있는게 기업 코테에서 문자열 처리가 은근 많이 나오는거 같다 그래서 나도 기존에 c++로 문자열 파싱까지 했었는데 문자열 관련 구현은 c++ 로 하기에는 시간적으로 많이 부족한거 같다. 이에 기본적으로 문자열 처리에 많은 도움을 주는 파이썬을 사용해서 문자열 처리 문제는 앞으로 처리 하기로 했다 실제로 c++로 구현하면 엄청 오래걸릴 코드들도 파이썬의 문자열 인덱싱 기능만 사용하면 빠른시간안에 끝난다. 이번문제는 이러한 이유로 파이썬으로 풀었다 c++로 풀고싶지는 않다 이러한 문제를 일단 이문제는 그냥 쉽다 파이썬의 split을 이용해서 빈칸으로 각 요소들을을 분할해주고 그 list들의 요소들의 값을 서로 비교해서 최대 최솟값을 구한다이다. 아마도 코드를 보면 이해가 쉽게 될 것 이다
def solution(s):
answer = ''
a = []
s = s.split(' ')
for i in s:
a.append(int(i))
max=a[0]
min=a[0]
for i in a:
if i >max:
max=i
if i<min:
min=i
answer=answer+str(min)
answer=answer+" "
answer=answer+str(max)
return answer
프로그래머스 문제를 풀고 이문제를 푸니 너무 쉽게 느껴졌다 알고리즘 수련이 아주 부족하다고 느껴졌다 더 열심히 해서 제발 취업을 애햐하는데 이문제의 경우는 문제의 답으로 최소경로수를 원하는 것이기 때문에 최소 경우의 수를 확정적으로 반환해주는 BFS를 사용해주어야 한다 이문제 자체는 실버 1이지만 문제도 짧고 해서 이해하기가 매우 편했다. 이 문제의 경우 bfs를 총 3가지 경우로 짜주면 그냥 해결되는 문제열다 X-1 ,X+1 ,2*X 자기 자신에대해서 자식이 이렇게
만들어지기 떄문에 bfs의 범위를 이렇게 3개씩 넓혀주면 빠르게 끝난다.
BFS의 특징으로는 큐를 사용하면 매우 편해진다는 장점이 있다 이문제의 경우도 마찬가지다 큐를 사용해서 자기를 없애면서 자기자식은 큐에 넣게되면 BFS가 된다 이전 문제에서도 큐를 이용해서 풀었기 때문에 이번문제도 큐를 이요했지만 이번에는 visited 배열에 자기가 몇대손인지를 넣을 수 있게 코드를 짜보았다
#include <iostream>
#include <queue>
using namespace std;
int visited[200002];
int N, K;
int main() {
cin >> N >> K;
queue<int> hs;
hs.push(N);
visited[N] = 0;
while (true) {
if (hs.front() == K) {
break;
}
if (hs.front() > 0) {
if (!visited[hs.front() - 1]) {
hs.push(hs.front() - 1);
visited[hs.front() - 1] = visited[hs.front()] + 1;
}
}
if (hs.front() < 100000) {
if (!visited[hs.front() + 1]) {
hs.push(hs.front() + 1);
visited[hs.front() + 1] = visited[hs.front()] + 1;
}
}
if (hs.front() <= 50000) {
if (!visited[hs.front() * 2]) {
hs.push(hs.front() * 2);
visited[hs.front() * 2] = visited[hs.front()] + 1;
}
}
hs.pop();
}
cout << visited[K];
}
백준만 풀다가 프로그래머스 문제가 빡세다고 해서 풀어보았다 개어렵다 kakao의 문제는 문자열 위주로 코딩테스트?가 진행 되는건가 싶었는데 오늘 풀고 나서 kakao의 문제는 대부분 문자열 처리인 거 같다는 생각을 했다 오늘 진행한건 일단 lv2 였는데 저녁을 안먹어서 그런지 오지게 안풀렸다 일단 이문제를 푸는데 약 1시간 반정도 걸렸으니 실제로 이문제가 나왔으면 코테에서 널어졌을 거 같다. 나는 일단 이문제를 이렇게 생각했다 사전에서 일단 1개의 문자가 맞는지 탐색한다 맞으면 자신과 자신의 다음문자를 합쳐서 나 이후로 검사한다 만약 또나온다면 합친 문자열에 또 그 다음문자를 합쳐서 검색한다. 그 후 반복이 끝나면 합치기 전에 나의 index를 저장 한다. 이 index는 즉 문자들을 합쳤을때 최종적으로 벡터에 존재하는 문자열을 의미한다.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> solution(string msg) {
vector<int> answer;
char start = 'A';
int k = 0;
vector<string> dictionary;
for (int i = 1; i <= 26; i++) {
dictionary.push_back(string(1, start));
start++;
}
for (int i = 0; i < msg.length(); i++) {
string temp = string(1,msg[i]);
int endnumber=0;
for (int j = 0; j < dictionary.size(); j++) {
if (temp == dictionary[j]) {
temp = temp + msg[i += 1];
endnumber = j+1;
}
}
answer.push_back(endnumber);
if ((i) == msg.length()) {
continue;
}
dictionary.push_back(temp);
if (i >= 1) {
i = i - 1;
}
}
return answer;
}
int main() {
vector<int> answe1r;
answe1r=solution("TOBEORNOTTOBEORTOBEORNOT");
for (int i = 0; i < answe1r.size(); i++) {
cout << answe1r[i] << '\n';
}
}
이 문제의 경우 사실 dfs로푸는게 간단해보였다 하지만 문제 분류가 그리디로 되어있었으니 그리디로 풀어 보겠다
이문제의 경우 A와 B가 주어졌을 경우 A에서 B를 만든다고 생각하지말고 B에서 A로 가야한다고 생각해야 잘풀리는 문제였다 B가 일단 2로 나누어지는 경우 2로 나누고 B가 10으로 나누었을 때 1이 남으면 10으로 나눈다 그후 A와 비교해서 같으면 나오고 아니면 다시 실행한다 단 B가 A보다 작아졌을 경우는 문제의 답이 존재하지 않는 경우기 때문에 -1을
출력한다.
이문제의 경우 상당히 쉬웠지만 계속 A에서 B를 만들려고 하니 시간이 많이 소모되었다.
#include <iostream>
using namespace std;
int main() {
int A, B;
int countnum=0;
cin >> A >> B;
while (true) {
if (A == B) {
countnum += 1;
break;
}
if (A > B) {
countnum= -1;
break;
}
if (B % 10 == 1) {
B--;
B = B / 10;
countnum++;
}
else if (B % 2 == 0) {
B = B / 2;
countnum++;
}
else {
countnum= -1;
break;
}
}
cout << countnum;
}
