목록알고리즘 문제풀이 (223)

홍시홍의 프로그래밍

[백준 1920] 수 찾기 (해시, 정렬)

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net 요구사항 첫번째 방법 1. 정렬하기 2. 탐색 두번째 방법 1. 해시로 탐색 1번 풀이 머지 소트로 정렬 후 -> 이분 탐색으로 찾기 2번 풀이 해시에 저장 -> 탐색하기 해시가 확실히 빠르다. #include using namespace std; int n,m; int map[100001..
알고리즘 문제풀이/백준 2020. 1. 8. 22:49
[백준 1976] 여행 가자

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 요구 사항 1. Union-Find 구현 풀이 1. 여행 경로가 주어졌을 때, 모든 여행지의 대표값이 동일한지 확인 #include u..
알고리즘 문제풀이/백준 2020. 1. 2. 23:44
[백준 1717] 집합의 표현

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 요구사항 1. Union-Find 자료 구조 기본 문제 풀이 1. 기본 구현 시간 초과 주의(입출력이 printf, puts 사용 할..
알고리즘 문제풀이/백준 2020. 1. 2. 23:14
[백준 1021]회전하는 큐

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 요구사항 1. 최소 연산으로 주어진 숫자를 꺼내기 풀이 1. 현재 뽑고자 하는 수가 어디에 있는지 찾기 2. 최소가 될 수 있도록 뽑는다 - size/2보다 클 경우 뒤에서 앞으로 이동 시켜주고, 아닐 경우 앞에서 뒤로 이동시킨다. 3. 정답 출력 #include using namespace std; int q[1..
알고리즘 문제풀이/백준 2019. 12. 19. 23:33
Prev 1 ··· 46 47 48 49 50 51 52 ··· 56 Next