생각하는 아져씨

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 🚦 문제 유형 그래프 탐색 bfs, dfs ✅ 문제 설명 유기농 배추를 재배하려면 해충 방지에 효과적인 배추흰지렁이를 구입해야 합니다. 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면, 인접한 다른 배추도 해충으로부터 보호받습니다. 인접한 배추는 '상하좌우' 입니다. 군데군데 심어져있는 배추를 보호하기 위해서 최소 몇 마리의 지렁이가 필요한지 구해야 합니다. 입력의 첫 줄: 테스트 케이스 개수 입력의..

코딩테스트 '완전탐색' 문제를 풀다보면 순열, 조합을 사용해서 풀 때가 종종 있다. 순열, 조합은 파이썬의 itertools 라이브러리를 불러와 사용할 수 있고 몇 가지 메소드를 사용해 쉽게 구현할 수 있다. 파이썬 공식문서에는 다양한 종류의 itertools 함수가 존재하는데 오늘은 순열, 조합, 중복순열, 중복조합에 대해서 정리하려고 한다. 조합형 iterator에는 다음 4가지가 있다. iterator 이름 필요한 인자 출력 결과 product() 중복순열 (p, q, r, ..., repeat = n) 모든 데이터를 전부 결합한 결과(=Cartesian Product) permutations() 순열 (p,r) r길이의 튜플들, 순서 고려, 반복 요소 없음 combinations() 조합 (p, ..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 🚦 문제 유형 자료 구조 정렬 우선순위 큐 ✏️ Solution 파이썬의 heapq 라이브러리를 사용하여 우선순위 큐를 통해 문제를 풀 수 있다. N이 최대 1500이고 최대 2,250,000개의 값을 가질 수 있는데, 그 중 N번째 큰 수를 찾기위해 순차탐색을 하는 것은 시간초과가 뜰 것이다. 최댓값 또는 최솟값을 찾을 때 힙 자료구조를 활용하면 쉽게 구할 수 있다. N번째 큰 수를 찾는 방법은 모든 원소를 힙에 넣고 max_heap 구조에서 N번 heapq.h..

문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 🚦 문제 유형 자료구조 스택 연결 리스트 ✏️ Solution 이 문제는 시간제한이 0.3초로 매우 짧아서 시간복잡도를 생각하면서 풀어야 한다. 풀이 방법은 3가지를 생각해 볼 수 있다. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행 1. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행 입력 ..

파이썬에서 사용할 수 있는 나눗셈의 연산에는 다음과 같다. / // % divmod 4가지를 잘 구별해야 코드 짤 때 이상한데서 헤메는 일이 없어진다. 🤣 1. float형의 단순 나눗셈을 구해주는 / a = 10 b = 6 print(a / b) >>> 1.6666666666666667 float 형으로 반환해준다. 음수가 있어도 같다. a = -10 b = 6 print(a / b) print(abs(a) / b) >>> -1.6666666666666667 >>> 1.6666666666666667 2. 나눗셈의 몫을 구해주는 // a = 10 b = 6 print(a // b) >>> 1 나눗셈의 몫만 구해준다. 주의할 점: 음수일 때는 다르다. a = -10 b = 6 print(a // b) pr..

문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선..