2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 1. 문제 설명 예를 들어 1번~10번 정수는 연두색 박스의 범위이고 최솟값은 5, 최댓값은 100이다. 또 다른 예로, 8번~10번 정수는 주황색 박스의 범위이고 최솟값은 5, 최댓값은 81이다. 2. 구현 아이디어 1 - 맞았습니다!! Segment Tree를 사용하면 쉽게 풀 수 있는 문제이다. (대부분의 세그먼트 트리 문제가 세그먼트 트리를 구현만 하면 쉽게 풀리는 것 같다) [C++] 세그먼트 트리의 개념과 구현 ..

11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 처음에는 빡구현 문제라고 생각하여 규칙을 찾아내고자 애를 썼지만 잘 되지 않았다 😥 결국 다른 사람의 코드를 참고하였고, DP로 풀어야 하는 문제임을 알 수 있었다. DP 배열은 2차원 배열로, DP[i][j]는 i번째부터 j번째 파일을 합치는데 필요한 최소 비용을 의미한다. 파일을 합치기 전에는 특정 지점을 기준으로 파일이 나누어져있을 것이다. (like 분할정복에서 합치기 전에 나뉘었던 것처럼 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 설명 2. 구현 아이디어 1 - 정답입니다! 주어진 정보대로 그대로 구현하면 되는 문제였다. 하지만, vector와 map 중 어느 자료구조를 사용할지 조금 망설이느라 문제를 푸는데 다소 시간이 소요되었다. map이 생각보다 느린 자료구조이기 때문에 최대한 지양하려고 노력하고 있지만, 제한사항이 타이트하지 않아 map을 사용하였다. 소요 시간을 그나마 줄이기 위해 unordered_map을 사용하였다. 다음달에 가장 선물을 많이 받은 친구의 갯수를 출력할 때, map의 두번째 원소로 비교를 해주어야..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 별다른 아아디어 없이, MST 알고리즘을 적용하면 풀 수 있는 문제이다. 최소 신장 트리(MST, Minimum Spanning Tree) - 크루스칼, 프림 알고리즘 1. 최소 신장 트리란? 신장 트리(Spanning Tree)란 그래프의 모든 노드가 사이클 없이 연결된 부분 그래프를 의미한다. 신장 트리는 여러 개가 존재할 수 있으며, 이 중 모든 노드가 ..

1. 최소 신장 트리란? 신장 트리(Spanning Tree)란 그래프의 모든 노드가 사이클 없이 연결된 부분 그래프를 의미한다. 신장 트리는 여러 개가 존재할 수 있으며, 이 중 모든 노드가 최소 간선의 합으로 연결되었을 때를 최소 신장 트리(MST, Minimum Spanning Tree)라고 한다. 최소 신장 트리를 찾을 수 있는 대표적인 알고리즘 2가지가 있는데, 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼은 간선 중심, 프림은 정점 중심 알고리즘이다. 정점 대비 간선이 적으면(Sparsh Graph) 크루스칼을, 많으면(Dense Graph) 프림을 사용하는 것이 좋다. 크루스칼 알고리즘의 시간복잡도: O(ElogE) 프림 알고리즘의 시간복잡도: O(VlogV+ElogV) 둘 다 음의 간선이..

1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 주사위의 면이 한 줄짜리면 쉬울텐데 ...! 십자가 모양이라서 주사위 각 면에 있는 수를 어떻게 저장할지 고민되었다. 일단 동서남북으로 굴렸을 때 주사위의 도면 변화를 그려봤다. 주사위의 각 면을 1차원 리스트로 관리할 때, 그림 아래 적은 것처럼 각 면에 적힌 숫자가 어느 면으로 가야할지 정할 수 있다. 그래서 dice라는 원본 리스트를 만들고, 구르는 방향에 따라 원소의 위치를 변경한 newDice 리스트를 만들어 명령마다 dice를 newDice로 갱신해주었다. 나머지는 문제에 나와있는 그대로 코드로 구현하면 된다. #include using namespace std; int n, m, x, y, k; int board[20][20]; vec..