전체 글
-
[Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02
문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..
-
[Algo Rhythm🕺💃]BOJ 14888 - 연산자 끼워넣기Algo Rhythm🕺💃/BOJ 2021. 6. 22. 16:24
문제 분석 $N (2 \le N \le 11)$개의 수로 이루어진 수열 $A_1, A_2, A_3, ..., A_n$의 순서는 바꿀 수 없지만 숫자 사이 들어가는 연산자들의 순서는 바꿀 수 있다. 따라서 이 문제는 연산자들의 순서에 대한 '모든 조합을 구한 뒤' 계산한 결과들 중 최대값과 최소값을 구하는 문제로 이해할 수 있다. 문제 풀이 1. 최적화 🙅♂️ 연산자들의 순서에 대한 모든 조합을 구하기 위해 backtracking을 사용했다. 이때 방문해야 하는 vertex들은 연산자들인데 연산자들의 종류를 구분하기 위해 enum을 정의했다. 또한 연산자들의 개수는 입력에 따라 가변적이기 때문에 정의한 enum을 저장하는 vector를 정의했다. backtracking에 사용한 점화식은 아래와 같다. 이..
-
🏠Bethel324-control-system을 구현하면서 배우고 성장한 점들Projects/🏠Bethel324-control-system 2021. 6. 21. 22:43
🏠Bethel324-control-system에 대한 설명은 이전 글을 참고하시길 바랍니다. 2021.06.21 - [Projects/🏠Bethel324-control-system] - 🏠Bethel324-control-system에 대하여 🏠Bethel324-control-system에 대하여 💻 개발 배경 이번 학기는 방돌이 영민이형과 함께 벧엘관 324호에 살았다. 기숙사에 살면 아래와 같이 고정적으로 반복해야 하는 몇 가지 일들이 있다. 먼저 밤 11시에 점호를 하면 소등해야 하 alinew.tistory.com 🏠Bethel324-control-system을 구현하면서 배우고 성장한 점들은 아래와 같습니다. 1. Notion을 이용한 체계적인 프로젝트 관리 ⏰ 이번 프로젝트는 팀 프로젝트였기 때..
-
🏠Bethel324-control-system에 대하여Projects/🏠Bethel324-control-system 2021. 6. 21. 20:23
💻 개발 배경 이번 학기는 방돌이 영민이형과 함께 벧엘관 324호에 살았다. 기숙사에 살면 아래와 같이 고정적으로 반복해야 하는 몇 가지 일들이 있다. 먼저 밤 11시에 점호를 하면 소등해야 하고, 방을 나갈 때는 방문을 잠궈야 한다. 그리고 봄철에는 건조하기 때문에 자기 전에 가습기를 틀어야 한다. 이런 일들은 은근히 사람을 피곤하게 만든다. 그래서 이것들을 자동으로 혹은 스마트폰 터치 하나로 할 수 있으면 편하겠다는 생각에 영민이형과 함께 🏠 Bethel324-control-system을 구현하기로 했다. 🏠 Bethel324-control-system은 LAN 상에서 웹 브라우저를 통해 아래와 같은 기능들을 수행할 수 있는 시스템이다. 💡 LED 상태 (on/off) 확인 및 제어 🐳 가습기 상태 ..
-
[Algo Rhythm🕺💃]BOJ 20170 - Commemorative DiceAlgo Rhythm🕺💃/BOJ 2021. 6. 21. 03:26
문제 분석 주사위 게임을 하는 첫번째, 두번째 플레이어를 각각 A, B라고 하고 A와 B의 주사위 중 임의의 한 면에 적힌 숫자를 각각 $\alpha, \beta$라고 하자. 이때 주사위는 6면이기 때문에 A와 B가 주사위를 던져서 나올 수 있는 경우의 수는 $6 \times 6 = 36$이다. 그리고 A가 B를 이기는 경우의 수인 $N_{win}$은 $\alpha \gt \beta$를 만족하는 모든 $\alpha$의 수와 같다. 따라서, A가 B를 이길 확률은 $N_{win} \over 36$이다. 이때, 문제에서 요구하는 것은 '더이상 나눌 수 없는' 분수 형태로 출력하는 것이기 때문에 분자와 분모를 최대 공약수로 나눠서 출력해야 한다. 문제 풀이 A와 B의 주사위 정보를 각각 배열에 저장한 뒤, $..
-
[Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크Algo Rhythm🕺💃/BOJ 2021. 6. 18. 23:44
문제 분석 스타트팀을 $T_{start}$, 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$명의 절반인 $N / 2$ 명이다. 문제에서 요구하는 $min(|S_{start} - S_{link}|)$를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$을 구하고 그 중 최소값을 찾는 것이다. 모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다. 문제 풀이 ..
-
[Algo Rhythm🕺💃]BOJ 1620 - 정상 회담2Algo Rhythm🕺💃/BOJ 2021. 3. 12. 15:05
문제 분석 문제를 분석하는 효과적인 방법들 중 하나는 그림으로 표현해보는 것이다. 이 문제에서 N = 0, 2, 4, 6 일때 완벽하게 악수하는 경우들과 그 수를 그림으로 표현하면 아래와 같다. (이때 각 국가의 대표는 노드로 표현했다.) 그림에서 검은색 노드와 흰색 노드가 연결된 선분을 기준으로 왼쪽 영역을 $l$, 오른쪽 영역을 $r$라고 하자. 그리고 $a$개의 노드들이 완벽하게 악수할 수 있는 경우의 수를 $f(a)$라고 하자. 그렇다면 N =0, 2, 4, 6일때 완벽하게 악수할 수 있는 경우의 수는 아래와 같은 규칙이 있음을 알 수 있다. 이 규칙을 점화식으로 표현하면 다음과 같다. $f(N)= \begin{cases} 1, & if\ n = 0\\ \sum_{i=0}^{N-2} f(i) \t..
-
[Algo Rhythm🕺💃]BOJ 14501 - 퇴사Algo Rhythm🕺💃/BOJ 2021. 3. 11. 00:41
문제분석 백준이는 $i (1 \le i \le N)$번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 단순히 생각하면 i번째 날의 일을 하는 경우와 안 하는 경우로 나눠서 모든 경우를 살핀 뒤 그 중 최대의 이익을 구하면 될 것 같다. 사실 그래도 된다. 하지만 조금 더 생각해보면 보다 더 효율적인 방법이 있다는 것을 알 수 있다. 앞서 말했듯이 백준이는 i번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 자세히 말하면 만약 i번째 날의 일을 한다면 $i + T[i]$번째 날의 일부터 하느냐 마느냐를 선택할 수 있고 만약 i번째 날의 일을 하지 않는다면 $i + 1$번째 날의 일부터 하느냐 마느냐를 선택할 수 있다. 즉, 백준이가 i번째 날의 일을 하느냐 마느냐를 결정..