Jally's Story

☑️문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net ☑️문제 소개 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. ☑️문제 풀이 11660번과 같이 이번에도 구간 합을 이..

☑️문제 링크 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net ☑️문제 소개 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, ..

☑️문제 링크 https://softeer.ai/practice/6266 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai ☑️문제 소개 회사에는 N개의 회의실이 있다. 회의실 이용 규칙은 다음과 같다: - 회의실은 9시부터 18시까지만 사용 가능하다. 모든 회의의 시간은 이 안에 완전히 포함되어야 한다. - 회의는 정확히 한 회의실을 연속한 일정 시간 동안만 점유한다. 즉 각 회의는 (회의실, 시작 시각, 종료 시각)의 정보로 나타낼 수 있다. - 같은 회의실을 사용하는 회의 시간은 서로 겹칠 수 없다. - 한 회의가 끝나는 시각에, 같은 회의실에서 다른 회의가 시작하는 것은 허용된다. - 길이가 0인 회의, 즉 시작 시각과 종료 시각이 동일한 회의는 예약된 바 없으며, 새롭게 잡을..

☑️문제 링크 https://softeer.ai/practice/6267 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai ☑️문제 소개 오늘 일은 사람들이 사회적 거리 두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다. 현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N, M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x, y)이다. 점심시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해 준다. 현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi, yi)라고i,yi 하자. 이 상황에서 어떤 좌석 (X, Y)의 안전도 DX, Y..

최단거리 구하기 문제는 시간복잡도상 DFS보단 BFS가 더 낫다. BFS는 큐를 이용한다. **큐는 FIFO(First In First Out)** from collections import deque def solution(maps): n, m = len(maps), len(maps[0]) queue = deque([(0,0,1)]) #여기서 (0,0,1)은 튜플이다 directions = [(0,1),(1,0),(-1,0),(0,-1)] visited = [[False] * m for _ in range(n)] while queue: #큐가 비어있을 때까지 진행한다는 뜻 row, col, distance = queue.popleft() if row == n-1 and col == m-1: return..

1) 재귀함수 사용한 정답 def dfs(numbers, target, index, current_sum): #끝나는 조건 if index == len(numbers): if current_sum == target: return 1 else: return 0 #내가 원하는 것 positive = dfs(numbers, target, index + 1, current_sum + numbers[index]) negative = dfs(numbers, target, index + 1, current_sum - numbers[index]) return positive + negative def solution(numbers, target): answer = dfs(numbers, target, 0, 0) ret..

문제를 간단히 설명하자면, 크기가 다른 귤들이 있을 때 최대한 적은 종류로 k개를 만들 수 있는 종류의 수를 반환하는 솔루션을 만드는 것이다. 예를 들어, 귤의 크기가 1,2,2,3,3,4,5,5 이렇게 있다고 할 때 k가 5이라면 크기가 2인 귤 2개, 3인 귤 2개, 5인 귤 1개를 고르는 것이 가장 종류가 작은 것을 알 수 있다. 따라서 정답은 3이 된다. def solution(k, tangerine): answer = 0 tangerine.sort() j = 1 count = list() idx = 1 for i in tangerine: if i != tangerine[idx]: count.append(j) j = 1 else: j += 1 idx+= 1 if idx == len(tangerin..

Dynamic Programming 최적 부분 구조(Optional Substructure) : 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것 이렇게 문제를 풀 때 중복되는 부분 문제들이 나타난다(overlapping subproblems) 이를 해결하는 알고리즘 패러다임이 dynamic programming : 한번 계산 한 것을 활용하는 방식 Memoization 말 그대로 계산한 값을 메모하고 사용하는 방식 → 재귀 사용 하향식 방법(Top-Down) 예제 1) 피보나치 수열 def fib_memo(n, cache): # base case if n < 3: return 1 # 이미 n번째 피보나치를 계산했으면: # 저장된 값을 바로 리턴한다 if n in cache..

퀵 정렬 divide: 피벗(기준점)을 정해 파티션을 해준다 conquer: 정렬해주기 combine: 할 일 없음 합병 정렬과는 다르게 divide & conquer에서 대부분의 일이 일어남 파티션 하는 법 1. b, i 는 0 으로 시작하고 기준점인 p는 리스트의 마지막 값으로 한다 여기서 i는 1씩 커지면 리스트의 다음 요소와 기준점을 비교할 수 있도록 한다 2. 기준점보다 값이 작다면 b와 i의 값을 바꾸어주고 두 값 모두 1씩 올려준다 3. 기준점보다 값이 크다면 i의 값만 1씩 올려주어 리스트의 다음 값을 비교할 수 있도록 해준다 4. 이렇게 하면 기준점보다 작은 값끼리, 큰 값끼리 모여있게 된다 5. 마지막으로 b와 p를 인덱스로 가진 값을 바꾸어주면 p를 기준으로 왼쪽에는 더 작은 값이, ..

1. Brute Force(무차별 대입공격) → 말 그대로 모든 경우의 수를 다 살펴보는 것! 직관적이고 비교적 코드로 구현하기 쉽다. 또, 모든 경우의 수를 확인하므로 확실한 답을 얻을 수 있다는 장점이 있다. 인풋이 커질수록 비효율적이라는 단점이 있다. 예제) 빗물의 양 측정하기 def trapping_rain(buildings): # 총 담기는 빗물의 양을 변수에 저장 total_height = 0 # 리스트의 각 인덱스을 돌면서 해당 칸에 담기는 빗물의 양을 구한다 # 0번 인덱스와 마지막 인덱스는 볼 필요 없다 for i in range(1, len(buildings) - 1): # 현재 인덱스를 기준으로 양쪽에 가장 높은 건물의 위치를 구한다 max_left = max(buildings[:i]..