본문 바로가기

전체162

백준 알고리즘 1541 (잃어버린 괄호) - python 백준 알고리즘 1541 (잃어버린 괄호) - python > https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net '+'와 '-', 그리고 숫자로만 이루어져 있는 수식을 최소값으로 만드는 문제 [문제 풀이] 1. '-'가 나온 후로는 다시 '-'가 나오기 전까지 괄호를 치는 것이 최소값이 된다. - 먼저 '-'를 기준으로 split - 첫 idx는 무조건 양수일 수 밖에 없음 (값+) - 그 이후의 idx는 각 요소들을 더하여 빼줌 (값-) 2.. 2022. 7. 8.
Learning Keep Leaning for Deep Learning. by think_why 2022. 7. 7.
백준 알고리즘 14889 (스타트와 링크) - python 백준 알고리즘 14889 (스타트와 링크) - python > https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 두 팀으로 나눠서 합산의 차이가 가장 적도록 만드는 문제. 백트래킹과 시간 효율이 중요한 문제이다. (처음엔 시간초과로 멘붕이었다가 다시 해결) [문제 풀이] 1. 절반(N//2명으로 구성)을 선택하여 조합을 생성 : DFS 탈출 조건 - 나머지 N//2명은 자동으로 결정됨 2. 예외 처리 - _min이 0일 경우에는 더 진행할 필요가 없음 3. 구해진 조.. 2022. 7. 4.
백준 알고리즘 1992 (쿼드트리) - python 백준 알고리즘 1992 (쿼드트리) - python > https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 문제인데, 주의할 점이 몇 가지 있다. 1. 4분할에 대한 4분면의 해당 순서 2. 시작 '(' 의 괄호를 넣는 위치 - 한 사분면 전체가 같지 않다는 것을 파악하면 대입 - 만약 입력 전체가 1이면 '(1)'이 아니라 그냥 '1'이다. 3. 끝 ')'의 괄호를 넣는 위치 - 한 사분면이 끝날 때 대입 [예시 입력] 8.. 2022. 6. 30.
백준 알고리즘 11399 (ATM) - python 백준 알고리즘 11399(ATM) - python > https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 전형적인 그리디 알고리즘, 누적 문제 [문제 풀이] 1. 뒤로 갈수록 누적이 되기 때문에 작은 순서대로 정렬 2. i번째의 수는 누적될 때 (N-i)번 누적되는 알고리즘 3. 누적 후 출력 import sys N = int(sys.stdin.readline()) people = list(map(int, sys.stdin.readline().split())) people.so.. 2022. 6. 30.
백준 알고리즘 1436 (영화감독 숌) - python (재풀이) 백준 알고리즘 1436 (영화감독 숌) - python > https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 666이 들어간 수열을 순서대로 찾는 문제. str으로 접근하니 간단했다. [문제 풀이] 1. 666에서 시작하여 str 기준으로 먼저 '6'을 발견하면 2. 그 idx부터 3개가 '666'인지는 체크 3. 맞으면 N을 -1하고 체크는 중단 4. 숫자를 올리면서 계속 반복 5. N == 0이 되면 출력 import sys N = int(.. 2022. 6. 29.
백준 알고리즘 1018 (체스판 다시 칠하기) - python (재풀이) 백준 알고리즘 1018 (체스판 다시 칠하기) - python > https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net W 또는 B로 시작하는 격자 무늬 체스판 다시 칠하기! 8 x 8의 판을 이용한다는 특징이 있다. [문제 해결] 1. 최소값 _min은 8 x 8 64로 설정 2. 8 x 8의 기준이 될 좌상단 index를 기준으로 하는 i, j for문 3. (0,0)이 W라고 가정하고 틀린 경우를 cnt에 누적한다. 정반대의 경우는 64.. 2022. 6. 24.
백준 알고리즘 14888 (연산자 끼워넣기) - python (재풀이) 백준 알고리즘 14888 (연산자 끼워넣기) - python > https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백트래킹의 컨셉에 충실! 식의 계산은 앞에서부터 진행! 계산을 하면서 각 연산자 count를 -1 -> dfs 진행 -> 다시 count +1 [문제 풀이] 1. 탈출 조건 : depth == N _max와 _min을 global로 이용하여 저장 2. result를 dfs에서 계.. 2022. 6. 22.
성장 보통은 성장하기 위해서 많은 것을 시도해보지만, 가장 많이 성장한 사람은 조금씩 시도하면서 하지 말아야할 것을 하지 않는 사람인 것 같다. by think_why 2022. 6. 18.
728x90