A Software Guy Blog
0%

200824 TIL

Posted on Edited on In

DFS

Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

  • Java Example

    • TBD

  • Python Example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # DFS (recursive) method definition
    def dfs(graph, v, visited):
      # make visited true for the currently visiting node
      visited[v] = True
      print(v, end=" ")

      # visiting neighbor node recursively
      for i in graph[v]:
        if not visited[i]:
          dfs(graph, i, visited)

BFS

Breath-First Search, 너비 우선 탐색, 가까운 노드부터 시작하여 영역을 점점 넓히며 탐색 하는 알고리즘이다.

  • Java Example

    • TBD

  • Python Example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    from collections import deque


    # Implementation of BFS method
    def bfs(graph, start, visited):
        # using queue
        queue = deque([start])
        # Make visited currently visiting node
        visited[start] = True
        # Repeat until queue is empty
        while queue:
            v = queue.popleft()
            print(v, end=" ")
            # adding node to queue which is not visited and neighbor to current node
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

Sorting

Selection Sort

  • 매번 가장 작은 것을 선택하여 앞의 인덱스로 옮겨 나가는 알고리즘

  • 선택 정렬의 시간 복잡도: O(N^2)

  • Python Example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

    # Implementation Selection Sort
    for i in range(len(array))
      min_index = i
      for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
          min_index = j
      array[i], array[min_index] = array[min_index], array[i]

Insertion Sort

  • 필요한 경우 데이터의 위치를 바꾸며 정렬

  • 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 선택정렬과 비교

    • 데이터가 일부 정렬되어 있는 경우 유리 이런경우 O(N)에 가깝다.

  • Python Example

    1
    2
    3
    4
    5
    6
    7
    8
    # Implementation of insertion sort
    def insertion_sort(array):
      for i in range(1, len(array)):
        for j in range(i, 0, -1):
          if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
          else:
            break

Java Exception Handling

Exception

Definition: An exception is an event, which occurs during the execution of a program, that distrupt the normal flow of the program’s instructions.
When the an error occurs within a method, the method creates an object and hands it off to the runtime system.
The object, called exception object, contains information about the error, including its type and the state of the program when the error occured.
Creating an exception object and handing it to the runtime system is called throwing an exception.

Advantages of Exceptions

1. Seperating Error-Handling Code from “Regular” Code

Exceptions enable you to write the main flow of your code and to deal with the exceptional cases elsewhere.
If the readFile function used exceptions instead of traditional error-management techniques, it would look more like the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
readFile {
  try {
    open the file;
    determine its size;
    allocate that much memory;
    read the file into memory;
    close the file;
  } catch (fileOpenFailed) {
    doSomething;
  } catch (sizeDeterminationFailed) {
      doSomething;
  } catch (memoryAllocationFailed) {
      doSomething;
  } catch (readFailed) {
      doSomething;
  } catch (fileCloseFailed) {
      doSomething;
  }
}

2. Propagating Errors Up the Call Stack

A second advantage of exceptions is the ablity to propagate error reporting up the call stack of methods.

A method can duck any exceptions thrown within it, thereby allowing a method farther up the call stack to catch it.
Hence, only the methods that care about errors have to worry about decting errors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
method1 {
  try {
      call method2;
  } catch (exception e) {
      doErrorProcessing;
  }
}

method2 throws exception {
  call method3;
}

method3 throws exception {
  call readFile;
}

3. Grouping and Differentiating Error Types

Because of all exceptions thrown within a program are objects, the grouping or categorizing exceptions is a natural outcome of the class hierarchy.

The try Block

The first step in constructing an exception handler is to enclose the code that might throw an exception within try block.
In general, a try block looks like the following:

1
2
3
4
try {
  code
}
catch and finally blocks...

The segment in the example labeled code contains one or more legal lines of code that throw an exception.

The catch Blocks

You associate exception handlers with a try block by providing one or more catch blocks directly after the try block.

1
2
3
4
5
6
7
try {

} catch (ExceptionType name) {

} catch (ExceptionType name) {

}

Each catch block is an exception handler that handles the the type of exception indicated by its argument.
The arguments type, ExceptionType, declares the type of exception that the handler can handle and must be the
name of a class that inherits form the Throwable class. The handler can refer to the exception with name.

Exception handlers can do more than just print error messages or halt the program.
They can do error recovery, prompt the user to make a decision, or propagate the error up to a higher-level handler using chanined exceptions.

The finally Block

The finally block always executes when the try block exits.
This ensures that the finally block is executed even if an unexpected exception occurs.
But finally is useful for more than just exception handling – it allows the programmer to avoid having cleanup code accidentally bypassed
by a return, continue, or break. Putting cleanup code in finally block is always a good practice, even when no exceptions are anticipated.

Important: The finally block is a key tool for preventing resource leaks.
When closing a file or otherwise recovering resources, place the code in a finally block to ensure that resource is always recovered.

Consider using the try-with-resources statement in these situations, which automatically release system resource when no longer needed.