주어진 정수 배열 nums안에서 더해서 0이되는 서로 다른 위치에 있는 세 수들을 반환하시오.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = [] Output: []

Example 3:

Input: nums = [0] Output: []

풀이

이번 문제는 Two-Pointer방식을 이용하면 생각보다 쉽게 풀 수 있다. 일단 Brute-Force방식을 생각해 볼 수 있지만, 역시나 시간 초과가 난다.

따라서, 먼저 배열을 정렬한 다음, for문을 통해 더해서 0이 될 첫번째 원소를 탐색하면서, 첫 번째 원소 이후의 원소들 중에서 두번째 원소와 세 번째 원소를 찾으면 된다.

여기서 한가지 생각해야 할 것은, 첫번째 보기에서도 나와있듯이, 중복되는 값들이 여러개 제시 될 수 있다. 따라서 첫 번째, 두 번째, 세 번째 원소를 정할 때, 모두 중복을 건너뛰는 코드를 넣어주어야 한다.

또한 놓칠수도 있는 것이, 첫번째 원소와 더해서 0이되는 두 번째, 세 번째 원소의 집합이 2개 이상일 수 도 있다는 것이다. 이러한 것을 생각한다면, 이 문제는 쉽게 해결할 수 있다.

이를 Python으로 구현하면 다음과 같다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []

        # nums배열 오름차순으로 정렬.
        nums.sort()

        for fst in range(len(nums) - 2):

            # nums에서 중복된 값을 제외하여 fst의 위치를 결정.
            if fst > 0 and nums[fst] == nums[fst - 1]:
                continue

            # sec, trd의 위치를 결정.
            sec, trd = fst + 1, len(nums) - 1

            # 더해서 0이 되는 세 수의 위치를 탐색.
            while sec < trd:
                tot = nums[fst] + nums[sec] + nums[trd]

                if tot < 0:
                    sec += 1

                elif tot > 0:
                    trd -= 1

                else:
                    answer.append([nums[fst], nums[sec], nums[trd]])

                    # fst위치에 있는 수와 더해서 0이되는 중복되지 않는 또 다른 sec, trd의 위치 결정.
                    while sec < trd and nums[sec] == nums[sec + 1]:
                        sec += 1

                    while sec < trd and nums[trd] == nums[trd - 1]:
                        trd -= 1

                    # 이전과 중복된 값에서 벗어나기 위해 sec, trd값을 한번 더 조졍.
                    sec += 1
                    trd -= 1

        return answer

for문 안에 while문이 있고 while문이 하나 더 중첩되어 복잡해 보일 수 있으나, fst와 더해서 0이되는 (sec, trd)가 여러 개일 수 있다는 것만 생각하면 그렇게 어렵지 않을 것이다.

너비가 1인 기둥들의 양의 정수인 높이들이 주어질 때, 비가 온 후 기둥들 사이에 담길 물의 양을 계산하시오.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

풀이

많이 어려웠고, 도저히 생각이 안나서 책을 참고했다. 두 가지 풀이에 대해 이해한 것을 바탕으로 설명해 보도록 하겠다

1. Two-Pointer를 이용한 풀이.

이 문제를 풀기 위해서는 아래와 같은 변수들이 필요하다.

• left: 왼쪽에서부터 움직이고 있는 변수.

• right: 오른쪽에서부터 움직이고 있는 변수.
• max_height.left: left가 지나오면서 가장 높인 기둥의 높이.
• max_height.right: right가 지나가면서 가장 높은 기둥의 높이.

이 문제는 코드를 보면서 설명하는 것이 이해가 더 잘 갈 것이다.

from collections import namedtuple

class Solution:
    def trap(self, height: List[int]) -> int:

        #예외 처리
        if not height:
            return 0

        #변수 초기화
        volume = 0
        left, right = 0, len(height) - 1
        max_height = namedtuple('max_height', 'left right')
        max_height.left, max_height.right = height[left], height[right]

        #가장 높은 기둥에 도달할 때까지 while문을 반복.
        while left < right:

            #왼쪽과 오른쪽의 최고 높이 갱신
            max_height.left = max(max_height.left, height[left])
            max_height.right = max(max_height.right, height[right])

            #한 번에 한 쪽씩만 움직이면서 물 더하기.
            if max_height.left <= max_height.right:
                volume += max_height.left - height[left]
                left += 1
            else:
                volume += max_height.right - height[right]
                right -= 1

        return volume

일단, 핵심은 while문 안이다. while문의 종료 조건은 left == right이다. 즉, 반복문의 매 회마다 max_height.left와 max_height.right의 값을 갱신한 후, 두 값을 비교하여 한쪽만 volume을 계산해 나간다.

이렇게 하면, max_height.left와 max_height.right중 어느 한 쪽이라도 낮은 쪽의 빗물은 volume에 더해지면서 이동할 것이므로, 결국 두 포인터 모두 기둥 중 가장 높은 기둥에서 만나게 된다.

2. Stack을 이용한 풀이.

이번엔 Stack을 이용한 풀이이다. 이번 풀이는 하나의 포인터만 사용한다.

class Solution:
    def trap(self, height: List[int]) -> int:
        idx_stack = []
        volume = 0

        # 한 방향으로 진행한다.
        for cur_idx in range(len(height)):

            # stack이 비어있지 않고, 현재의 기둥 높이가 이전 기둥의 높이보다 높은 경우.
            while idx_stack and height[cur_idx] > height[idx_stack[-1]]:
                hole_idx = idx_stack.pop()

                if not idx_stack:
                    break

                dist = cur_idx - idx_stack[-1] - 1
                waters = min(height[cur_idx], height[idx_stack[-1]]) - height[hole_idx]

                volume += dist * waters

            idx_stack.append(cur_idx)

        return volume

주어진 정수 배열 nums와 정수 target에 대해, 덧셈하여 target을 만들 수 있는 배열 안의 두 수의 인덱스를 반환하여라.

정확히 하나의 답이 존재하며, 같은 원소를 두 번 사용하지 않을 수 있다.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

풀이

당연히 생각해 볼 수 있는 풀이 방법은 brute-force이다. 하지만 이 방식으로는 시간 초과가 발생한다.

문제에서 분명히 하나의 답이 존재한다고 했으므로, 우리는 현재 숫자에 대한 나머지 후보가 될 수 있는 dictionary를 이용하여, 값을 찾아낼 수 있다.

이를 Python으로 구현하면 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}

        for idx, num in enumerate(nums):

            #현재 숫자 num에 대한 나머지 계산
            complement = target - num

            # 나머지가 dictionary안에 있을 경우.
            if complement in nums_dict:
                return [idx, nums_dict[complement]]

            #현재의 숫자를 key로 index를 value로 설정(현재의 값은 미래의 나머지가 될 것이므로).
            nums_dict[num] = idx

문자열 s가 주어질 때, s안에서 가장 긴 팰린드롬 부분 문자열을 반환하여라.

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

풀이

꽤 애먹었던 문제다. 일단 Palindrome은 짝수 길이의 palindrome와 홀수 길이의 palindrome이 존재한다. 언뜻 보면 두 종류의 palindrome을 구하는 함수를 따로 구현해야 할 것 같지만, 초기 왼쪽과 오른쪽을 가리키는 포인터의 간격을 조정함으로써 하나의 함수로 구할 수 있다.

1) Two-Pointer방식을 이용한 find_palindrome함수 구현 구현은 생각보다 간편하다. 왼쪽과 오른쪽을 가리키는 포인터가 문자열의 범위를 넘지 않으면서, 서로 가리키는 문자가 같은 동안에 계속 왼쪽과 오늘쪽을 가리키는 포인터의 값을 조정하는 함수를 구현하면 된다.

2) 예외처리 find_palindrome함수는 길이가 2 이상인 문자열에서 동작한다. 또한, 파이썬은 문자열 반전에 매우 빠른 성능을 보여 주므로, 이 두 사항을 예외로 처리하기로 한다.

3) Sliding-Window기법을 이용하여 최대값 구하기. 이제 문자열의 문자들을 순회하며, find_palindrome이 반환하는 palindrome중 문자열의 길이가 가장 긴 문자열을 찾는다.

이를 Python으로 구현하면 다음과 같다.

class Solution:
    def longestPalindrome(self, s: str) -> str:

        # 팰린드롬을 찾는 함수 구현
        def find_palindrome(left: int, right: int) -> str:
            while left > -1 and right < len(s) and s[left] == s[right]:
                left -= 1; right += 1

            return s[left + 1: right]

        # 예외 처리
        if len(s) < 2 or s == s[::-1]:
            return s

        answer = ''

        # 슬라이딩 윈도우의 크기 비교
        for idx in range(len(s) - 1):
            answer = max(answer, find_palindrome(idx, idx + 1), find_palindrome(idx, idx + 2), key=len)

        return answer

주어진 문자열 배열 strs을 애너그램별로 그룹화하라.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

풀이

'eat'와 'ate'는 애너그램이다. 같은 문자들로 이루어져 있기 때문에, 단어를 이루는 문자들을 사전 순서대로 정렬하게 되면, 같은 결과가 나오게 된다. 따라서 이 문제는 단어를 이루는 문자들을 사전 순서 대로 정렬 한 후, 정렬 순서대로 이어 붙인 단어를 key로 하고, 같은 값을 가지는 단어들의 list를 value로 하는 dictionary를 이용하면 쉽게 풀 수 있다.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        str_dict = defaultdict(list)

        for word in strs:
            str_dict[''.join(sorted(word))].append(word)

        return str_dict.values()

문자열 paragraph와 금지된 단어들의 배열 ** banned** 가 주어진다. banned에 포함되지 않은 단어 중, 가장 많이 사용된 단어를 반환하시오. 답은 유일하며, paragraph에는 banned에 포함되지 않은 적어도 하나의 단어가 존재하고 있다.

Example 1:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.

Example 2:

Input: paragraph = "a.", banned = [] Output: "a"

풀이

문제의 핵심은 banned에 포함되지 않은 단어들의 갯수를 세는 방법이다.

Python에서는 dictionary의 한 종류인 Counter와 defaultdict를 제공하고 있으니, 이를 이용하면 쉽게 풀이할 수 있다.

하지만 여기서 조심할 것은 'Non-alphanumeric문자를 어떻게 걸러낼 것인가' 이다. 여기서는 paragraph의 모든 문자열을 순회하며, Non-alphanumeric문자를 ' '로 대치하는 방법을 사용할 것이다.

이를 Python으로 구현하면 다음과 같다.

1. Counter를 이용한 풀이.

from collections import Counter

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        word_list = []

        # Non-alphanumeric문자를 ' '로 대치
        for char in paragraph:
            if not char.isalnum():
                paragraph = paragraph.replace(char, ' ')

    # paragraph의 모든 문자들을 소문자로 변환.
        paragraph = paragraph.lower()

    #banned에 포함되지 않은 단어들을 list에 삽입.
        for word in paragraph.split():
            if word not in banned:
                word_list.append(word)

        # list를 Counter로 변환.
        word_counter = Counter(word_list)

    #가장 많이 사용된 단어 반환.
        return word_counter.most_common(1)[0][0]

2. defaultdict를 이용한 풀이.

from collections import defaultdict

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        word_dict = defaultdict(int)

        # Non-alphanumeric문자를 ' '로 대치
        for char in paragraph:
            if not char.isalnum():
                paragraph = paragraph.replace(char, ' ')

    # paragraph의 모든 문자들을 소문자로 변환.
        paragraph = paragraph.lower()

    # banned에 포함되지 않은 문자를 key로 개수를 value로 하는 defaultdict 생성.
        for word in paragraph.split():
            if word not in banned:
                word_dict[word] += 1

    # defaultdict를 정렬하여 가장 많이 사용된 단어를 반환.
        return sorted(word_dict.items(), key=lambda x: x[1], reverse=True)[0][0]

logs배열이 주어진다. 각 log는 공백으로 구분된 단어의 문자열이며, 첫 번째 단어는 식별자이다.

두가지 형식의 log들이 존재한다:

• Letter-logs: 식별자를 제외한 모든 단어들이 소문자로 구성된 log.

• Digit-logs: 식별자를 제외한 모든 단어들이 숫자로 구성된 log.

다음 기준에 맞추어 로그를 재정렬하시오.

1. letter-logs는 모든 digit-logs보다 앞에 온다.
   2. letter-logs는 사전 순서대로 정렬한다. 식별자를 제외한 모든 내용이 일치할 경우, 식별자의 사전 순서대로 정렬한다.
   3. digit-logs는 입력 순서를 유지한다.

logs의 정렬 결과를 반환하시오.

Example 1:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"] Explanation: The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig". The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

Example 2:

Input: logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"] Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

풀이

풀이의 골자는 다음과 같다.   #1. letter-logs와 digit-logs를 분리한다.     =>여기서 digit-logs는 입력 순서를 유지하므로, 더이상 정렬할 필요가 없다.   #2. letter-logs를 정렬한다.     => 식별자를 제외한 부분을 1차 정렬 기준으로 세우고, 식별자를 2차 정렬 기준으로 세운다.   #3. 정렬한 letter-logs에 digit-logs를 이어 붙인 새로운 list를 반환한다.

이를 Python으로 구현하면 다음과 같다.

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letters, digits = [], []

        #1.문자로만 이루어진 log와 숫자가 포함된 log를 분리
        for log in logs:
            if log.split()[1].isdigit():
                digits.append(log)
            else:
                letters.append(log)

        #2. 문자로만 이루어진 log list를 정렬.
        letters.sort(key= lambda x: (x.split()[1:], x.split()[0]))

        #3. 문자로만 이루어진 log list와 숫자가 포함된 log list를 합침.
        return letters + digits

문자열을 뒤집는 함수를 작성하라. 입력 문자열은 문자열 배열 s로 주어진다. 제한 사항 다른 배열을 추가 할당하지 말고 리스트 내부를 직접 조작할 것.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

풀이

1. Two Pointer방식.

이 풀이에서는 Two Pointer방식을 사용하여 풀이할 것이다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1

        #Pointer들의 위치를 조정하며, 값을 교환한다.
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1;right -= 1

문자열 s가 주어졌을때, 이 문자열이 palindrome인지 판별하시요. alphanumeric character에 대해서만 고려한다.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

풀이

문제 풀이의 공통된 방법으로는 'alphanumeric 문자들을 따로 모아야 한다는 것.'이다.

1. 자료 구조를 이용한 풀이.

이 풀이에서는 deque를 이용하여 deque의 맨 앞의 문자와, 맨 뒤의 문자를 길이가 2 이상인 동안에 계속 비교하면서 풀이한다.

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        deque = deque()

        # Alphanumeric을 lowercase로 변환하여 deque에 삽입한다.
        for char in s:
            if char.isalnum():
                deque.append(char.lower())

        # deque의 길이가 2 이상일 때, pop()과 popleft()의 크기를 비교한다.
        while len(deque) > 1:
            if deque.pop() != deque.popleft()
                return False    # palindrome이 아니므로 False를 반환하며 종료한다.

        return True        #palindrome이므로 True를 반환하며 종료한다.

2. 문자열 Slicing을 이용한 풀이.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        p_str: str = ''

        # Alphanumeric을 lowercase로 변환하여 deque에 삽입한다.
        for char in s:
            if char.isalnum():
                p_str += char.lower()

        # 문자열과 뒤집은 문자열이 같은지 비교한 결과를 반환한다.       
        return p_str == p_str[::-1]

RAID(Redundant Array of [Independent | Inexpensive] Disks)

• 여러개의 하드 디스크에 동일한 데이터를 다른 위치에 중복해서 저장하는 방법.
• 입출력의 균형을 통해 전체적인 성능을 향상시킨다.
• 운영체제는 RAID를 하나의 디스크로 인식한다.

Clustering: 여러 대의 컴퓨터를 연결하여 하나의 컴퓨터를 사용하는 효과를 내도록 구성한 시스템.

• 사용 목적에 따라 고계산용 클러스터(HPC), 부하분산 클러스터(LVS), 고가용성 클러스터(HA)로 구분할 수 있다.

• 고계산용 클러스터(High Performace Computing Cluster)
  

  • 슈퍼 컴퓨터의 구성 방법.

• 부하분산 클러스터(Linux Virtual Server)

  • 여러대의 물리 서버(Real Server)에 부하 분산을 위한 Load Balanceer를 연결하는 구성방식을 가짐.

• 고가용성 클러스터(High Availablity Clustering)

  • 지속적인 서비스 제공을 목적으로 하는 구성 방식.
  • LV의 문제를 해결하기 위해, 부하 분산 처리를 수행하고 있는 Primary node에 오류가 발생할 경우 Secondary node가 이 업무를 수행.

#2.Cloud Computing

• 사용자가 제시한 작업에 필요한 컴퓨팅 자원이 작업에 할당하여 결과를 도출하도록 하는 컴퓨팅 방식.

• 기존의 그리드 컴퓨팅, 분산 컴퓨팅, 서버 및 스토리지 가상화 기술을 융합한 기술.   =Cloud Computing에서 제공하는 서비스=

• IaaS

  • Infrastructure as a Service.
  • 업무 처리에 필요한 서버, PC, 저장공간과 같은 하드웨어 자원을 빌려쓰는 형태.

• PaaS

  • Platform as a Service.
  • 소프트웨어 개발 환경을 제공받는 형태.

• SaaS

  • Software as a Service.
  • Software자체를 클라우드 형태로 빌려쓰는 형태.

    #3. Big Data

• 기존의 DBMS로 관리할 수 없는 대량의 정형/비정형 데이터에서 가치를 추출하고 결과를 분석하는 기술.

• 사회 예측, 사회 구성원에게 맞춤 정보 제공, 분석 관리.

Big Data관련 기술

• 기존의 통계학 및 전산학에서 사용했던 데이터 마이닝, 기계학습 자연 언어 처리, 패턴 인식등을 사용한다.
• 비정형 데이터 분석을 위한 텍스트 마이닝, 오피니언 마이닝등이 발전하고 있음.
• Hadoop, NoSQL, R등이 이용됨

운영체제의 핵심적인 부분들을 Linux Kernel과 자유 소프트웨어와 공개 프로그램을 모아서 만든 운영체제.

=Linux 배포판 종류=

Package 관리 기법에 따라 Slackware, Debian, RedHat계열로 구분할 수 있다.

Slackware: Upstream에서 최대한 수정되어 배포되는 형식.   사용자들이 내장 프로그램을 사용하기에는 편리하나, Package 수정이 힘듦.   e.g) SuSE, Porteus등등.

Debian: 독자 Package관리 기법인 dpkg, apt를 사용하는 배포판.   e.g)Ubuntu, Linux Mint, Kali Linux

RedHat: 독자 Package관리 기법인 YUM, RPM를 사용하는 배포판.   e.g)RHEL, CentOS, Fedora

 컴퓨터 사용자에게 프로그램 수행 환경을 제공하는 시스템 소프트웨어로, 컴퓨터 하드웨어와 사용자 간의 매개체 역할을 한다.

=OS의 범위=