옌의 로그

문제 [백준] 행복 유치원 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; ..

문제 [백준] 부분수열의 합 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에 ..

문제 [백준] 후위 표기식2 사용 알고리즘(자료구조) - 스택(Stack) 해결방법 후위 표기식이란?? 예를 들어, 중위 표기식 3+4를 후위 표기식으로 표현하면 34+ 가 된다 => 그렇다면? 입력 받은 식을 앞에서부터 보면서, 피연산자인 경우 : 스택에 저장 연산자가 나온 경우 : 스택에서 2개의 피연산자를 꺼내서 연산한 뒤, 결과값을 다시 스택에 저장 예제 1번 ) 더보기 5 ABC*+DE/- 1 2 3 4 5 처리 과정 1 push st : [1] 2 push st : [1, 2] 3 push st : [1, 2, 3] pop 한 후, * 연산 st : [1, 6] pop 한 후, + 연산 st : [7] 4 push st : [7, 4] 5 push st : [7, 4, 5] pop 한 후 / ..

문제 [백준] 색종이 만들기 (Olympiad > 한국정보올림피아드 > KOI 2001 > 중등부) 사용 알고리즘 - 분할 정복 - 재귀 해결방법 종이를 한 변의 길이가 절반이 되게끔 자른다고 생각하고 문제를 해결한다 종이를 자르는 경우는 기준위치의 색깔과 현재 위치의 색깔이 다를 때 종이를 자른다 한 변의 길이가 절반이 되게 자르는 경우, 종이 4장이 생성되는데, 이 때 각 종이의 기준위치는 다음과 같다 길이 : N 일때, 기준위치 (col, row) // (0, 0)이다 종이1 > 길이 : N/2, 기준위치 (col, row) 종이2 > 길이 : N/2, 기준위치 (col, row+N/2) 종이3 > 길이 : N/2, 기준위치 (col+N/2, row) 종이4 > 길이 : N/2, 기준위치 (col+..

문제 [백준] 마라톤 틱택토 (Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #6) 사용 알고리즘 - 브루트 포스 (Brute Force) 해결방법 입력 받은 보드에서 행, 열 또는 대각선 방향에서 3연속하는 이니셜이 있는 경우 승리자로 취급한다 전체 좌표를 돌면서 대각선 좌측 아래 방향, 아래 방향, 대각선 우측 아래 방향, 우측 방향 이렇게 총 4가지 방향을 탐색한다 최소 3개만 연속하면 되므로, 좌표마다 같은 방향으로 최대 2칸 까지만 탐색한다 범위를 벗어나는 경우 탐색하지 않는다 같은 이니셜이 3개 이상 연속한 경우 탐색을 완전 종료한다 반례 모음집 더보기 정답 : A 포인트 : 대각선 방향 탐색시 가능한..

문제 [백준] 주유소 (Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번) 사용 알고리즘 - 그리디 (Greedy) 해결방법 마을이 일직선 상에 있다는 것이 포인트 한 마을에서 다음 마을로 이동하기 전에 가장 저렴한 주유소를 저장해 두고 해당 주유소에서 주유한 뒤 이동한다 매 번 마을에 도착할 때마다 최소 주유비에 다음 이동 거리를 곱해서 경비를 구해야한다 예제 1의 경우 각 마을의 주유비가 [5, 2, 4, 1] 이다. 이 때 이동할 때마다 그리디 하게 주유비를 선택한다고 하면 다음과 같다. i 현재 주유비 최소 주유비 이동 거리 경비 0 5 5 2 10 1 2 2 3 6 2 4 2 1 2 소스코드 사용언어 : C++ #include #include using namespace..