옌의 로그

문제[백준] 쉬운 최단거리  사용 알고리즘- 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 일 때, (두 문자열의 마지막 글자가 ..

문제 [백준] 합이 0 (Olympiad > International Autumn Tournament in Informatics > 2011 > Group B (Juniors) 3번) 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 사용 알고리즘 - 이분탐색 - 투 포인터 - 정렬 해결방법 입력받은 학생들의 코딩실력 수열을 벡터 code_lv에 저장한 후 오름차순 정렬한다 N명의 학생 중 코딩실력의 합이 0이되는 3명을 고르는 문제이므로 2중 for문을 돌며 벡터에서 2명의 학생을 고른후, 나머지 한 명은 이분탐..

문제 [백준] 진우의 민트초코우유 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 사용 알고리즘 - 브루트포스 - 구현 해결방법 문제조건에서 우유의 총합이 10개를 넘지 않는 단 것이 포인트 가능한 우유 좌표의 순열을 모두 탐색해서, 민우가 집으로 돌아올 수 있다는 전제하에 마실 수 있는 최대 우유 개수를 구한다 (*순열 : 시퀀스에 담긴 원소를 중복없이 순서에 상관있게 나열하는 것) 예를 들면, 우유가 총 3개 있다고 했을 때, 각각의 우유 좌표를 벡터에 저장한다 {{1,1}, {3,4},..

문제 [백준] 트리의 기둥과 가지 (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 |..

문제 [백준] 효율적인 해킹 Contest > Internet Problem Solving Contest > IPSC 2008 B번 > N >> M; graph.resize(N+1); int from, to; for (int i=0; i> to >> from; graph[from].push_back(to); } int max_pc = 0; // 해킹 가능 최대 컴퓨터 수 vector res_com; // 컴터 번호 저장 for (int i=1; i= max_pc) { if (possible_com > max_pc) { max_pc = possible_com; res_com.clear(); } res_com.push_back(i); } fill(visited, visited+N+1, 0); // visit..

문제 [백준] 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; ..