본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 1949번 : 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net tree를 만들고 dfs를 수행하며 top down dp로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 마을마다 주민수를 입력받아 일차원 배열에 저장합니다. 2. 인접리스트로 무방향 그래프를 만들어 줍니다. 이를 graph라는 vector형 변수에 저장합니다. 3. 루트노드에서 출발하여 문제에서 나온 규칙을 계속해서 지켜가며 트리의 아래로 내려간다면 결국 답이 나온다는 줄기..
(C++) - 백준(BOJ) 13565번 : 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net bfs문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. m, n을 입력받습니다. m은 행, n은 열입니다. 2. m행 n열만큼 이차원 배열인 board변수에 적절히 입력해줍니다. 📔 풀이과정 1. 아직 전류를 흘러보낸적이 없다면 ck = 0, 있다면 ck = 1로 생각합니다. 2. 0행에 해당하는 부분은 outer side에서 전류를 흘려보낸다고 생각할 수 있..
(Rust) - 백준(BOJ) 2557번 : Hello World https://www.acmicpc.net/problem/2557 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net PS의 국룰 hello world 출력하기였습니다. 📕 Code fn main() { println!("Hello World!") }
(C++) - 백준(BOJ) 12837번 : 가계부 (Hard) https://www.acmicpc.net/problem/12837 12837번: 가계부 (Hard) 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 www.acmicpc.net segment tree문제였습니다. 📕 풀이방법 📔 입력 및 초기화 기존의 값들은 모두 0에서 출발하므로 init을 만들 필요가 없습니다. 따라서 쿼리의 개수만큼 a,b,c라는 변수에 입력받습니다. 📔 풀이과정 1. a==1 이면 update함수를 수행합니다. 이는 변화값을 따로 계산해서 그 차이만큼만 해당하는 구간에 더해주는 것이 아니며 그저 더해주기만 하면 됩니다. 2. a==2이면 b ~ c까..
(C++) - 백준(BOJ) 14428번 : 수열과 쿼리 16 https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net segment tree로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 가장 작은 값, 그 중에서 가장 작은 인덱스를 뽑아야 하기 때문에 struct Node를 선언해 바로 index를 뽑을 수 있도록 변수들을 선언했습니다. 또한 min함수를 struct에 대해 사용하기 위해 연산자 오버로딩(함수 중복정의) 을..
(C++) - 백준(BOJ) 13224번 : Chop Cup https://www.acmicpc.net/problem/13224 13224번: Chop Cup Oisín is amateur magician and is big fan of Chop Cup routine which involves three cups face down and one ball underneath one of the cups. He's only started to practice the trick and wants to test out if you can follow where the ball is without any tricks www.acmicpc.net 구현문제였습니다. 📕 Code #include using namespace std; int cup[4] {0,1,0,0}; str..
(C++) - 백준(BOJ) 14427번 : 수열과 쿼리 15 https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net segment tree로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 가장 작은 값, 그 중에서 가장 작은 인덱스를 뽑아야 하기 때문에 struct Node를 선언해 바로 index를 뽑을 수 있도록 변수들을 선언했습니다. 또한 min함수를 struct에 대해 사용하기 위해 연산자 오버로딩(함수 중복정의) 을 사용했습니다. 수를 입력 받..
(C++) - 백준(BOJ) 14438번 : 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net segment tree문제였습니다. 📕 Code #include #define INF 0x3f3f3f3f #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n, q, num[100001], tree[..

티스토리툴바