분류 전체보기(301)
-
[중급 알고리즘] Union-Find, Heap, BST
Union-Find - 처음에는 parent[i] = i로 초기화한다. - find로 조상의 루트로 갱신함과 동시에 리턴한다. 이를 통해 트리의 레벨을 최소화해 시간복잡도를 낮춘다. → 경로 압축 - 그냥 타고타고 올라가서 조상의 번호를 리턴하면 최대 시간복잡도는 $O(N)$이가 되기 때문이다. - 트리의 랭크는 높이와 같은 의미를 갖지만 경로 압축을 사용하면 높이와 다른 값을 가질 수도 있다. 따라서 높이 대신 랭크라는 표현을 사용한다. - 랭크가 작은 것을 랭크가 높은 것의 자식으로 만든다. 💚 2606 바이러스 - 컴퓨터가 연결된 상태가 주어진다. - 1번 컴퓨터가 웜 바이러스에 걸렸을 때 웜바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제 DFS를 통해 모든 컴퓨터 연결 상태를 탐색할 수 있다. ..
2022.07.02 -
[AtCoder] Filling 3x3 array
https://atcoder.jp/contests/abc256/tasks/abc256_c C - Filling 3x3 array AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 각 행과 각 열의 합이 정해져있으므로 만약 행과 열마다 2개 요소가 정해지면 나머지 하나의 요소의 값은 정해지는 구조이므로 N은 최대 30이고, 시간복잡도는 $O(N^4)$으로 그리 크지 않다. #include #include using namespace std; int h[3]; int w[3]; int arr[3][3]; int main() {..
2022.06.30 -
[AtCoder] Batters
https://atcoder.jp/contests/abc256/tasks/abc256_b B - Batters AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 시간 제한이 2초라서 사실 딱히 별다른 알고리즘을 풀지 않고 그냥 구현해도 무방하다. 그래도 그러면 재미없으니까 최대한 효율적으로 풀어보려 노력했다. 누적합(Prefix Sum)을 사용하면 시간복잡도 $O(N)$를 사용해 매 piece마다 마지막 위치를 예상할 수 있다. #include using namespace std; int arr[100]; int suffi..
2022.06.30 -
[백준] 2240: 자두나무
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 인간은 망각의 동물이라 그랬나.. 요즘 바쁘다보니 알고리즘 풀이를 2주 정도 쉬었더니 엄청나게 실력이 대폭 줄어있었다..ㅠ 더 열심히 하자...ㅎㅎ 우선 점화식을 잘 세워야한다. 메모이제이션의 대상은 추후에도 계속 사용될 가치가 있는 값이어야 한다. 그리고 여기서는 단순히 최대의 자두를 고르는 것이 아니라 제한된 이동 수 안에서 자두의 수를 최대화해야한다. 그렇다면 점화식에 필요한 파라미터는 시간, 현재 ..
2022.06.30 -
[MongoDB] 소개와 설명
NHN 포스트에 상당히 잘 안내가 되어있어서 참고하면 좋다. https://meetup.toast.com/posts/275 특징 도큐먼트 데이터베이스 도큐먼트는 필드와 값의 쌍으로 구성되며, 관계를 갖는 데이터를 중첩 도큐먼트와 배열을 사용해 1개의 도큐먼트로 표현 유연한 스키마 스키마의 선언 없이 필드의 추가와 삭제가 자유로운 Schema-less 구조이다. 컬렉션 내 모든 도큐먼트들의 필드 집합이 동일하지 않고 같은 필드라도 데이터 타입이 다를 수 있는 비정형 스키마 비관계형 데이터베이스 RDBMS의 관계 개념이 없다. 조인을 지원하지 않는다. 대신 임베디드 방식의 도큐먼트 구조를 사용하거나 레퍼런스 방식의 도큐먼트 구조를 사용한 후 애플리케이션에서 조인 비트랜잭션 mongoDB는 트랜잭션을 지원하지..
2022.06.25 -
[중급 알고리즘] 스택
LIFO의 특성을 활용 💚 9935 문자열 폭발 - 문자열 S에서 폭발 문자열 T를 모두 지우는 문제 - 스택에 넣는 것은 (문자열의 인덱스, 폭발 문자열에서 인덱스) - 현재 문자가 폭발 문자열의 첫 번째 문자와 같으면 스택에 넣는다. - 다른 경우에 스택에 비어있으면 그냥 넘어간다. - 다른 경우에 스택이 비어있지 않으면 스택의 가장 위에 있는 것의 폭발 문자열의 인덱스를 가져온다. 이 인덱스를 p라고 한다. - 현재 문자가 폭발 문자열의 p + 1와 같으면 스택에 넣는다. (p + 1이 폭발 문자열의 마지막 문자면, 폭발 문자열을 찾은 것이다. 스택에서 폭발 문자열을 지운다.) - 다르면 스택을 모두 비워버린다. - 폭발 문자열의 길이가 1이면 스택을 사용할 수 없기 때문에 그냥 for문을 돈다. ..
2022.06.24