📍문제 링크https://www.acmicpc.net/problem/1057 1057번: 토너먼트김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를www.acmicpc.net 📍알고리즘 분류- 수학- 브루트포스 📍문제 풀이- 총 팀 수 N과 팀번호 A, B가 주어질 때, A, B 팀이 몇 라운드에서 만나는지 구하라 (A, B 팀은 무조건 이긴다고 가정) - 토너먼트의 규칙은 반드시 2팀씩 묶어 1팀만 올라간다는 것이다따라서 팀 1 2 3 4 가 있다면1라운드에서 묶음 1 1 2 2 로 나타낼 수 있다2라운드에서 묶음 1 1 1 1 로 나타낼 수 있고 토너먼트가 종..

📍문제 링크 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 트리 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 - 간선에 가중치를 갖는 트리가 주어질 때, 테스트 케이스에서 주어지는 시작점부터 끝점까지의 거리를 구하라 - DFS를 활용한다- 거리를 계산하는 로직은 아래와 같다1️⃣정점의 갯수 + 1 만큼의 길이를 갖는 빈 배열 distance를 만든다 (계산의 편의상)2️⃣현재 정점의 이웃 정점들을 순회하며 distance[이웃 정..

📍문제 링크 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 높이 m, 너비 n 의 사각형이 주어질 때, 1번째 row의 0이 마지막 row의 0까지 연결되어 있는지를 확인 DFS를 통해 연결된 경로가 있으면 바로 YES를 출력하면 된다 📍코드 (JavaScript) const [in1, ...map] = re..

📍문제 링크 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 브루트포스 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 구현으로도 해결할 수 있는 문제이지만 DFS를 사용해서 풀자 - 크기가 작아서 구현으로 해결 가능 DFS를 사용하는 이유 - 빠르게 목표 지점에 도달하는 경로 하나만 찾으면 프로그램을 종료할 수 있어서 📍의사 코드 /* 1. 행렬 형태로 주어진 데이터를 2차원 배열로..

📍문제 링크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에서 변수명을 ..