空놀이

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))