본문 바로가기

백준/C++

 (135)
[C++] 백준 10871번 - X보다 작은 수 이번에는 동적할당에 대한 문제를 풀어보고 싶어서 이 문제를 가져와보았다. 문제 10871번 https://www.acmicpc.net/problem/10871 10871번: X보다 작은 수 첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 자체는 간단하다. 정수 N개로 이루어진 수열 A에서 X보다 작은 수를 모두 출력하면 되는 문제이다. 그런데 여기서 그냥 num[10000] 이런 식으로 배열의 최대 크기만큼 설정해준다면 메모리 낭비가 생긴다. 그러므로 동적할당을 해주는 것이 좋다. 동적할당은 미리 배열의 크기를 설정해놓..
[C++] 백준 10773번 - 제로 문제 10773번 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 입력받은 값을 vector에 저장해준다. 그리고 벡터의 사이즈 만큼 반복문을 돌려서 0이 있는지 확인한다. 만약 0이라면 해당 인덱스와 최근에 쓴 수의 인덱스를 erase()를 통해 지워준다. 여기서 지운 인덱스 2개를 빼줘야한다. 마지막으로 accumulate로 합을 구해준다. #include #include #include using name..
[C++] 백준 4963번 - 섬의 개수 문제 4963번 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 갈 수 있는 8가지 방향을 dy, dx로 나누어 저장해준다. while문을 이용해 입력받은 값에 대한 섬의 개수를 구해준다. map 배열에 입력받은 값들을 넣어주고, map에 섬이 있는 부분인데 방문을 안 한 부분이라면 dfs를 수행해준다. 그리고 count를 올려준다. 만약 입력받은 w와 h가 0이라면 반복문을 빠져나와준다. #include using namespace st..
[C++] 백준 1697번 - 숨바꼭질 으... 너무 졸리다... 문제 1697번 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include #include using namespace std; int n, k; bool visited[100001]; void bfs(int n) { queue q; q.push({ n,0 }); while (!q.empty()) { int x = q.front().first; int cnt = q.fr..
[C++] 백준 2178번 - 미로 탐색 문제 2178번 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 흑흑... 또 까먹었다... 이것도 예전에 풀었던 건데... 다시 그걸로 공부하고 작성해 보았다. #include #include #include using namespace std; int map[100][100]; int n, m, k; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int bfs(int f, int s) { queue q; q.push({ f,s });..
[C++] 백준 2606번 - 바이러스 오늘도 dfs/bfs 문제~~ 문제 2606번 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 이 문제는 dfs나 bfs로 풀면 되는 문제인데, 나는 그냥 bfs로 접근해 count를 1씩 증가시켜가며 문제를 해결하였다. 어제 공부해놔서 그런지 쉽게 풀렸다. #include #include #include #include using namespace std; bool visited[1001]; vector node[1001]; void bfs(int..
[C++] 백준 1260번 - DFS와 BFS 예전에 공부했지만 까먹은 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 문제를 풀어보려고 한다. DFS와 BFS는 그래프를 탐색하는 방법이다. 여기서 그래프는 정점과 그 정점을 연결하는 간선으로 이루어진 자료구조를 말한다. DFS는 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동한다. BFS는 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다. 문제 1260번 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다...
[C++] 백준 1300번 - K번째 수 지금까지 정렬 문제를 풀어봤는데 오늘부터 이분 탐색 문제를 풀어보려고 한다. 문제 1300번 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 처음에는 벡터를 이용하여 풀어볼까 했는데 뭔가 어려운 느낌이 들어서 찾아보니 이런 식으로 푼 분도 있었다. #include #include #include using namespace std; int main() { int n,k; cin >> n >> k; int start..

티스토리툴바