空놀이

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        for i in range(len(s)):
            if(s[i]=='I'):
                if(i + 1 < len(s) and (s[i+1] == 'V' or s[i+1] == 'X')):
                    sum -=1
                else:
                    sum += 1
            elif(s[i] == 'V'):
                sum += 5
            elif(s[i] == 'X'):
                if(i + 1 < len(s) and (s[i+1] == 'C' or s[i+1] == 'L')):
                    sum -=10
                else:
                    sum += 10
            elif(s[i] == 'L'):
                sum += 50
            elif(s[i] == 'C'):
                if(i + 1 < len(s) and (s[i+1] == 'M' or s[i+1] == 'D')):
                    sum -=100
                else:
                    sum += 100
            elif(s[i] == 'D'):
                sum += 500
            elif(s[i] == 'M'):
                sum += 1000
                
        print(sum)
        return sum

일단 쉬운 문제 많이 풀기!!

class Solution:
    def toLowerCase(self, str: str) -> str:
        str = str.lower()  
        return str
        

하지만 이렇게 lower api를 쓰면 너무 쉬우니 아래 처럼 문자열 처리를 해보자 ㅎㅎ

ord api를 사용하면, A라는 char의 ascii값을 얻을 수 있다.

chr api를 사용하면 ascii값을 다시 char로 변환할 수 있다.

class Solution:
    def toLowerCase(self, str: str) -> str:
        ans = ""
        for i in range(len(str)):
            if(ord(str[i]) >= ord('A') and ord(str[i]) <= ord('Z')):
                print("%d" % (ord(str[i]) - ord('A')))
                ans += chr(ord(str[i]) - ord('A') + ord('a'))
            else:
                ans += str[i]
        return ans

19주차 3/10

전체 17/150

O(N^2) 로 풀었다. 

다음에는 O(N)으로 풀자..ㅎㅎ

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if(nums[i] + nums[j] == target):
                    ans.append(i)
                    ans.append(j)
                    print(ans)
                    return ans

쉬운 문제로 자신감 올리기..

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        length = (int)(len(s) / 2)
        for i in range(length):
            k = len(s) - 1 - i
            temp = s[i]
            s[i] = s[k]
            s[k] = temp
        

C++로만 풀다가 파이썬으로 푸니 어색어색..

푸는 속도도 너무 느리다...

그래서 슬럼프가 왔지만 이번 주말에 극복하기로..

올해 19주가 지났고 약 33주가 남았다.

5월 남은 3주는 일주일에 3개씩 문제를 풀고,

6월부터는 다시 주 5개 문제 풀기 해보자.

코드는 아래에..

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        cnt = 1
        data = ""
        for i in range(len(s)):
            if i % (2*k) == 0:
                cnt = (i + k)
                #print("cnt = %d" % cnt)
                for j in range(k):
                    #print("%d %d" % (i, j))
                    if(i+k-1-j < len(s)):
                        data = data + s[i+k-1-j]
                i = j
            elif(i >= cnt):
                data = data + s[i]
        return data

나는 알고리즘 공부를 아래와 같이 하였다.

기본적으로 '알고리즘 문제 해결 전략'을 한번 읽어 보았다.

그리고 leet code를 풀어보고 있다.

물론 책을 읽고 leet code를 풀어봤자 책 내용은 다 잊어버려서,

leet code를 풀면서 다시 공부하고 싶다.

공부 순서는 아래와 같다.

1. Stack, Queue

http://ddmix.blogspot.kr/2014/12/cppalgo-6-stack-queue.html

- Stack : 입구가 하나, 나중에 들어간 애가 먼저 나옴

- Queue : 입구와 출구가 따로 있음, 먼저 들어간 애가 먼저 나옴

LeetCode 문제 : 323 -> 283

2. Tree 구조 

http://ddmix.blogspot.com/2014/12/cppalgo-7-tree.html

LeetCode 문제 : 589 -> 94 -> 144 -> 297 ->

(1) 이진 트리(Binary Tree)

(2) Tree Traversal

Linked List, Stack 기반:

Pre order - Root, Left, Right : Root가 앞에

Post order - Left, Right, Root : Root 가 뒤에

In-order - Left, Root, Right : Root가 안에

Queue 기반 : Level order : 위에서부터 순차적으로..

1) Root Push

2) Root Pop

3) Left Push, Right Push

4) Left Pop, Left-Left Push, Left-Right Push

5) Right Pop, Right-Left Push, Right Right Push

6) Left-Left Pop

3. 재귀 호출

http://ddmix.blogspot.com/2014/12/cppalgo-8-recursion.html

(1) Flood Fill 비슷한 문제

LeetCode 문제 : 733 -> 200 -> 542 -> 200 -> 130

4-1. 검색

Binary Search 공부

LeetCode 문제 : 35 -> 69 ->74 풀이 완료

4-2. 정렬

Binary Sort -> Merge Sort -> Quick Sort 순으로 공부

5. 그래프

http://ddmix.blogspot.com/2015/02/cppalgo-20-graph-basics.html

(1)  인접 행렬법

정점의 수가  V인 그래프를  VxV 행렬을 이용하여 표현

(2) 인접 리스트

각 노드가 연결된 노드들을 리스트로 만들어 놓는다.

(3) DFS (Depth First Search) 깊이 우선 탐색

(4) BFS (Breadth First Search) 너비 우선 탐색

- 한 정점 V에 인접한 모든 정점을 방문한 후에 다음 정점으로 진행하는 방법

(5) 이중연결

- 두 정점 간에 두개 이상의 단순 경로가 존재함

(6) 가중 그래프

- 간선에 가중치가 있는 그래프

1) 최소 비용 신장트리 우선순위 탐색

2) 최단 경로 찾기 - Dijkstra 알고리즘 

: 시작점을 제외한 다른 정점이 모두 시작점을 가리킨다고 가정

LeetCode 문제 : 994

6. Tree + 그래프

LeetCode 문제 : 863

7. String

* 공부하기 좋은 사이트

(1) http://ddmix.blogspot.com/2014/11/cppalgo.html

(2) https://github.com/CodeClub-JU/Introduction-to-Algorithms-CLRS/blob/master/Introduction%20to%20Algorithms%20-%203rd%20Edition.pdf

Tree를 문자열로 만들고 문자열을 다시 Tree로 만들기

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def __init__(self):
        self.traversal = []
        
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            self.traversal.append('#')
            return ' '.join(self.traversal)
                
        self.traversal.append(str(root.val))
        self.serialize(root.left)
        self.serialize(root.right)
        
        return ' '.join(self.traversal)
        
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        #print(data)
        def makeTree():
            val = next(vals)
            if val == '#':
                return
            root = TreeNode(int(val)) 
            root.left = makeTree()
            root.right = makeTree()
            return root
            
        vals = iter(data.split())
        
        return makeTree()
            
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.traversal = []
        
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        
        self.traversal.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        
        return self.traversal
        
        

inorder 트리 구조가 어떤 것인지 알게 되었다.

class Solution:
    def __init__(self):
        self.traversal = []
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        
        
        self.inorderTraversal(root.left)
        
        self.traversal.append(root.val)
        
        
        self.inorderTraversal(root.right)
        
        return self.traversal

위키백과에 따르면, 트리 구조는 아래와 같다.

이진 탐색 트리에서

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
• 레벨 순서 순회: F, B, G, A, D, I, C, E, H

출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

파이썬 그리고 트리에 익숙해지기

"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        traversal = [root.val]
        for child in root.children:
            traversal.extend(self.preorder(child))
        return traversal

-> 뒤에 나오는 것은 리턴 타입이다

즉 List[int] 가 리턴 타입