[파이썬] 백준 4948 : 베르트랑 공준

[파이썬] 백준 4948 : 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 실버 2 정수론, 소수 판별 접근 에라토스테네스의 체로 소수를 판별하는 방법을 사용하면 간단하게 구할 수 있다. 다만 내가 작성한 방법은 pypy3에서만 통과되었다. 코드 import sys; input = sys.stdin.readline def isPrime(num): for i in range(2, int(num**0.5) + 1): if n..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms

[파이썬] 백준 3184 : 양

[파이썬] 백준 3184 : 양 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 실버 2 그래프, DFS, BFS 접근 울타리의 경계를 만날 때까지 영역 내의 다른 좌표들을 탐색해야 하므로 bfs가 적합하다. 좌표를 움직이되, 설정한 경계값을 넘지 않았는지, 방문하지 않았는지, 해당 좌표에 울타리가 존재하지 않는지 확인하고 만약 늑대가 있다면 늑대의 수를, 양이 있다면 양의 수를 더해준다. bfs의 탐색이 끝나는 경우는 울타리 내의..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms

[파이썬] 백준 2210 : 숫자판 점프

[파이썬] 백준 2210 : 숫자판 점프 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 실버 2 그래프, DFS, 브루트포스 접근 방문처리를 할 필요가 없으므로 브루트포스와 같은 접근을 해야 한다. 모든 좌표에 대한 DFS를 진행하고, 글자 수를 하나씩 채우다가 길이가 6이 되는 경우 그 문자열이 기존에 추가했던 적이 있는지 없는지를 확인하고 리스트에 추가한다. 마지막으로 해당 리스트의 길이를 출력한..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 28.
• textsms

C++ 02 : 문자열 입력받기, cin, getline()

C++ 02 : 문자열 입력받기, cin, getline() C++은 C와의 호환성으로 인해 문자열을 C-스트링 방식뿐만 아니라 String 클래스를 이용하는 방식도 이용할 수 있다. 헤더 파일을 사용하면 C언어에서 사용하는 strcmp(), strlen(), strcpy()와 같은 함수를 사용할 수 있다. C-스트링 방식 : \0으로 끝나는 문자 배열 char word[5] = {'G','r','a','p','e'}; 이러한 형태는 문자열이 아니라 단순 문자 배열이다. 문자열로 취급되기 위해서는 마지막에 \0(널문자)를 포함해야 한다. char word[6] = {'G','r','a','p','e','\0'}; #include using namespace std; int main() { char wor..

• format_list_bulleted C++
• · 2022. 3. 27.
• textsms

[파이썬] 백준 1260 : DFS와 BFS

[파이썬] 백준 1260 : DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 실버 2 그래프, DFS, BFS DFS, BFS의 구현 방법을 알고 있는 것을 전제로 제시된 문제이다. 다만 정점을 방문은 반드시 오름차순 순서로 이루어져야 하기 때문에, 인접한 정점들을 오름차순으로 정렬한 후에 접근할 수 있도록 구현해야 한다. bfs구현을 할 때는 시간 복잡도가 O(1)인 deque을 이용하는 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 27.
• textsms

[파이썬] 백준 11727 : 2xn 타일링 2

[파이썬] 백준 11727 : 2xn 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 실버 3 DP 도저히 규칙을 못 찾아서 노가다로 경우의 수를 구해봤다. 1 : 1 2 : 3 3 : 5 4 : 11 5 : 21 ... 3번째 의 5는 1번째의 1에 2를 곱한 값과 2번째의 3을 더한 값과 같다는 사실을 발견했다. 이를 점화식으로 나타내면 dp[i] = dp[i-2]*2 + dp[i-1]가 된다. 코드 import sys n = int(sys.stdin.read..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 26.
• textsms