본문 바로가기

알고리즘22

2-sat 쉽게 이해하기 [boj] 11280 2-SAT - 3 https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 2-sat은 2개의 변수가 or (v) 관계로 이어진 1개 이상의 절(clause)을 and (⋀)로 이었을 때, 전체 식의 결과가 true를 반환하는 변수가 존재하냐를 묻는 질문이다. 변수가 4개고 2개의 절이 있는 식 f의 예시는 아래가 있다. ¬ 기호는 not 을 의미한다. 예를 들면, a가 참(true)일 때, ¬a는 거짓(f.. 2023. 6. 13.
[BOJ] 백준 1517번: 버블소트 www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므.. 2021. 1. 11.
[자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 연결리스트란 연결리스트는 기차와 같습니다. 연결리스트는 동적으로 크기를 조절하므로 배열을 사용하는것 보다 메모리를 효율적으로 사용할 수 있다는 것이 장점입니다. 연결리스트는 다음 노드에 해당하는 현재 노드를 기준으로 왼쪽 노드, 오른쪽 노드의 연결로 구성됩니다. 편의상 왼쪽에 존재하는 노드가 더 앞선 순서를 갖는다고 가정하겠습니다. 단방향 연결리스트의 경우 다음 노드를 의미하는 next와 마지막 노드를 가리키는 last, 저장할 data 최소 세가지의 요소로 구성됩니다. (마지막 노드를 가리키는 요소를 가지고.. 2020. 10. 30.
[BOJ] 백준 1676번: 팩토리얼 0의 개수 www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net N! 은 1x2x3x4 x... N으로 곱하는 과정에서 10의 배수가 생길 때마다 0이 생깁니다. 다시 해석해보면 N!을 곱하는 전체 과정을 소인수 분해하여 2와 5의 개수를 찾으면 맨뒤에 오는 연속된 0의 개수를 알 수 있습니다. 좀 더 간단화시키면 2의 배수는 5의 배수보다 항상 많으므로 N! 를 소인수 분해하여 5의 개수를 찾으면 됩니다. 5, 10, 15, 20, .... 은 5를 1개 가지고 있습니다. 25, 50, 75, .... 는 5를 2개 가지고 있습니다. 125, 250, 375.. 2020. 9. 7.
[BOJ] 백준 11726번: 2xn 타일링, 타일링 문제 www.acmicpc.net/submit/11726/21279055 로그인 www.acmicpc.net 타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다. 타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다. 아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다. 각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다. 여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다. 좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다. 점화식은 피보나치 형태.. 2020. 9. 7.

티스토리툴바