lee-soo 님의 블로그

https://www.acmicpc.net/problem/1201 내 인생의 첫 플래티넘 문제이다 뇌 척수가 뽑힐정도의 고통을 받고 결국 풀이를 봤다. 참고한 블로그이다https://hongjw1938.tistory.com/191 알고리즘 풀이 - 백준 1201(NMK, 그리디(Greedy))관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1~N 수를 한 번씩 이용해서 LIS와 길이가 M이고, LDShongjw1938.tistory.com너무 예쁘게 설명을 잘 해놓았는데나의 개판같은 설명이 이해가 안되면,, 여기서 보면서 이해해라 그림도 그려주신 아주 멋진분이시다 먼저 -1이 나오는 조건문부터 해결해주어야 한다. ..

https://www.acmicpc.net/problem/1744 읽어보면쉽다 단순히오름차순 정렬해주고 제일 작은 음수 들끼리 곱해주고, 제일 큰 양수들끼리 곱해주고 그 중에서 다 묶고 난 후, 남은 음수가 1개일때, 남은 양수가 1개일때 등조건만 나눠주면 된다 #include #include using namespace std;int main(){ int n; cin >> n; int arr[n]; for (int i = 0; i { cin >> arr[i]; } sort(arr, arr + n); int result = 0; for (int i = n - 1; i >= 0; i--) { if (arr[i] >= 0 &&..

https://www.acmicpc.net/problem/1541 문제는 간단하다 최소가 되면 됨 잘 생각해봐라-가 나온 이후에+가 나온다면?-앞에 괄호를 쳐줘서 모든 + 들을 다 더한 후 음수로 바꿀 것이다 그렇다면 -가 나온 이후에+가 나오고 또 -가 나오면? 그냥 또 빼주면 된다 그니까 -가 1개라도 나오면 그 이후의 수는 모두 -로 바꿔주는 것이 최소이다.#include #include using namespace std;int main(){ string s; cin >> s; string temp; int result = 0; char trigger = '+'; int first = 0; for (int i = 0; i { if (s[i]..

.https://www.acmicpc.net/problem/1931 그리디 알고리즘을 배운다면무조건 나오는 문제 중 하나이다. 이건 그냥 외우다 시피 해라!~! https://source-sc.tistory.com/59 [탐욕 알고리즘][2] - 회의실 배정 문제유명한 Greedy 알고리즘 - 회의실 배정 문제 회의실 배정 문제는 그리디 알고리즘에서 빠지지 않고 등장하는 문제이다. 이문제는 각 회의마다 시작시간과 종료시간이 정해져있고 하나의 회의실에source-sc.tistory.com이 블로그에서 회의실 배정 문제에 대해 굉장히 자세히 알려주고 있다! 그리디 알고리즘을 사용하는 건 알겠는데 어떻게 사용하냐! 끝나는 시간을 기준으로 생각하면 된다 예를들어 q에 들어가는 회의 시간은"종료 시간이 가장 빠른..

https://www.acmicpc.net/problem/11047흠.. 너무쉽다 이거 딱봐도 그리디 문제 조건에 Ai 가 Ai-1의 배수라 했으니까 그냥 간단하게 가장 큰 수부터 작은 수 까지 반복적으로 더해주고, 커지면 다음으로 넘어가면 된다#include using namespace std;int main(){ int n, k; cin >> n >> k; int arr[n]; for (int i = 0; i { cin >> arr[i]; } int money = 0, count = 0; int temp = n - 1; while (money != k) { if (money + arr[temp] > k) { ..

https://www.acmicpc.net/problem/1167 이 문제에 대해 간단히 설명하자면 여러개의 노드가 있을때, 한 노드와 또 다른 노드 사이의 거리가 제일 멀 때의 거리를 구하라그게 지름이고 이것이다. 예를들어 이렇게 노드가 있으면? 가장 긴 거리는3+2+6 =11이다 그래서 내가 먼저 처음에 생각한건 "무조건 거리를 잴 때는, 연결된 노드가 1개밖에 없는 경우이다"라고 생각해서 조건문으로 자식이 한개인 경우를 걸러낸 후,그 노드들에 대해 dfs를 통해 distance들을 알아내고max를 지정해줬었다 #include #include #include #include using namespace std;bool visited[100001];bool visited_2[100001];vector..

https://www.acmicpc.net/problem/11725 해당 문제는 루트를 1이라고 할 때, 노드 2번부터 n번까지 그의 부모 노드를 출력하면 되는 문제다 예를들어 입력된 예제를 보면 이런 형식으로 되어있고 2번노드의 부모는 43번은 64번은 15번은 36번은 17번은 4이므로461314가 나오게되는데 문제는 노드가 주어질 때, 그저 간선간의 정보만을 입력으로 줄 뿐 누가 부모노드인지 알려주지 않았다 하지만!우리는 1이 루트노드인걸 알았으니, 1로부터 시작한 탐색을 하면 되는데bfs로 하든 dfs로 하든 이건 상관없다 #include #include #include using namespace std;vectorint> v[100001];bool visited1[100001];int par..

https://www.acmicpc.net/problem/2250 호호..문제가 어려워 보이지만차근차근 읽으보면 입력은 부모 -> 왼쪽자식 -> 오른쪽자식로 이루어진다 자식이 없는 곳은 -1 로 표현한다 [TREE] 백준 1991번 트리의 순회(C++) [TREE] 백준 1991번 트리의 순회(C++)https://www.acmicpc.net/problem/1991 트리 순회 문제다. 아마 개발자를 목표로 하는 취준생이나, 대학생 3~4학년이라면 당연히 전위 중위 후위순위에 대한 알고리즘을 알고 있을 거다. 간단히 설명하자면,lee-soo.tistory.com사실 이 문제를 풀고온 후, 하나만 깨달으면 문제는 전혀 어렵지 않다. 이런 입력이 들어왔을 때 그림을 유심히 보자. 노드의 순서들이 어라. "트리..

https://www.acmicpc.net/problem/1991 트리 순회 문제다. 아마 개발자를 목표로 하는 취준생이나, 대학생 3~4학년이라면 당연히 전위 중위 후위순위에 대한 알고리즘을 알고 있을 거다. 간단히 설명하자면, 트리를 탐색할 때문제에 나온 것처럼 루트 , 왼쪽자식 ,오른쪽 자식순서대로 찾아볼거냐 왼쪽자식 루트 오른쪽 자식 or 왼쪽 오른쪽 루트 방식으로 찾아볼거냐에 대한 것이다. 그래서 전위순회를 한 경우에는 가장 먼저 A에서 시작하므로 루트 A를출력그 이후 왼쪽노드로 넘어가면B가 루트노드가되므로 B 출력그 이후 D 가...이렇게 반복하는 것이다 이런 문제는 재귀를 통해서 풀면 되는데 진입점에 따라 탐색 방식이 달라진다고 생각하면 된다. 예를들어 1.왼쪽노드 들어가기2.오른쪽노드 들..

https://www.acmicpc.net/problem/1261 처음에 진짜 문제부터 이해 못할뻔했다. 뭔 알고스팟에 있다면....뭔 궁극의 무기 sudo.... 그냥 문제는 n*n 크기의 방들이 주어지고0은 지날 수 있는곳1은 벽이다. 그리고 1,1 위치부터 n,n 까지의 위치까지 가기 위해서 최소 몇개의 벽을 부숴야 하는가?에 대한 문제인것 문제 풀이에 앞서[BFS] 백준 13549번 숨바꼭질 3(C++)> n >> s; bfs(n);}void bfs(int temp){ queue" data-og-host="lee-soo.tistory.com" data-og-source-url="https://lee-soo.tistory.com/54" data-og-url="https://lee-soo.tistor..