Lumiere, and s5unnyjjj

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 처음에 문제를 보고 단순히 이전 층에서 i호까지 더하는 for문을 사용하여 완전탐색으로 계산 하면 된다고 생각했다. 그런데 문제 조건 중에 시간 제한이 0.5초 라는거 보고 완전탐색이 아닌 dp를 사용해야겠다는 생각이 들었고 바로 규칙을 찾으려 했다. ▶ 규칙은 어렵지 않았다. a층 b호는 a-1층 1~b호까지의 합을 구하면된다. a층 b-1호는..

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 문제 조건이 "잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만든다"이다. ▶ 두번째 줄 입력값은 왼쪽 전봇대의 번호에 따라 연결된 오른쪽 전봇대의 번호가 나열되어있다. 그 뜻은 왼쪽 전봇대와 연결된 오른쪽 전봇대의 번호가 오름차순으로 연결되어있으면 꼬이지 않는 것이다. 즉, 오..

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ LIS 알고리즘 공부를 많이 했더니 "내림차순 배치와 동시에 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다." 라는 문구를 보자마자 LIS 알고리즘이 떠올랐다. 하지만 다른점은 LIS알고리즘은 오름차순으로 정렬했다면 해당 문제는 내림차순정렬이다. ▶ 그래서 binary_se..

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 보자마자 완전 탐색으로 하기에는 정수의 개수가 너무 크다는 조건이 걸려서 이분탐색으로 풀어야 겠다고 생각했다. ▶ 수첩2를 기준으로 출력하는 것이기떄문에 수첩2 내 값의 위치를 바꾸면 안된다. 하지만 수첩1의 경우에는 수첩1 내에 값이 존재하는지 여부만 출력하는 것이지 인덱스를 출력하는 것이 아니기 때문에 수첩..

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 처음에 이 문제를 보자마자 용액의 특성 값을 담고 있는 배열의 모든 원소들에 절대값을 적용한채로 오름차순으로 정렬한 다음, 앞 뒤로 더해서 제일 작은 값을 찾아가면 된다고 생각했다. 그러면 총 세 단계가 된다. STEP1. 배열의 모든 원소들에 절대값을 적용한다.(원소에 음수도 포함되어 있기 때문이다..

백준 사용 언어: Python 문제 링크: https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 처음에 이 문제를 보자마자 조합문제일까 생각해보았지만, n의 개수가 10,000보다 작거나 같다는 조건을 보고 dp문제일 것 같다는 생각이 들었다. 그래서 규칙을 찾고자 우선 5정도까지 다 작성해보았다. ▶ 이렇게까지 작성해보고 n 값이 그 값..

프로그래머스 사용 언어: Python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 처음에는 아래와 같이 작성해보았다. def solution(triangle): if len(triangle) == 1: return triangle[0] answer = 0 dp = [] dp.append(triangle[0]) for i in range(1, len(..

프로그래머스 사용 언어: Python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr *** 본 문제를 푸는 과정을 공유하려 한다. ▶ 아래와 같이 작성해보았다. import re from itertools import permutations def calculation(n1, n2, operation): if operation == '-': return n1 - n2 elif operation == '*': return n1*n2..