mo1lusca의 블로그

https://www.acmicpc.net/problem/1931제한된 시간 안에 가장 많은 회의를 진행해야 한다.아주 탐욕적이고 직관적으로 생각했을 때, 이 문제를 풀 로직으로 두개가 생각났다.1. 회의시간이 가장 짧은 회의를 선택2. 끝나는 시간이 가장 빠른 회의를 선택회의를 위의 로직대로 오름차순 정렬해 하나씩 선택 할 것이다. 1번 로직은 A(1~2), B(3~50), C(50~51)의 세 회의가 주어졌을 때,회의시간이 짧은 A-C-B 순으로 선택하게 된다.이때 C를 고른 시점에서 B는 고를 수 없기 때문에 (B는 3에 시작하는 회의라서) 얻는 답은 2가 된다.하지만 우린 이게 답이 아니란걸 안다. 딱봐도 A-B-C 순이므로 답은 3이다.따라서 1번 로직은 탐욕적이지만 이 문제에는 적합하지 않다...

https://www.acmicpc.net/problem/1541그리디 알고리즘을 사용해서 풀면 된다.말이 알고리즘이지 실버쯤 되는 그리디 문제는 무지성으로 풀어도 풀린다.. 값을 최소로 만들려면, "-" 뒤에 오는 값이 최대가 되도록 괄호를 쳐주면 된다!#include #include #include using namespace std;int main() { string s; string buf = ""; cin >> s; int len = s.length(); int result = 0; bool is_minus = false; for (int i = 0; i 알고리즘 분류에 문자열과 파싱이 있는걸 보고 잠시 어지러웠지만,C에서 C++로 건너온 우리에게는 string 자료형과 stoi라는 몹시 뛰어..

DFS를 열심히 연습했으니 이번엔 DFS를 활용한백트래킹 알고리즘을 배우자! 백트래킹은 모든 경우의 수를 탐색하는 알고리즘인데,여기서 중요한 포인트는 DFS나 BFS같이 모든 노드를 방문해 탐색하는 것이 아니라가망이 없는 경로는 버려서 효율적으로 해를 찾는다는 것이다! 백트래킹 연습을 위해 N과 M 시리즈 문제(12문제)를 풀어보자.대체로 비슷한 문제들이어서 몇 문제만 풀어놓아도 금방 풀린다. 글이 상당히 기니 주의하기 바란다.1번 문제https://www.acmicpc.net/problem/15649N개의 수 중 M개를 선택해 만들 수 있는 수열들을 구한다.#include #include using namespace std;int n, m;int arr[9];bool used[9];void backtr..

https://www.acmicpc.net/problem/7576토마토박스를 배열로 준다.1인 토마토는 익어있어서, 인접한 익지 않은(0인) 토마토를 익게 한다.토마토맛토부분 코드 설명#define MAX 1000typedef struct { int x; int y;} Point;queue q;int box[MAX][MAX];int day[MAX][MAX];int dx[] = { 0, 0, -1, 1 };int dy[] = { 1, -1, 0, 0 };토마토상자의 최대 길이는 1000이므로 쓰기 편하게 define 해준다.각 토마토의 위치는 박스 내에서 x, y로 표현할 수 있기에 편하게 Point라는 구조체를 만들어준다.BFS에 사용할 queue를 선언하고, 입력받은 토마토박스의 상태를 저장할 box ..

https://www.acmicpc.net/problem/2606이 문제를 쉽게 풀기 위해선 간단한 관점의 변화가 필요하다.바이러스가 전파된다 == 노드끼리 연결되어 있다 == 탐색 알고리즘으로 도달할 수 있다.이정도 결론만 도출해내도 문제를 푸는데에 충분하다.#include #include #include using namespace std;vector graph[101];bool dist[101];void Dfs(int i) { dist[i] = true; for (int next : graph[i]) { if (!dist[next]) { Dfs(next); } }}int main() { int n, m; cin >> n >> m; for (int i = 0; i > u >> v; graph..

https://www.acmicpc.net/problem/1260 그래프를 입력받고 해당 그래프를 DFS와 BFS로 각각 탐색하면 된다.DFS와 BFS 모두 공부할 수 있는 기초 문제이기 때문에, 최대한 이해하는 편이 유익하다. 부분 코드 설명vector graph[1001];bool visited_bfs[1001];bool visited_dfs[1001]; 노드와 링크 정보를 저장할 graph를 선언한다. 배열의 각각의 원소는 벡터로 존재한다. 배열의 index는 각각의 노드 번호를 가리키고, 배열의 원소인 벡터는 해당 노드와 연결되어 있는 다른 노드의 번호를 저장한다.이미 탐색한 경로는 다시 탐색하지 않기 위해 bool형 visited 배열을 DFS와 BFS 각각 따로 선언해주었다. int main(..

https://www.acmicpc.net/problem/14729 오름차순으로 정렬 후 낮은 값부터 7개를 출력하면 된다.#include #include using namespace std;int main() { int n; cin >> n; double* arr = new double[n]; for (int i = 0; i > arr[i]; } sort(arr, arr + n); for (int i = 0; i 소수점 뒤 세 자리까지 출력해줘야 하기 때문에 cout이 아닌 printf를 사용하였다.

https://www.acmicpc.net/problem/1966 문서 수, 추적할 문서 번호, 문서의 중요도를 입력받고문서를 중요도순으로 인쇄할 때의 추적하는 문서가 몇 번째로 인쇄되는지 구한다.부분 코드 설명queue> q; //importance, indexqueue importance;int temp[100] = { 0, }; 사용할 변수들을 선언한다. q는 입력값을 순서대로 저장할 queue이다.입력값인 중요도와 입력순서(index)를 저장해야 하기 때문에 pair클래스를 사용해 두 값을 저장하도록 했다.temp 배열에서는 입력받은 중요도 값들을 저장한 후 내림차순 정렬할 수 있도록 한다.정렬한 temp를 importance에 저장해 중요도가 높은 값부터 하나씩 꺼낼 수 있도록 한다. int n..

https://www.acmicpc.net/problem/3986 9012 괄호 문제와 비슷한 느낌으로 풀면 된다.들어오는 문자를 stack에 push한다. (push하려고 준비 한다)이때 만약 들어온 문자가 top에 있던 문자와 같은 문자라면 pop한다.#include #include using namespace std;int main() { int n; cin >> n; int cnt = 0; for (int i = 0; i s; string buf; cin >> buf; int len = buf.length(); for (int j = 0; j 한 문자열에 대해 위에서 말한 작업을 수행 후 stack이 empty인지 검사한다.empty이면 좋은 단어이므로 cnt를 증가시킨다.

https://www.acmicpc.net/problem/9012 여는 괄호 '('를 stack에 push, 닫는 괄호 ')'를 stack에 pop하는 명령으로 생각한다.stack이 empty일때 pop하거나 모든 명령을 실행한 후에도 stack이 empty가 아니라면올바른 괄호 문자열(VPS)이 아니다. #include #include using namespace std;int main() { int n; cin >> n; for (int i = 0; i q; string s; cin >> s; int len = s.length(); bool is_vps = true; for (int j = 0; j 이제 보니 queue로 구현했는데, 어차피 특정한 값을 push, pop 하는게 아니라서별..