알루 코딩

주어진 문자열 s를 이용해서 만들 수 있는 가장 긴 팰린드롬을 구하는 문제입니다. 문자열 s는 대문자와 소문자가 구분해서 주어지고 만들어 질 수 있는 가장 긴 팰린드롬의 길이를 답으로 출력하면 됩니다. 처음에 접근했던 방법은 Discussion에서 해당 코멘트를 봤습니다. 한 유저가 남긴 코멘트였는데, 해시맵을 사용하면 된다고 해서 바로 딕셔너리를 생각해봤습니다. 주어진 문자열에서 문자가 나온 횟수를 value로 저장하고, 해당 문자를 key값으로 저장하는 딕셔너리를 생각해본다면, 가장 긴 팰린드롬의 길이는 짝수의 횟수를 가진 key값과 홀수값 중에서 최댓값을 가진 key값의 구성으로 만들어지겠다라는 것이 추론됩니다. 예를 들어서 설명해볼까요? "aabbsserrr" 이라는 문자열이 있다고 하면, 이 문..

위 문제는 그리디 문제입니다. 리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠. 맨 처음에 저는 O(n^2))의 복잡도로 문제를 풀었습니다. 그래서, 시간초과의 문제에 걸렸습니다. 제약조건을 보면 prices의 길이가 최대 100000이기 때문에, O(n^2)의 복잡도로 풀어버리면 10의 8승을 넘기 때문에 시간초과에 걸리는 것은 당연한 소리겠죠! 처음, 시간초과에 걸렸던 코드는 아래와 같습니다. class Solution: def maxProfit(self, prices: List[int]) -> int: is_reversed_sorted = all(prices[i] >= prices[i+1] for i in range(len(prices)-1)) if is_reversed_sorted: retur..

위 문제는 정렬된 두 리스트를 병합하는 문제입니다. 단순 알고리즘 문제를 푸는 것이 아니라 자료구조를 고려해서 풀어야 하는 문제였는데요, 자료구조의 필요성이 느껴진 문제이기도 했습니다. 문제를 접근하는 방식에는 2가지 방법이 있는데요, 하나는 재귀적 알고리즘을 사용하는 방법과 두번째로는 더미노드를 만들어 그 뒤에 이어 붙이는 방법이었습니다. 시간 복잡도는 둘다 O(n+m)이 나오는데요, 두 번째 방법으로 푼 코드를 살펴봅시다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeT..

이 문제는 주어진 문자열 t 안에 s문자열이 있는지 아닌지를 판단하는 문제입니다. 예를 들어서, t가 ahbgdc 이고, s가 abc 라면, ahbgdc에서 h,g,d,를 제거하면 abc가 되므로 true를 반환합니다. 반면, 만약 t가 abcde이고, s가 aec 라면, abcde 문자열에서 어떤 수를 써서라도 aec를 만들 수 없기에 false를 반환합니다. 즉, t의 원래의 문자열에서 순서는 유지한 채 수열을 이루는 항 중에 일부만 모아 s가 만들어진다면, true를 반환하고, 그렇지 않다면 false를 반환하면 됩니다. 코드를 통해 살펴보죠. class Solution: def isSubsequence(self, s: str, t: str) -> bool: idx = 0 cnt = 0 if len..

주어진 문자열 s와 t가 동형사상이라면, true를 반환하고, 그렇지 않으면, false를 반환하는 문제인데요! 다양한 문제풀이가 있을거에요. 딕셔너리를 이용해서 풀어도 되고, 자바를 활용한다면 해시맵으로도 풀 수 있을 것 같습니다! 저도 처음에는 딕셔너리로 접근을 했다가, index의 위치만 저장하는 리스트로 풀어도 되겠다 싶어서 리스트만을 이용했습니다. 코드를 보면서 살펴보겠습니다. class Solution: def isIsomorphic(self, s: str, t: str) -> bool: answer = False if len(s) != len(t): return answer else: s_check = [] t_check = [] for i in s: s_check.append(s.index..

◆ 먼저, 글을 보기 전에 이 문제를 풀어볼까요? 더보기 문제 base 진법으로 표기된 숫자를 10진법 숫자 출력해보세요. 입력 입력으로는 공백으로 구분된 숫자가 두 개 주어집니다. 첫 번째 숫자는 num을 나타내며, 두 번째 숫자는 base를 나타냅니다. 출력 base 진법으로 표기된 num을 10진법 숫자로 출력해보세요. 제한 조건 base는 10 이하인 자연수입니다. num은 3000 이하인 자연수입니다. 입출력 예시 input output 12 3 5 444 5 124 입출력 예 설명 입출력 예 1 3진법으로 표기된 12는 10진법으로 표현하면 5입니다. ( 1*3 + 2 ) 입출력 예 2 5진법으로 표기된 444는 10진법으로 표현하면 124입니다. ( 4*5*5 + 4*5 + 4 ) 저는 처음..

알고리즘 문제를 풀 때, 정수를 나눈 몫과 나머지를 구해야 할 때면, 보통 아래와 같은 방법으로 구합니다. ex) 29을 3으로 나눈 몫과 나머지를 구해야 하는 경우 a = 29 b = 3 print(a//b, a%b) # 9, 2 하지만, 파이썬에서는 divmod와 unpacking 기능이 있는데 divmod를 사용하면 아래와 같이 간편하게 몫과 나머지를 구할 수 있습니다! divmod는 한번에 몫과 나머지를 반환해주는 파이썬 내부 함수에요! a = 29 b = 3 print(*divmod(a, b))# 9 2 ◆ divmod를 사용할 때 주의할 점◆ - 무조건 divmod를 사용하는 것이 좋은 것은 아닙니다! 가독성이나, 팀의 코드 스타일에 따라서, 근본적인 //, % 의 방법으로 쓰는게 더 좋을 수..

문제 설명 더보기 문제 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한 n은 50,000,000이하의 자연수 입니다. 입출력 예시 입출력 예 n result 1 1 2 2 3 4 4 11 https:/..

문제 설명 더보기 문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째..

이 문제는 삼성sw 역량 테스트 기출 문제에 속하는데요. 삼성 코테 유형은 대체로 구현이 많이 나옵니다. 차근차근 문제를 이해하고 종이에 써가면서 풀어본다면, 끈기와 빨리 풀 수 있는 실력만 있다면 충분히 푸실 수 있는 문제입니다. 겉으로 봤을 땐, DFS나 BFS로 푸는 문제인 것 같지만, 단순 구현으로도 풀리는 문제입니다. 먼저 문제를 이해해보록할게요. 보드가 있구요. 보드 위에 주사위가 있습니다. 주사위는 보드 위 숫자가 0인 부분에 있고 명령에 따라서 굴리는 문제라고 보시면 됩니다. 그럼, 아래 문제의 내용이 이해가시나요? 주사위가 보드 위에서 굴려질 때마다 주사위 면에 적혀지는 숫자와 보드위에 적혀지는 숫자가 달라진다는 것을 알 수 있습니다. 즉, 주사위가 굴려짐에 따라 보드와 주사위의 숫자가 ..