옌의 로그

문제[백준] 쉬운 최단거리  사용 알고리즘- BFS (너비우선탐색)해결방법목표지점을 시작점으로 생각하고, BFS 탐색을 하면서 visited 배열에 이동거리를 갱신해준다탐색종료 후, 갈 수 있는 지점이나, 도달하지 못한 케이스를 찾아 visited 배열을 -1로 바꿔준다소스코드사용언어 : c++#include #include using namespace std;int N, M;int start_x, start_y;int map[1001][1001];int visited[1001][1001];int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}}; //위, 좌, 하, 우void bfs(int y, int x){ queue> q; q.push(make_pair(y, x..

문제 [백준] LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용 알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming) 해결방법 입력 받은 두 문자열 X, Y의 위치 인덱스를 각각 i, j라 할 때, 두 문자열의 최장 공통 부문 수열을 LCS(i, j)라 하자 if Xi = Yj 일 때, (두 문자열의 마지막 글자가 같을 때) LCS(i, j) = LCS(i-1, j-1) + 1 if Xi != Yj 일 때, (두 문자열의 마지막 글자가 ..

문제 [백준] 트리의 기둥과 가지 (Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest > 초급 E번) 사용 알고리즘 - 깊이 우선 탐색 (DFS) 해결방법 루트노드가 주어지므로, 루트노드부터 DFS 탐색 기가노드를 만난 경우 => 기둥의 길이 도출 (gi_len) 리프노드를 만난 경우 => 가지의 길이 도출 (ga_len) 예외 케이스 루트노드가 기가노드인 경우 = 기둥 길이는 0 기가노드가 리프노드인 경우 (사실상 기가노드가 존재하지 않는 경우) = 가지 길이는 0 반례 케이스 기가노드가 루트노드인 경우, 2개의 자식을 가지는 노드 3번이 기가노드로 체크될 수 있다. 이 부분을 유의해서 풀었음 더보기 ..

문제 [백준] 파스칼 삼각형 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 파스칼의 삼각형은, x == 0 일땐 무조건 1을 가진다 dp[y][x] = dp[y-1][x-1] + dp[y-1][x] 대칭구조 이므로, 절반만 dp를 채우고, 내부 합을 구할 때 dp 값이 없는 경우, 대칭위치의 값을 사용해 연산한다 dp[3][0], dp[3][1] dp[4][0], dp[4][1] dp[5][0], dp[5][1], dp[5][2] dp[6][0], dp[6][1], dp[6][2] .... 소스코드 사용언어 : c++ #include using namespace std; int dp[31][31]; int main() { int R, C, W; cin >> R >> C >>..

문제 [백준] 감소하는 수 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 사용 알고리즘 - 백트래킹 (Backtracking) 해결방법 감소하는 수는 중복된 숫자를 허용하지 않는다. 이 의미는 nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 이렇게 10개의 숫자 수열이 있을 때, 해당 수열의 부분수열 찾아, 내림차순 정렬해주면 그게 감소하는 수가 된다. 예를 들면, 하나의 숫자만 뽑아서 부분수열을 만들면 다음과 같다 (10C1) {0}, {1}, {2}, , , {7}, {..

문제 [백준] 행복 유치원 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 사용 알고리즘 - 그리디 (Greedy) 해결방법 원생 사이의 키 차이가 비용일 때, 비용이 최소값이 되게 하려면 서로 인접한 원생들의 키 차이를 봤을 때, 비용이 가장 큰 사이부터 갈르면 된다. 예를 들어, 문제 예제 1번의 경우 원생의 키 : 1 3 5 6 10 키차이(거리) : (2)(2)(1)(4) 총 3그룹으로 만드로 싶다면, 원생 사이를 2번 가르면 되는데, 이 때 키차이가 큰 구간부터 가른다고 생각하면 된다. > 1 |..

문제 [백준] N과 M (10) 사용 알고리즘 - 백트래킹 (BackTracking) 해결방법 주어진 수열을 백트래킹을 통해 탐색하면서, 부분 집합의 개수가 M이 된 경우만 집합에 담는다. 오름차순 정렬 소스코드 사용언어 : c++ #include #include #include #include using namespace std; int N, M; set unique_row; // 부분 수열을 저장할 집합 // 백트래킹을 이용하여 부분 수열 생성 void generateSubsequences(vector& sequence, vector& current, int index) { if (index == sequence.size()){ if (current.size() == M) { vector temp; ..

문제 [백준] 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사용 알고리즘 - 백트래킹(Backtracking) 해결방법 문제 자체는, 주어진 수열에서 모든 부분 수열을 확인하면 되는 문제이다. 모든 부분 수열을 어떻게 확인할건데 ?? >> 백트래킹을 사용해보자 백트래킹 알고리즘의 핵심은 '해를 찾는 도중에 막히면 되돌아가서 다른 경로를 탐색한다' 이다. 문제 예제1을 살펴보면, 다음과 같다 더보기 -- 주어진 수열 [-7, -3, -2, 5, 8] -- 호..

문제 [백준] 두 스티커 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 사용 알고리즘 - 구현 해결방법 모눈 종이에 두 스티커를 붙이는 방법은 2가지다 가로로(옆으로) 나란히 붙이기 세로로(위아래로) 나란히 붙이기 이 때, 신경써야 하는 부분은 각각의 방법으로 붙였을 때 모눈종이를 벗어나는지이다 가로로 붙이는 경우 A가로길이 + B가로길이

문제 [백준] 크로스워드 퍼즐 쳐다보기 (Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #2 3번) 사용 알고리즘 - 구현 해결방법 행(row)방향, 열(column)방향으로 전체 탐색하면서 나오는 모든 단어들을 비교해 답을 구한다 알파벳을 만나는 경우, res 변수에 더해준다 벽을 만나는 경우, 이전까지 만들어진 단어(res)를 temp에 저장한 뒤, 다시 알파벳이 나오면 그 지점을 시작으로 다시 단어를 만든다 res가 2글자 이상인 경우 temp도 2글자 이상인 경우 temp = min(res, temp) >> temp를 최소값으로 갱신시킨다 temp가 1글자 이하인 경우 temp = res >> temp에 ..