본문 바로가기

tree

 (11)
[문제해결기법] 6. 세그먼트 트리 1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right..
[코드트리] 정육면체 한번 더 굴리기 - 시뮬레이션 (기출문제) 삼성 SW 역량테스트 2021 하반기 기출 정육면체 한번 더 굴리기 1이상 6이하 중 임의의 숫자가 그려진 n * n 격자판에 한 면이 1 * 1 크기인 정육면체를 놓여져 있습니다. 해당 격자판에서 정육면체를 굴리려합니다. 다음과 같이 4 * 4 크기의 격자판이 주어졌다고 가정해보겠습니다. 처음 정육면체의 각 면에는 1부터 6까지의 숫자가 다음과 같이 쓰여져 있고 m번에 걸쳐 주사위를 계속 1칸씩 굴리게 됩니다. 이때, 마주보는 면에 적혀있는 숫자의 합은 정확히 7입니다. 주사위는 항상 초기에 격자판의 1행 1열에 놓여져 있고, 처음에는 항상 오른쪽으로 움직입니다. (중략) n * n 크기의 격자판의 상태가 주어졌을 때, m번 진행하며 얻게되는 점수의 총 합을 구하는 프로그램을 작성해보세요. 입력 형식 ..
[코드트리] 코드트리빵 - 시뮬레이션 (기출문제) 삼성 SW 역량테스트 2022 하반기 기출 코드트리빵 최근 코드트리 빵이 전국적으로 인기를 얻어 편의점에서 해당 빵을 구하기 힘들어졌습니다. 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, ..., m번 사람은 정확히 m 분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작합니다. 사람들은 출발 시간이 되기 전까지 격자 밖에 나와있으며, 사람들이 목표로 하는 편의점은 모두 다릅니다. 이 모든 일은 n*n 크기의 격자 위에서 진행됩니다. 코드트리 빵을 구하고 싶은 사람들은 다음과 같은 방법으로 움직입니다. 이 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행되어야 함에 유의합니다. 격자에 있는 사람들 모두가 본인이 가고 싶은..
[코드트리] 싸움땅 - 시뮬레이션 (기출문제) 삼성 SW 역량테스트 2022 하반기 기출 싸움땅 인기 게임인 싸움땅은 다음과 같은 방식으로 진행됩니다. 게임은 n * n 크기의 격자에서 진행되며, 각각의 격자에는 무기들이 있을 수 있습니다. 초기에는 무기들이 없는 빈 격자에 플레이어들이 위치하며 각 플레이어는 초기 능력치를 가집니다. 각 플레이어의 초기 능력치는 모두 다릅니다. 게임은 다음과 같은 방식으로 진행됩니다. 아래 그림에서 빨간색 배경의 숫자는 총의 경우 공격력을, 플레이어의 경우 초기 능력치를 의미하며, 노란색 배경의 숫자는 플레이어의 번호를 의미합니다. 하나의 라운드는 다음의 과정에 걸쳐 진행됩니다. 1-1. 첫 번째 플레이어부터 순차적으로 본인이 향하고 있는 방향대로 한 칸만큼 이동합니다. 만약 해당 방향으로 나갈 때 격자를 벗어나는 ..
[코드트리] 나무박멸 - 시뮬레이션 (기출문제) 삼성 SW 역량테스트 2022 상반기 기출 나무박멸 n * n 격자에 나무의 그루 수와 벽의 정보가 주어집니다. 나무의 성장과 번식력이 좋아서 제초제를 뿌려 나무의 성장을 억제하고자 합니다. 제초제의 경우 k의 범위만큼 대각선으로 퍼지며, 벽이 있는 경우 가로막혀서 전파되지 않습니다. 다음과 같이 초기 조건이 주어진다고 가정할 때, 1년동안 나무의 성장과 억제는 다음과 같이 이뤄집니다. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장합니다. 성장은 모든 나무에게 동시에 일어납니다. (중략) 각 3개의 과정이 1년에 걸쳐 진행된다고 했을 때, m년 동안 총 박멸한 나무의 그루 수를 구하는 프로그램을 작성해보세요. 입력 형식 첫 번째 줄에 격자의 크기 n, 박멸이 진행되는 년 수 m, 제초제의 ..
[코드트리] 예술성 - 시뮬레이션, BFS/DFS (기출문제) 삼성 SW 역량테스트 2022 상반기 기출 예술성 예술가 Sam은 그림에 대한 예술성을 평가하는 알고리즘을 만들어냈습니다. 그림을 편의상 n * n 크기의 격자로 생각하고, 각 칸의 색깔을 1이상 10이하의 숫자로 표현하여 이 알고리즘을 적용해보려 합니다. 다음은 5 * 5 크기의 그림의 예시입니다. 먼저 이 그림에서 동일한 숫자가 상하좌우로 인접해있는 경우 동일한 그룹이라 본다면, 총 4개의 그룹이 만들어지게 됩니다. 예술 점수는 모든 그룹 쌍의 조화로움의 합으로 정의됩니다. 그룹 a와 그룹 b의 조화로움은 (그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수로 정의됩니다. ..
[코드트리] TreeSet 연습문제 문제 : top K 숫자 n개의 숫자가 주어졌을 때, 중복을 제외하고 내림차순으로 정렬했을 때 앞에 있는 k개의 숫자를 출력하는 프로그램을 작성해보세요. 입력 형식 첫 번째 줄에는 원소의 개수 n과 k가 공백을 사이에 두고 주어집니다. 두 번째 줄에는 n개의 원소가 공백을 사이에 두고 주어집니다. 1 ≤ k ≤ n ≤ 100,000 1 ≤ 주어지는 원소 값 ≤ 109 출력 형식 중복을 제외하고 내림차순으로 정렬했을 때 앞에 있는 k개의 숫자를 공백을 사이에 두고 출력합니다. 중복을 제외했을 때 원소의 개수가 k보다 작은 경우는 없다고 가정해도 좋습니다. 나의 풀이 #include #include using namespace std; int main() { int n; int k; int a; set s..
[코드트리] Hash Set SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. unordered_set STL C++에서는 unordered_set이라는 STL을 이용할 수 있습니다. unordered_set은 HashSet 자료구조로 되어있으며, 이 HashSet이 바로 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. 모든 함수의 시간복잡도는 O(1)입니다. unordered_set은 set보다 속도가 빠르지만, 값의 존재 여부에만 관심이 있지 그 순서에는 전혀 관심이 없는 자료구조입니다. #include 헤더와, unordered_set name; 형태의..
728x90

티스토리툴바