Min IT's Devlog

풀이 일자: 23.02.15 난이도: [Easy] 분류: [Array, Math] 문제 내용 int형 배열 num과 int형 변수 k가 주어졌을 때 num+k의 결과를 array형태로 리턴시키는 문제 문제 해결 흐름 저번에 풀었던 2023.02.14 - [코테/LeetCode] - [python3] 67. Add Binary문제와 사실상 비슷한 문제이다. 다만 num내부의 자료형이 int이고 결과도 int로 해야하기 때문에 저번처럼 여러번 자료형 변환을 거쳐 푸는 것은 비효율적으로 보인다. 1. k의 각 자리를 분리하기 위한 방법을 생각해보자. → 일반적인 십진수의 경우 각 자리를 구하는 방법은 반복문을 돌려가며 일의 자리를 하나씩 확인하는 방법이 존재한다. k = 112; ans = [] while (..

풀이 일자: 23.02.11 ~ 14 난이도: [Medium] 분류: [BFS, Graph] 문제 내용 n이 주어지고 이를 통해 0 ~ n-1로 각각 라벨링되어있는 노드가 있다고 생각하면 edge가 red인 것과 blue인 것이 존재하며 현재 이루고 있는 graph가 directed graph라고 했을 때 answer[i]이라는 곳에는 0에서 i번째 노드로 갈 때 제일 최단의 길이를 넣어서 리턴하는 문제. ( 단 빨간색과 파란색 edge를 번갈아가며 이동하도록 해야함) 문제 해결 흐름 1. 전체적으로는 shortest path 알고리즘을 사용하면 되는 것으로 보이나 우선 directed graph이므로 일단 다익스트라 알고리즘은 사용할 수 없다. → 그럼 이를 대체할 알고리즘은 현재 0에서 각 노드로의 ..

풀이 일자: 23.02.14 난이도: [Easy] 분류: [Math, Bit Manipulation] 문제 내용 str형태로 주어지는 이진수 a, b를 합한 결과를 이진수 문자열형태로 리턴하는 문제이다. 문제 해결 흐름 1. 2진수를 10진수로 바꿔서 더한다음 다시 2진수로 변환하는 방법이 있겠다. → int(num, 2)를 사용하면 2진수 형태의 문자열을 10진수로 변환이 가능하며 bin(num)을 사용하면 '0b1111'의 형태의 이진수 문자열을 얻을 수 있다. 0b는 필요없으니까 [2:]를 이용한 slicing을 하면 끝! class Solution: def addBinary(self, a: str, b: str) -> str: a = int(a, 2); b = int(b, 2); ans = bin..

풀이 일자: 23.02.13 난이도: [Easy] 분류: [Math] 문제 내용 2개의 양수가 주어졌을 때 그 수들을 포함한 그 사이의 수들 중 홀수의 개수를 구하는 문제이다. 문제 해결 흐름 1. 별다른 알고리즘 보다는 어떤 수학적인 패턴을 찾아서 구해내는 것이 맞겠다. → 짝수부터 세는 경우 ( high - low )//2 + 1개의 홀수가 나온다. class Solution: def countOdds(self, low: int, high: int) -> int: if (low & 1) == 0: low += 1; return 0 if low > high else (high - low)// 2 + 1; Time Complexity: O(1) 반복문 돌아가는 것 없이 계산만 진행하기에 O(1)이다. S..

풀이 일자: 23.02.10 난이도: [Medium] 분류: [DP, BFS] 문제 내용 0(물)과 1(땅)로 구성된 n*n 크기의 grid라는 배열을 줬을 때 땅과 가장 가까운 물타일들 중 땅과의 manhattan거리가 최대일때의 거리를 구하는 문제이다. 주의) 문제에 나와있긴 하지만 거리를 구할 때 manhattan거리를 사용하라고 했다. Manhatten 거리 = |x0 - x1| + |y0 - y1| Euclidian 거리 = ( (x0 - x1)2+(y0 - y1)2)½ 예를 들면 아래의 배열처럼 주어졌다고 가정해보자. 1 0 1 0 0 0 1 0 1 각 물타일과 해당 물타일과 가장 가까운 땅과의 거리를 적어보면 아래와 같이 될 것으로 최대일 때의 거리는 2이다. 1 0(1) 1 0(1) 0(2..

풀이 일자: 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. 이 문제에 적합한 알고리즘이 어떤 게 있을까? → 고려해야 하는 요인이..