나그네

15925번: 욱제는 정치쟁이야!! 문제 https://www.acmicpc.net/problem/15925 15925번: 욱제는 정치쟁이야!! 첫째 줄에 각 줄의 컴퓨터 개수 N과 이후의 컴퓨터실 사용 여부가 하나의 공백을 사이에 두고 주어진다. 사용 여부는 사용시 1, 미사용시 0으로 주어진다. (1 ≤ N ≤ 31, N % 2 == 1) 이후 둘째 줄부터 www.acmicpc.net 풀이 브루트포스 문제로 O(N^2)으로 해결가능합니다. 사용 여부를 x라고 할 때, 한 행 또는 열에서 x가 N/2개 이상이면 모두 x로 바꿉니다. 문제의 예제 입력 1을 예로 들어 설명해보겠습니다. 5 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 일 때, 행부터 먼저 모..

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 문제 https://www.acmicpc.net/problem/24265 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 i=1~n-1까지 총 n-1번 반복되는 for문을 수행합니다. 이 for문 내부에선 j=i+1~n까지 총 n-i번 반복되는 for문을 수행합니다. 이중 for문 내부의 코드는 i=1일 때 j=2~n, i=2일 때 j=3~n, ... , i=n..

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 문제 https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. 이 for문 안에서 다시 n회 반복되는 for문을 수행합니다. 따라서 이중 for문 안의 코드1은 n^2번 수행됩니다. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 2입니다. 코드 #inclu..

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 문제 https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. for문 안의 코드1은 n번 수행됩니다. 따라서 코드1의 수행 횟수는 입력받은 n과 같은 값을, 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 1입니다. 코드 #include using name..

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 문제 https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 항상 1번만 return 합니다. 따라서 수행 횟수는 1, 최고차항의 차수는 0입니다. 코드 #include using namespace std; int main() { int a; cin >> a; cout

29766번: DKSH 찾기 문제 https://www.acmicpc.net/problem/29766 29766번: DKSH 찾기 첫째 줄에 문자열이 입력된다. 문자열의 길이는 $1\,000$을 넘지 않는다. www.acmicpc.net 풀이 입력받은 문자열의 i(0 ~ N-1)인덱스 부터 4글자씩 비교하며 DKSH가 나올 때마다 개수를 세면 됩니다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s, a = "DKSH"; int cnt = 0; cin >> s; for (int i = 0; i < s.size(); i++) { int flag = 0; for (int j = 0; j < 4..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29160번: 나의 FIFA 팀 가치는? 문제 https://www.acmicpc.net/problem/29160 29160번: 나의 FIFA 팀 가치는? 첫 번째 줄에 선수의 수 $N$과 $K$가 공백으로 구분되어 주어진다. $(0\leq N\leq 1\,000\,000;$ $1\leq K\leq 50\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $i$번째 선수의 포지션 $P_{i}$, 선수 가치 $W_{i}$가 www.acmicpc.net 풀이 항상 가치가 가장 높은 선수를 선발하는 과정을 반복하기 때문에 우선순위 큐(최대 힙)를 사용한다. 11개의 포지션 번호별로 선수를 저장할 수 있는 우선순위 큐 배열을 만든다. 각각의 포지션 번호별로 비어있는 우선순위 큐를 제외하고 한 명씩 선수를..

29156번: 탭 UI 문제 https://www.acmicpc.net/problem/29156 29156번: 탭 UI 탭 UI는 여러 탭이 일렬로 나열되어 특정 탭을 클릭하면 해당 탭에 대한 내용을 확인할 수 있는 UI(User Interface)이다. 화면 내에 있는 탭은 노출되고 좌우로 화면을 벗어난 탭은 노출되지 않으며 사 www.acmicpc.net 풀이 각 탭의 길이를 입력받을 때 누적합(prefix_sum) 배열을 만들어 전체 길이를 기록한다. 그리고 각각의 탭의 중앙의 좌표를 저장한 coordinate 배열을 만든다. 화면의 길이의 절반(화면의 중앙)을 mid라고 한다. 그리고 클릭한 탭 x가 주어졌을 때, mid에 위치하기 위해 coordinate[x]가 얼마나 이동해야 하는지를 gap이..

28682번: 재우야 임관하자 문제 https://www.acmicpc.net/problem/28682 28682번: 재우야 임관하자 인터랙티브 문제의 경우 출력을 하고, 언어에 따라 아래와 같은 명령어를 바로 다음에 적어 출력 버퍼를 flush해 줘야 한다. C: fflush(stdout); C++: fflush(stdout); 혹은 std::cout > n; string a[] = {"swimming", "bowling", "soccer"}; for (int i = 0; i < n; i++) // 그냥 swimming만 n번 출력해도 된다. cout