[Python/파이썬] 백준 1644번 - 소수의 연속합

문제 설명 입출력 예제 풀이 코드 연속된 소수의 합을 구하기 위해서는 에라토스테네스의 체를 이용해 N까지의 소수를 구하고, 구한 소수 배열을 바탕으로 투 포인터를 활용해 연속된 소수의 합이 N이 되는지를 확인하여 정답을 구할 수 있다. 에라토스테네스의 체와 투 포인터에 대한 설명은 아래 링크에서 참고할 수 있다. [알고리즘] 투 포인터(Two Pointers)란? 투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에서 연속된(정렬이 hstory0208.tistory.com [Java/자바] 프로그래머스 - 소수 찾기 (에라토스테네스의 체) 문제 설명 1부터 입력받은 ..

• format_list_bulleted ◼ 코딩테스트/투포인터 (Two Pointer)
• · 2023. 7. 21.
• textsms

[Python/파이썬] 백준 1806번 - 부분합

문제 설명 입출력 예제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 코드 배열에서 특정한 합을 갖는 부분 연속 수열을 찾는 것은 투 포인터 알고리즘을 활용하는 대표적인 예이다. 투포인터 알고리즘에 대한 설명은 아래 링크를 통해 확인 할 수 있다. [알고리즘] 투 포인터(Two Pointers)란? 투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에..

• format_list_bulleted ◼ 코딩테스트/투포인터 (Two Pointer)
• · 2023. 7. 19.
• textsms

[Python/파이썬] 백준 1920 - 수 찾기

문제 설명 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 코드 이 문제의 주어지는 입력값의 허용 범위를 보면 100,000으로 시간복잡도OlogN 이나 O(n)으로 풀어야 한다. 그리고 모든 정수의 범위를 보면 -2^31 보다 크거나 같고 2^31보다 작다고 한다. 정수의 범위가 크기 때문에 OlogN의 시간복잡도를 갖는 이분탐색으로 이 문제를 해결하였다. 이분탐색 알고리즘에 대해 알고 싶다면 아래 링크를 참고하길 바란다. [알고리즘] Binary Sea..

• format_list_bulleted ◼ 코딩테스트/이분탐색 (Binary Search)
• · 2023. 7. 16.
• textsms

[Python/파이썬] 백준 11559 - Puyo Puyo (뿌요 뿌요)

문제 설명 입출력 예제 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 코드 bfs 알고리즘 문제 분류에 있는 문제였지만 구현에 가까운 문제였다. 구현문제 답게 문제의 요구사항에 맞게 구현하여 풀 수 있었다. 이 문제에서 필요한 기능은 상하좌우 동일한 블록 탐색, 블록 제거, 블록 떨어트리기 총 3가지로 해당 기능들을 메서드로 뽑아 코드를 작성했다. 아래의 코드 주석을 통해 문제를 쉽게 이해할 수 있을 것이라고 생각한다. 정답 코드 from collections import deq..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 14.
• textsms

[Python/파이썬] 백준 17142 - 연구소3

문제 설명 입력과 출력 입출력 예제 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 코드 이 문제는 삼성 SW 기출문제에 출제된 문제라고 한다. 삼성 SW 문제들이 좀 문제를 이해하는데 어렵지 않나 한다. 이문제도 마찬가지로 문제를 이해하기가 좀 어려웠다; 이 문제를 푸는 방식에 대해 설명하자면 바이러스 M개를 활성화 해야하므로 파이썬의 combinations를 이용해 활성화할 바이러스 M개의 위치의 조합들을 구하여 해당 좌표들을 큐에 넣고 탐색하도록 하였다. 그리고 그 활성화된 바이러스 좌표들을 시작으로 빈칸 ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 13.
• textsms

[Python/파이썬] 백준 14888번 - 연산자 끼워넣기

문제 설명 입력과 출력 입출력 예제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 코드 이 문제는 푸는 방법이 2가지가 있다. 바로 파이썬의 라이브러리인 permutations(순열)과 DFS로 푸는방법이 있다. 여기서 순열로 풀게 되면 pypy3는 제출 통과하지만 python3으로 제출 시 시간초과가 발생하게 되고 시간복잡도가 높다. 그러므로 나는 DFS로 푸는 방식을 선택하여 이 문제를 풀었다. 주어진 숫자들을 처음부터 시작하여, 주어진 부호..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 7. 10.
• textsms