cpp
-
[Algo Rhythm🕺💃] BOJ 2225 - 합분해Algo Rhythm🕺💃/BOJ 2021. 7. 22. 22:15
💫문제 분석 입력으로 주어지는 두 정수를 각각 $N,K\ (1\le N,K \le 200)$라고 하자. 그리고 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 $f(N,K)$라고 하자. 마지막으로 N을 만들기 위해 더해지는 K개의 정수들을 순서대로 $I_1, I_2, ..., I_K$라고 하자. $f(N,K)$의 규칙을 파악하기 위해 $f(2, 3)$를 구하는 과정을 분석해보자. $f(2, 3)$은 아래와 같이 6이다. 이때 $I_1$과 나머지 $I_2, I_3$의 관계를 파악해보자. $I_1 = 0$ 일때 $I_2, I_3$를 구하는 것은 $f(2, 2)$을 구하는 것과 같다. (1이 적힌 파란 원으로 표시함) $I_1 = 1$ 일때 $I_2, I_3$를 구하는 것은 $f(1,2)$..
-
[Algo Rhythm🕺💃] BOJ 1463 - 1로 만들기Algo Rhythm🕺💃/BOJ 2021. 7. 22. 00:00
💫문제 분석 주어진 $n\ (1 \le n \le 10^6)$에 대하여 사용가능한 연산들은 다음과 같다. $op_1 : n \equiv 0 \pmod{3}이면,\ n = n \div 3$ $op_2 : n \equiv 0 \pmod{2}이면,\ n = n \div 2$ $op_3 : n = n - 1$ 그리고 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 $f(n)$이라고 하자. $n$에 대하여 $op_1,\ op_2,\ op_3$을 모두 사용할 수 있을 때 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 각각 $f_1,\ f_2,\ f_3$라고 하자. 그렇다면 $n \equiv 0 \pmod{3}$이면 $op_1$을 사용하여 $n$을 $n \div 3$으로 줄일 수 있기 때문에 $f_1..
-
[Algo Rhythm🕺💃] BOJ 1759 - 암호 만들기Algo Rhythm🕺💃/BOJ 2021. 6. 30. 19:52
💫문제 분석 암호가 구성되는 서로 다른 알파벳 소문자의 개수를 $l$, 암호로 사용했을 법한 문자의 개수를 $c\ (3 \le l \le c \le 15)$라고 하자. 암호를 이루기 위해서는 다음과 같은 두 조건을 만족해야 한다. 최소한 한 개 이상의 모음(a, e, i, o, u)로 이루어져 있다. 최소한 두 개 이상의 자음들로 이루어져 있다. 암호를 이루는 알파벳들은 증가하는 순서로 배열되어 있다. 암호로 사용했을 법한 문자들을 하나의 vertex로 보자. 그렇다면 이 문제는 $c$개의 vertex들 중 앞서 언급한 조건들을 만족하여 $l$개의 vertex들을 선택하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 먼저 암호로 사용했을 법한 문자들을 저장한 배열 $alphabets$을 ..
-
[Algo Rhythm🕺💃] LeetCode 720. Longest Word in DictionaryAlgo Rhythm🕺💃/LeetCode 2020. 9. 4. 01:05
📚 Problem description Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string. Example 1: Input: words = ["w","wo","wor","worl", "world..
-
[Algo Rhythm🕺💃] LeetCode 208. Implement Trie (Prefix Tree)Algo Rhythm🕺💃/LeetCode 2020. 9. 3. 16:04
📚 Problem description Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters a-z. All inputs ar..
-
[Algo Rhythm🕺💃] BOJ 16288. Passport ControlAlgo Rhythm🕺💃/BOJ 2020. 9. 3. 10:32
📚 문제 설명 $N$명의 입국 승객이 여권 심사를 위하여 그림 G.1 과 같이 입국 대기 줄에서 $[1, 2, … , N − 1, N]$ 순서로 기다리고 있다. 입국 승객은 준비된 $k$개의 여권 심사 창구 중 하나를 통과한 뒤 공항을 빠져나갈 수 있다. 입국할 때의 줄 선 승객의 순서를 $[1, 2, … , N − 1, N]$이라고 할 때 $k$개의 여권 심사 창구를 통과하여 입국장을 빠져나가는 순서 $[π_{1}, π_{2}, … π_{N−1}, π_{N}]$는 처음과 달라질 수 있다. $k$개 여권 심사 창구가 준비되어 있을 때, 이 입국장을 빠져나가는 순서가 가능한 순서인가를 계산해야 한다. 예를 들어 설명해보자. 만일 $N = 3, k = 2$ 라고 할 때 입국장을 빠져나가는 순서 중 $[1, ..
-
Visual Studio Session배워서 남주자 2019. 7. 30. 17:02
우리 학교는 특이하게 입학생 전원이 무전공 입학을 한다. 그리고 2학년때 각자 전공을 선택한다. 그래서 대개 2학년때 전공기초 과목을 듣는 편이다. 여러 가지 컴퓨터공학 기초과목이 있지만 그 중 data structure가 포함된다는 데에 이견을 가진 사람은 아마 없을 것이다. 지난 학기 data structure TA(Teaching Assistant)를 맡았다. 처음 맡은 TA이고 수강생도 많아서 부담감이 컸다. 또한 코딩감각이 없는 친구부터 나보다 훨씬 잘 하는 친구들까지 실력의 범위가 굉장히 넓어서 어떻게 도움을 주어야 할지 많이 고민했다. 교수님께서 처음에는 Atom을 사용하시다가 tree부터는 슬슬 복잡해지니까 debugging 기능을 제공하는 IDE에 대해서 수강생들이 배우고 이용했으면 좋겠..