📍문제 링크https://www.acmicpc.net/problem/1475 1475번: 방 번호첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.www.acmicpc.net 📍알고리즘 분류- 구현 📍문제 풀이1 ~ 1,000,000 사이의 숫자가 주어진다. 0 ~ 9 의 숫자들이 쓰인 횟수 중 가장 많은 횟수를 구하라- 단, 6, 9 는 뒤집어서 서로 대체할 수 있다 각 숫자들이 쓰인 횟수를 딕셔너리에 기록하고, 6과 9의 경우, 평균을 구해 올림하여 기록한다.그리고 딕셔너리를 순회하며 최댓값을 구하면 된다 📍코드 (Python)import math# 숫자를 입력받고 하나씩 쪼개 배열에 저장num_arr = list(map(int, list(input..

📍문제 링크 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 1️⃣피보나치 수열임을 파악하기 - 1 2 3 4 5.. N 의 N명이 양 옆으로만 움직일 수 있을 때 가짓수는 피보나치 수열 fib(N)과 일치 - 즉, fib(N) = fib(N - 2) + fib(N - 1) 그 이유는, N번째 사람이 N 자리일 수 있고, N-1 자리일 수 있는데, i) N 자리이면 N-1명의 가짓수인 fib(N-1)에 해..

📍문제 링크 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 📍알고리즘 분류 - 누적 합 - 슬라이딩 윈도우 📍문제 풀이 - 주어진 수열에서 연속된 N개의 최댓값과 가능한 갯수를 출력하라 - Sliding Window 알고리즘을 사용하면 O(N^2) 대신 O(N)으로 해결이 가능 📍Sliding Window - 배열이나 문자열같은 일련의 데이터셋에서 특정 조건을 만족시키는 (예 - 일정 구간의 최댓값) 하위 집합을 찾을 때 유용 - wi..

📍문제 링크 https://www.acmicpc.net/problem/22945 22945번: 팀 빌딩 능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같 www.acmicpc.net 📍알고리즘 분류 - 정렬 - 투 포인터 📍문제 풀이 - 시간 초과를 해결하기 위한 노력1 left와 right 중에서 더 작은 값(min)을 끊임없이 갱신(centering)해가면 된다 만약 큰값을 centering하면, 간격도 좁아지고, 기존 값보다 작아질 수 있기 때문에, 출력할 최댓값을 보존할 수 없기 때문이다 - 시간 초과를 해결하기 위한 노력2 Python에서 변수명을 ..

📍문제 링크 https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N

📍문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 그래프 이론 - 그래프 탐색 - 트리 - 깊이 우선 탐색 - 트리에서의 다이나믹 프로그래밍 📍문제 풀이 트리와 이차원 배열이 주어진다. 이차원 배열은 [정점 번호, 숫자] 형태의 원소를 갖고 있다. 이차원 배열을 순회하며, 정점 번호에 해당하는 정점의 모든 자식 노드에 숫자를 더해주면 된다. - DFS를 사용하는 이유 사실 어차피 모든 그래..