Min IT's Devlog

풀이 일자: 23.02.09 난이도: [Hard] 분류: [Array, Hash Table, Bit Manipulation] 문제 내용 사명의 후보가 될 단어들을 ideas라는 배열안에 주어지고 이 중 2개를 선택하여 사명을 지으려고 하며 이때 사명의 조건은 2개의 다른 단어들을 배열에서 뽑아서 서로 앞의 알파벳을 바꿨을 때 바꾼 단어가 ideas라는 배열 안에 없어야한다. 물론 단어의 순서에 따라 이름이 달라지니까 그러한 것도 고려해야하며 가능한 서로 다른 이름의 개수를 구하는 문제였다. ex) ideas = ["coffee", "donuts", "toffee"]가 있다고 가정하자 이를 통해 가능한 경우와 불가능한 경우를 생각해보면 - ("coffee", "donuts") = "doffee conuts..

풀이 일자: 23.02.08 난이도: [Medium] 분류: [Array, DP, Greedy] 문제 내용 인덱스 0부터 시작하는 arr가 주어졌을 때 arr[i]의 의미는 i번째 칸에서 오른쪽으로 움직일 수 있는 최대 길이를 의미한다. 이 경우 인덱스 n-1에 도달하기 위해 움직여야할 최소 횟수를 구하는 문제이다. 아래의 그림을 보면 알 수 있다. 아래의 배열이 주어졌을 때 2번의 이동으로 배열의 맨 끝까지 이동이 가능하다. 문제 해결 흐름 1. 어떤 알고리즘으로 해당 문제를 해결하면 좋을까? → 0번째에서 n-1까지 이동해야하므로 최대한 멀리 갈 수 있는 node를 찾아서 그런 node를 타고 다니면 되겠다. → 즉 멀리 갈 수 있는 것만 택하면 되니까 Greedy하게 처리하면 되겠네.. 2. 그렇다..

풀이 일자: 23.02.07 난이도: [Medium] 분류: [Array, Hash Table, Sliding Window] 문제 내용 농장에서 일렬로 세워진 나무에서 과일을 따는 문제이다. 주어진 조건으로는 1) 2개의 바구니를 가지고 있고 바구니에는 각각 한 종류의 과일만 넣을 수 있고 한 바구니에 넣을 수 있는 과일 양은 무한 2) 하나의 나무에서 한 개의 과일만 딸 수 있다 3) 시작점을 자신이 정할 수 있고 시작점부터 과일을 따다가 3번째 종류의 과일이 나오는 경우 그 즉시 stop. 문제 해결 흐름 1. 간단하게 생각한다면 2중 for문을 이용해서 해결한다면 쉽겠다. → 바깥 for문은 시작점 내부 for문은 현재 따고 있는 위치라고 생각한다면 딴 과일의 종류를 array나 dictionary..

풀이 일자: 23.02.06 난이도: [Easy] 분류: [Array] 문제 내용 [x1,x2,...,xn,y1,y2,...,yn]이 주어지면 [x1,y1,x2,y2,...,xn,yn]으로 변환하는 문제 문제 해결 흐름 1. 단순하게 생각 → ans용 array를 하나 만들어서 0부터 n-1을 순회해 가면서 i번째와 i+n번째 수를 배열에 넣어가면 완성. 다른 해결 방식 1. 단순하게 생각하면 매우 쉽지만 만약 in-place로 풀어야 한다면?(만약 새로 배열을 만들 수 없는 메모리만 제공한다면?) → bit를 이용하자.. 현재 숫자의 크기 조건이 (1 > 10; 1,6 2,7 3,8 4,9 5,10 5 10 ↓ 1 6 2 7 3 8 4 9 5 10 => 매우 쉬운 문제로 코딩테스트에서 나올 일이 없을 ..

풀이 일자: 23.02.02 ~ 02.06 (해설찬스) 난이도: [Medium] 분류: [DP, Sorting] 문제 내용 팀에 있는 모든 플레이어의 점수의 합을 구하는데 1가지 조건이 존재한다. Conflict가 없도록 해야 하는데 Conflict란 어린 선수가 더 나이가 많은 선수보다 더 높은 점수를 가지고 있는 것을 의미하며 같은 나이에서는 점수와 상관없이 Conflict가 일어나지 않는다. 이를 고려해서 팀의 점수를 계산했을 때 가장 높은 점수의 합을 구하는 문제이다. LIS 관련 개념 포스팅 2023.02.03 - [CS/알고리즘] - [DP] 최장 증가 부분 수열(LIS) 알고리즘 with python 문제 해결 흐름 1. 이 문제에 적합한 알고리즘이 어떤 게 있을까? → 고려해야 하는 요인이..

풀이 일자: 22.10.10 난이도: [Medium] 분류: [String, Greedy] 문제 내용 palindromic한 문자열이 주어지면 이를 1개의 문자를 바꿔서 깨트리면 되는데 모든 경우의 수 중 사전적으로 가장 앞에 나오는 문자열을 반환하는 문제이다. 문제 해결 흐름 1. 특수 케이스를 생각해보자. → 문제에서 제시한 특수케이스는 한 글자를 바꾸더라도 palindromic함을 유지하는 경우인데 그 경우는 오직 문자열의 길이가 1일때만 가능하겠다. 2. 사전적으로 가장 작은 것을 내놓으면 된다면 Greedy하게 처리할 수 있지 않을까? → 앞에서부터 check를 해가면서 'a'가 아닌 문자를 'a'로 바꾸기만 하면 되는게 아닐까? 3. 예외 케이스가 있나? → 예를 들어 'aba'인 경우 'a'..

풀이 일자: 22.09.09 난이도: [Medium] 분류: [Greedy, Sorting] 문제 내용 주어진 character 집합에서 상대적으로 ATK, DEF가 다른 character보다 낮은 경우 Weak라고 하며 Weak character의 수를 찾는 문제. 문제 해결 흐름 1. 다른 ATK, DEF보다 낮은 player의 수를 찾아야 하니까 뭔가 극단적인 값을 이용하면 되지 않을까? → Greedy하게 현재 주어진 배열에서 ATK와 DEF가 상대적으로 가장 높은 값을 가지고 시작하자. 2. 가장 높은 값을 가지고 시작하되 좀 더 쉽게 만드는 방법이 있을까? → 배열이 ATK 내림차순, DEF 오름차순으로 정렬하면 비교하는데 크게 문제가 없겠다. class Solution: def numberO..

풀이 일자: 22.09.05 난이도: [Medium] 분류: [BFS/ Tree] 문제 내용 주어진 n-ary tree를 가지고 각 level의 노드값들의 리스트들을 하나로 묶어서 리턴하는 문제이다. 문제 해결 흐름 1. 문제에서 level별 순회값을 리턴하라고 어떻게 풀어야 하는지 제시해주었다. → 대놓고 BFS쓰라는 거구나. 그래도 일단 익숙한 DFS로 풀어보았다. """ # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution: def levelOrder(self, root: 'Node') -> List[L..

풀이 일자: 22.09.04 난이도: [Hard] 분류: [Hash Table/ DFS/ BFS/Binary Tree] 문제 내용 root(0,0)부터 아래로 내려가면서 왼쪽 노드는 +1 -1 오른쪽 노드는 +1 +1을 좌표에 더하여 y좌표가 같은 것끼리 묶어서 값을 리턴하는 문제였다. 문제 해결 흐름 1. 일단 이것도 트리 순회를 하면서 값을 정리하는 것이므로 트리 순회 알고리즘이 필요하겠다. → 간편한 DFS 방식을 사용해볼까? 2. 트리의 크기를 최대 최소로 알아볼까? → 현재 가질 수 있는 맨 아래 최대 최소 좌표는 (9,-9) ~ (9,9)이다. 그 이유는 최대 1000개의 노드가 있으므로 2^n으로 등비수열의 합을 게산해보면 0 ~ 9 level까지 가능하다는 것을 확인할 수 있기 때문이다. ..

풀이 일자: 22.09.03 난이도: [Medium] 분류: [Backtracking/BFS] 문제 내용 자릿수에 관한 정보 n과 인접한 수와의 차이를 나타내는 k를 받아서 해당 조건에 맞는 수의 List를 반환하는 문제였다. 즉 n = 3, k = 7이라 했을 때, 세자리수이고 인접한 각 자리수의 차이가 7인 수의 List를 반환해야 하므로 [181, 292, 707, 818, 929]가 이에 해당한다. 문제 해결 흐름 1. 받는 k에 따라 0~9까지의 수의 다음에 나올 수 있는 수를 미리 저장해두어야겠다. → k=0일때를 제외하고 0~9까지의 수 n 다음에 나올 수 있는 수가 (n+k, n-k)이므로 해당 정보를 딕셔너리(해쉬)로 저장하자. k가 0일때는 n 다음에 n이 나와야 한다. 2. 이제 나올..