본문 바로가기

Algorithm16

BOJ 3273 ) 두 수의 합 (C++) https://www.acmicpc.net/problem/3273만만하게 봤는데 생각보다 오래 걸렸다.N이 10^6이기 때문에 무작정 이중 for문을 돌려버리면 시간초과가 난다. ai + aj = x (1 ≤ i 1000000보다 작거나 같은 자연수이기 때문에 x - ai 가 범위를 벗어나지 않는지도 체크해 주어야 한다는걸 놓치는 바람에 헤맸다. #include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin>>n; vector v = vector(n); vector v1 = vector(1000002); for(int i=0;i>v[i]; } ci.. 2024. 7. 17.

BOJ 15738 ) 뒤집기 (C++) 15738번: 뒤집기 첫째 줄에 배열 A의 크기 N(1 ≤ N ≤ 100,000)과 위치 K(1 ≤ K ≤ N), 연산의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째에는 배열 A에 들어있는 수가 1번째 수부터 순서대로 주어진다. 배열에 들어있는 www.acmicpc.net algorithm 헤더의 reverse 함수를 사용하면 쉽게 해결이 가능한 문제다. 문제에서는 배열의 원소도 입력해주지만 실제 문제를 푸는 데에는 필요가 없으므로 입력만 받고 배열에는 몇 번째원소인지를 입력해주었다. 그 다음 들어오는 입력에 따라 reverse 함수를 이용해 배열을 뒤집어주고 마지막에 전체 배열을 돌면서 K번째 원소가 몇번째에 위치하고 있는지를 출력해 주면 된다. #include #include #inclu.. 2022. 6. 20.

BOJ 15705 ) 단어 찾기 (C++) https://www.acmicpc.net/problem/15705 15705번: 단어 찾기 N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다. 단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오. 단어 S가 표에 존재하려면, 표의 한 칸에서 시작 www.acmicpc.net 모든 경우를 다 시도해보면 되는 간단한 문제다. 단어의 첫 문자와 배열에 저장된 문자가 같으면 거기서부터 탐색을 시작한다. search 함수에서 시작점으로부터 어느 방향으로 탐색을 진행할지를 정하고, dfs 함수를 호출해 해당 방향으로 계속해서 탐색을 진행한다. 마지막 문자까지 일치하면 true를 반환하고 종료한다. #include #include #define pii pair #defi.. 2022. 6. 19.

BOJ 3190 ) 뱀 (C++) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 큐에 뱀의 몸 좌표를 넣어주고 이동마다 머리와 꼬리를 관리해준다. 처음에 접근을 잘못해서 매 이동마다 큐 내부의 모든 몸의 좌표를 이동시켜주려고 하다가 포기했었는데 생각해보니 머리와 꼬리만 관리해줘도 상관없겠다는 결론에 이르렀다. dir이라는 변수를 두고 왼쪽 회전인 경우 -1, 오른쪽으로 회전인 경우 +1을 해줌으로써 방향 관리를 해주고 cnt와 routeidx로 해당 회차에 방향 이동이 일어나는지를 관리해줬다. 매 이동에서 다음 좌표에 과일이 있으면 좌표를 큐에 넣.. 2022. 6. 16.

BOJ 5921 ) Escaping the Farm (C++) 5921번: Escaping the Farm The cows have decided on a daring plan to escape from the clutches of Farmer John. They have managed to procure a small inflatable raft, and during the cover of night, a group of cows will board the raft and row across the river bordering the farm. The pla www.acmicpc.net 소가 20마리밖에 되지 않으므로 모든 경우를 고려해도 된다. DFS를 이용해 각 소를 배에 태울지 말지를 고른 후 N번째 소에 대한 선택까지 끝나면 각 자릿수의 합에서 자리올림이 .. 2022. 6. 13.

BOJ 2428 ) 표절 (C++) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net N이 10^6이므로 쌍을 찾기 위해 이중 for문을 돌릴 경우 시간초과가 난다. binary search를 써야하고 (i,j)와 (j,i)는 같은 케이스 이므로 i=0.9*v[n]; } int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin>>N; int t; for(int i=0;i>t; v.push_back(t); } sort(v... 2022. 6. 9.

이전 1 2 3 다음

티스토리툴바