오늘은 여기까지

https://www.acmicpc.net/problem/1182완전탐색으로 풀기파이썬의 combinations 함수를 통해 가능한 부분수열을 모두 구한다. 부분수열마다 합이 구하고자 하는 수와 같은지 비교한다.시간복잡도가 O(n * 2^n) 이므로 n이 큰 경우 통과하지 못할것 같다. 다른 풀이가 생각나면 풀어볼것import itertoolsn, s = map(int, input().split())sequence = list(map(int, input().split()))result = 0for i in range(1, n+1): for j in itertools.combinations(sequence, i): temp = list(j) if sum(temp) == s: ..

https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 무향 그래프, 양방향 그래프라는 점을 고려해서 풀어야 한다. A에서 B로 가는 길과 B에서 A로 가는 길을 동일하게 취급한다. dx, dy 문제와 유사하게 접근하되, 처음 지나간 길의 개수를 알고 싶으므로 집합 자료형을 활용한다.def solution(dirs): coordinate = {'U': (0, 1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)} vis..

https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 처음 풀이def solution(N, stages): fail = {} for i in range(1, N+1): win_cnt, challenge_cnt = 0, 0 for s in stages: if s > i: win_cnt+=1 challenge_cnt+=1 ..

https://www.acmicpc.net/problem/16937 1. 완전탐색이 가능한가?스티커의 개수는 최대 100개이다. 스티커 2개를 고르는 경우의 수는 100*99 = 9900가지이다.이때 고른 스티커가 모눈종이에 붙일 수 있는지 탐색하는 과정의 시간복잡도를 고려해야 하는데, 스티커마다 90도 회전을 시킬 수 있기 때문에 총 8가지 경우에 대해 탐색한다. (1. 둘다 회전하지 않은 경우 2. 하나만 회전한 경우 3. 다른 하나를 회전한 경우 4. 둘다 회전한 경우) * (1. 가로로 배치 2. 세로로 배치)따라서 고른 스티커 쌍마다 탐색하는 시간복잡도는 O(1)이다. 결과적으로 9900가지의 경우 수가 존재하고, 각 경우마다 O(1) 시간복잡도로 탐색하므로 완전탐색이 가능하다.2. 스티커 붙이..

https://www.acmicpc.net/problem/2503사용개념: 구현, 완전탐색 일단 완전탐색해서 구현할 수 있는지 확인해본다.1~9 사이 숫자 중 서로 다른 수 3개를 뽑아 만들 수 있는 모든 경우의 수는 504가지이다. (9C3)또 N은 100이하 자연수이다.따라서 504가지의 경우를 모두 돌면서 N개의 질문을 통해 후보인지 탐색해도, 시간 안에 탐색이 가능하다. 1. 모든 숫자 후보 만들기candidate = list(permutations([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)) # 125: (1, 2, 5) 이런식 2. 숫자 후보의 strike, ball 값 구하기get_result 함수는 숫자 후보와 민혁이 고른 숫자를 비교해 strike, ball 값을 리턴한다...

https://www.acmicpc.net/problem/2467 개념: 투 포인터, 이분탐색 N은 2 이상 100,000 이하의 정수이므로 순차탐색(이중 for문)은 최악의 경우 시간복잡도 O(N^2)가 1초를 넘어간다. 게다가 용액의 특성값이 정렬된 순서로 주어진다.풀이시간복잡도: O(N)0과 n-1을 투포인터로 지정한다.합이 0에 가까운 구간을 탐색한다.value는 현재 특성값의 합과 이전 값을 비교하기 위한 변수로, 우선 나올 수 있는 최대값인 2,000,000,000으로 설정했다.비교했을때, 현재 특성값의 합이 더 작다면 value, x, y값들을 업데이트 해준다.동시에 포인터를 조절해주기 위해 현재 특성값의 합이 0 이하면 왼쪽 포인터를 +1, 0보다 크면 오른쪽 포인터를 -1 만큼 움직인다...

https://www.acmicpc.net/problem/13702개념: 이분탐색 막걸리 양을 조절해가면서 막걸리를 K번 나눠줄 수 있는 최대값을 찾는 과정이다.  따라서 이분탐색으로 풀면 될 것이라고 생각했고, 막걸리를 K번 이상 나눠줄 수 있으면 mid값을 증가 시켜서 더 큰 값이 있는지 찾고 아니라면 mid값을 감소 시킨다.N, K = map(int, input().split())mliter = []for _ in range(N): mliter.append(int(input()))mliter.sort()start = 1end = max(mliter)while start= K: result = mid start = mid + 1 else: ..

https://www.acmicpc.net/problem/17266 개념: 이분탐색 이분탐색으로 가로등 높이를 탐색하려고 생각했는데, 특정 가로등 높이로 굴다리 전체를 밝힐 수 있는지 판별하는 함수를 구현하는데 오래 걸렸다.start = 1, end = N으로 설정해서 가로등 높이를 탐색한다.checkLight 함수는 특정 가로등 높이로 굴다리 전체를 밝힐 수 있는지 판단하는 함수다.prev 변수는 마지막으로 밝혀진 위치이다.가로등 위치를 순회한다.현재 가로등 위치에서 높이를 뺀 값이 prev보다 크면, 이전 가로등과 현재 가로등 사이에 어두운 부분이 있다는 뜻이다. 따라서 False를 반환한다.그렇지 않으면, prev를 현재 가로등이 비추는 가장 먼 위치로 업데이트한다. (p + height)모든 가로..

https://www.acmicpc.net/problem/2805사용 개념: 이분탐색 start = 1, end = 나무 최대 높이로 설정하고 절단기 높이(mid)를 조절해 나간다.벌목된 나무 길이가 M보다 크면 절단기 높이를 올려야 하므로 start = mid + 1으로 조정, M보다 작으면 절단기 높이를 낮춰야 하므로 end = mid - 1으로 조정한다.import mathn, m=map(int, input().split())tree=list(map(int, input().split()))start, end = 1, max(tree)while start=mid: log += i - mid if log >= m: start = mid + 1 ..

https://www.acmicpc.net/problem/11663 사용되는 개념: 이분탐색선분의 시작점(a)부터 끝점(b) 사이 점의 개수는 'b보다 큰 점의 index' - 'a보다 크거나 같은 점의 index'로 구할 수 있다.이는 다른 말로 upperbound, lowerbound의 개념으로 볼 수도 있다.  Upper Bound, Lower Bound이분탐색은 '원하는 값을 찾는 과정'이라면, Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고 Upper Bound는 '원하는 값이 나오는 마지막 위치'를 찾는 과정이라고 볼 수 있다.Upper Bound는 특정 값을 초과하는 첫 번째 위치를 반환한다.Lower Bound는 특정 값 이상인 값인 첫번째 위치를 반환한다.둘의 가..