devlog

출처 : https://www.acmicpc.net/problem/2665풀이 방법먼저 일반적인 bfs알고리즘으로 방문 배열을 visited[y][x][cnt] y, x에서 cnt만큼 검은 방을 뚫고 온 경우로 설정한 후 풀이하였다.이때 cnt 2501로 설정해 주어야 한다. (50*50) 처음에 51로 설정해서 틀렸다. 그 후 다음 좌표의 값이 방문하지 않았고 방이 검은 방인지 흰 방인지에 따라 흰 방이라면 바로 큐에 넣어주고 검은 방이라면 cnt + 1을 해주어서 큐에 넣어주었다.코드 #include #include #include #include #include using namespace std;int N, ans = 987654321;int room[51][51];int visited[51][5..

출처 : https://www.acmicpc.net/problem/15683풀이 방법백트레킹을 이용한 브루트포스 문제이다. 사무실의 크기가 최대 8x8 이므로 브루트포스를 사용해서 성공할 수 있다.cctv를 dfs로 돌아가며 하나씩 최대 4개의 방향을 돌아가며 다 검사하고 백트레킹을 통해 다시 돌아오는 삼성 기출문제의 연구실 문제와 유사하다.  cctv의 타입에 따라 조사할 방향을 정해두면 된다. 나는 아래와 같이 구현했다. 아래 코드에서 i는 for 문을 통해 0에서 3까지 반복 진행한다.타입이 1인 경우 한쪽 방향만 볼 수 있다.타입이 2인 경우 양 쪽 끝방향을 볼 수 있다.타입이 3인 경우 직각인 방향을 볼 수 있다.타입이 4인 경우 3가지 방향을 볼 수 있다.타입이 5인 경우 4방향 다 볼 수 있..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42747# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 방법H-Index는 특정 과학자가 발표한 논문 중, h번 이상 인용된 논문이 h 편 이상이고, 나머지 논문들은 h번 이하로 인용된 경우, 이 h의 최댓값을 의미한다. H-Index의 중요한 핵심은 ‘인용 횟수’보다는 ‘인용된 논문의 수’에 중점을 둔다는 점이다. 논문을 정렬 후 인덱스와 비교하면 된다.예를 들어, [1, 5, 5, 5, 5]의 정답은 4이다. 그러므로 인덱스를 하나씩 올..

출처 : https://www.acmicpc.net/problem/14719풀이 방법x좌표를 기준으로 현재 지역은 왼쪽에서 가장 큰 값과 오른쪽에서 가장 큰 값 중 작은 값에서 자신의 블록 높이를 뺀 만큼 물이 차오르게 된다.그러므로 각각의 왼 쪽 최댓값과 오른쪽 최댓값을 구해 자신의 블록 길이만큼 빼주면 된다. #include #include #include using namespace std;int main() { vector block; int H, W; cin >> H >> W; int answer = 0; for (int i = 0; i > a; block.push_back(a); } for (int i =1;i = 0; k..

출처 : https://www.acmicpc.net/problem/1101 풀이 방법 문제에서 핵심 포인트는 한 상자에서 다른 상자로 카드를 옮길 때 색상에 상관없이 한 번에 옮길 수 있다는 점이다.이를 통해 만약 비어있는 상자가 아니거나 하나의 색상 카드만 존재하지 않는 경우라면 모든 카드를 조커 상자로 옮기면 된다.또한 핵심 포인트 때문에 카드의 색상이 가장 다양하게 존재하는 상자가 무조건 적 조커가 되지 않으므로 모든 상자를 돌아가며 조커가 될 때 가장 작은 횟수를 구하면 된다. 만약 1개의 색상만 존재하는 상자가 이미 앞 전에 같은 색상만 존재하는 상자가 있다면 옮겨 주어야 하므로 이 부분만 유의하면 된다. #include #include #include #include using namespac..

출처 : https://www.acmicpc.net/problem/5557풀이 방법dp를 설정하는 것에 시간이 많이 쓴 거 같다결정한 방법은 dp[y][x] == y번째 자리일 때까지의 합이 x인 경우로 설정했다.또한 만약 dp[y][x]의 값이 0이라면 해당 경우는 가능하지 않은 경우 이므로 선택하지 않는다.결국 dp[y][x]의 값이 양수인 것 중에서만 dp[y-1][x-number[i]]를 더해주거나 빼주면 된다. (0 이상 20 이하 인경우만) #include #include #include using namespace std;int N;vector number;long long dp[101][21];int main() { memset(dp, 0, sizeof(dp)); //dp 배열 초기화..

출처 : https://www.acmicpc.net/problem/2631풀이 방법LSB알고리즘을 사용해서 전체 학생 수에서 LSB를 빼주면 된다. #include #include using namespace std;int N;vector students;vector dp;int binary_search(int target) { // 타겟을 찾음 int left = 0, right = dp.size() - 1; int mid = (left + right) / 2; while(left target) { return mid+1; } else if (dp[mid] > target) { right = mid - 1; ..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 방법변환이 가능한지 확인할 수 있는 함수가 필요하다 이를 위해 두 단어의 스펠링 개수 차이가 1이면 가능하다고 판단하는 canChange함수를 작성했다.그 후 일반적인 bfs함수를 통해 tartget 단어가 될 때까지 수행했다. #include #include #include #include using namespace std;bool canChange(string str1, string..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 방법문제를 보자마자 완전 탐색 + bfs로 풀이해야겠다고 생각이 들었다. 연결된 간선을 하나씩 끊어 가며 bfs로 두 구역의 차이를 구한 후 가장 작은 차이를 가지는 것을 저장해 두었다.간선을 끊는 방법은 간선을 돌며 선택된 간선에서 한쪽에서 bfs를 수행할 때 다른 한쪽 구역은 방문하지 않는 방법이다. 이렇게 양 쪽에서 각각 bfs를 수행한 후 두 지역의 차이를 ..

출처 : https://www.acmicpc.net/problem/2660풀이 방법회장을 뽑기 위해선 완전 탐색 + bfs로 풀이하면 된다.각 사람을 돌아가며 모든 벡터를 초기화 하고 bfs를 진행한 후 가장 작은 점수인 사람을 선택하면 된다.#include #include #include #include using namespace std;int N;vector> graph;int bfs(int start) { int ret = 0; queue> q; q.push(make_pair(start, 0)); // 시작 점 추가하기 int visited[N+1]; for (int i = 0;i > N; graph.resize(N+1); while(true) { int a, b; cin >> a >> b..