프로그래밍

[C++] 백준 2606. 바이러스

문제 설명1번 노드와 연결되어 있는 노드가 몇 개인지 세면 된다.문제 접근단순한 그래프 순회 문제이므로 BFS를 이용한다.1번 노드와 연결된 노드의 개수만 세면 되므로, BFS는 1번 노드를 출발점으로 한 번만 돌아도 된다. 전체 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int numOfCom, numOfPair; cin >> numOfCom >> numOfPair; vector g[numOfCom + 1]; //인접 리스트 vector visited(101, false); /..

[C++] 백준 1927. 최소 힙

문제 설명자연수가 입력되면 배열에 추가하고, 0이 입력되면 가장 작은 수를 출력하고 배열에서 제거한다.배열이 비어 있을 때 0이 입력되면 0을 출력한다.문제 접근문제에서도 최소 힙을 사용하라고 되어 있고, 최소 힙은 가장 작은 수가 root에 있도록 정렬되기 때문에 문제에서 요구하는대로 배열이 구성된다. C++에서는 STL인 우선순위 큐를 이용하면 된다.priority_queue는 기본적으로 최대 힙이기 때문에, 옵션을 주어 최소 힙으로 동작하게 수정한다. 전체 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N,..

[C++] 백준 1764. 듣보잡

문제 설명들어본 적 없는 사람 목록과 본 적 없는 사람 목록을 받아 두 목록에 중복된 사람, 즉 '듣도 보도 못한 사람'을 찾는 문제이다.접근집합을 사용하면 사전순으로 자동 정렬된다.두 리스트에서 중복을 찾아내는 방법은 집합이 중복을 허용하지 않는 성질을 이용했다. 먼저 듣도 못한 사람 목록을 집합에 저장한다. 보도 못한 사람 역시 같은 집합에 저장한다. 이때 듣도 보도 못한 사람은 집합에 추가되지 않고, 집합의 크기가 변하지 않는다.보도 못한 사람을 추가했을 때 집합의 크기가 달라지지 않았다면 듣도 보도 못한 사람이다. 전체 코드#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin...

[C++] 백준 1620. 나는야 포켓몬 마스터 이다솜

문제 설명먼저 포켓몬 도감'에 입력할 포켓몬 이름 리스트를 입력받는다,이후 숫자를 입력하면 해당 도감 번호의 포켓몬 이름을 출력하고, 포켓몬 이름을 입력하면 도감 번호를 출력하는 문제이다.접근vector를 이용해서 도감을 구성하고, 이름을 입력받아 도감 번호를 출력할 때 find함수를 이용하면 시간 초과로 문제를 해결할 수 없다.자료 검색에 걸리는 시간을 줄이기 위해 해시 테이블 자료 구조를 사용한다.C++에서는 unnordered_map이라는 STL을 이용하면 된다. 자료 검색에 걸리는 시간복잡도가 O(1)이다. unordered_map m; for(int i = 1; i > s; m.insert({i, s}); } 1번부터 N번까지 해시 테이블로 도감을 만든다.  unorder..

[C++] 백준 1012. 유기농 배추

문제 설명직사각형 형태의 밭의 각 좌표마다 배추가 심어질 수 있다. 배추가 심어지면 1로 표현한다. 1로 이어진 구역이 몇 개인지 세는 문제다. 접근직사각형 형태의 밭은 2차원 배열로 표현할 수 있다.2차원 배열 상에서 이어진 1은 DFS나 BFS를 이용해 탐색할 수 있다.DFS나 BFS로 구역을 탐색하고, 한 구역의 탐색이 끝나면 벌레 개수를 증가시킨다.모든 구역이 탐색될 때까지 반복한다. 구현DFS를 이용하기로 한다.static int dx[] = { 0, 1, 0, -1 };static int dy[] = { 1, 0, -1, 0 };void DFS(int x, int y) { visited[x][y] = true; // 상하좌우 네 방향으로 이동 for (int i = 0; i = 0 && nx ..

[Rust] 스레드

스레드 이용하기spawn으로 새로운 스레드 생성새로운 스레드를 생성하려면 thread::spawn 함수를 호출하고, 스레드에서 실행하고 싶은 코드가 담긴 클로저를 넘긴다.use std::thread;use std::time::Duration;fn main() { thread::spawn(|| { for i in 1..10 { println!("hi number {} from the spawned thread!", i); thread::sleep(Duration::from_millis(1)); } }); for i in 1..5 { println!("hi number {} from the main thread!",..

[Rust] 스마트 포인터

러스트는 소유권과 대여의 개념을 가지고 있다. 참조자는 데이터를 빌리기만 하는 반면, 스마트 포인터는 가리킨 데이터를 소유한다.Box가장 직관적인 스마트 포인터로, 힙에 데이터를 저장할 수 있게 해준다.fn main() { let b = Box::new(5); println!("b = {}", b);}위와 같이 사용하면 b는 일반적인 코드와 똑같이 5라는 값을 나타낼 것이다. 5가 힙에 할당된다는 점만 다르다.재귀적 타입recursive type은 자기 안에 동일한 타입의 또 다른 값을 담을 수 있다. 컴파일할 때 모든 정보를 알아야 하는 러스트에 있어서 재귀적 타입은 문제를 일으킬 여지가 많다. 박스는 알려진 크기를 갖고 있으므로 박스에 넣으면 이를 허용할 수 있다. 콘스 리스트(cons l..

[Rust] 반복자

반복자반복자는 일련의 아이템을 순서대로 처리할 수 있게 해준다. let v1 = vec![1, 2, 3]; let v1_iter = v1.iter(); for val in v1_iter { println!("Got: {}", val); }반복자를 사용해 for 루프가 호출되면, 반복자의 각 요소가 루프의 한 순번마다 사용된다.Iterator 트레이트모든 반복자는 표준 라이브러리의 Iterator 트레이트를 구현한다.pub trait Iterator { type Item; fn next(&mut self) -> Option;}type Item 과 Self::Item 은 이 트레이트의 연관 타입을 정의한다. 트레이트를 구현하려면 Item 타입도 함께 정의되어야 하..