MATH Archives - icodebroker

[PYTHON/COMMON] sample 함수 : 임의의 문자 리스트 구하기

■ sample 함수를 사용해 임의의 문자 리스트를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import random
import string

stringList = random.sample(list(string.ascii_lowercase), 25)

print(stringList)

"""
['e', 'x', 'h', 'o', 'j', 'd', 'q', 'm', 'b', 'v', 'w', 'k', 'l', 'r', 's', 'u', 'i', 'g', 'a', 'f', 'n', 'z', 'c', 'p', 't']
"""

import random

import string

stringList = random.sample(list(string.ascii_lowercase), 25)

print(stringList)

"""

['e', 'x', 'h', 'o', 'j', 'd', 'q', 'm', 'b', 'v', 'w', 'k', 'l', 'r', 's', 'u', 'i', 'g', 'a', 'f', 'n', 'z', 'c', 'p', 't']

"""

[PYTHON/SCIPY] scipy 패키지 설치하기

■ scipy 패키지를 설치하는 방법을 보여준다. 1. 명령 프롬프트를 실행한다. 2. 명령 프롬프트에서 아래 명령을 실행한다. ▶ 실행 명령


pip install scipy

pip install scipy

[PYTHON/NUMPY] numpy 패키지 설치하기

■ numpy 패키지를 설치하는 방법을 보여준다. 1. 명령 프롬프트를 실행한다. 2. 명령 프롬프트에서 아래 명령을 실행한다. ▶ 실행 명령


pip install numpy

pip install numpy

[C#/COMMON/.NET6] 다익스트라(Dijkstra) 알고리즘을 사용해 그래프에서 최단 경로 리스트 구하기

■ 다익스트라(Dijkstra) 알고리즘을 사용해 그래프에서 최단 경로 리스트를 구하는 방법을 보여준다. ▶ Graph.cs


namespace TestProject;

/// <summary>
/// 그래프
/// </summary>
public class Graph
{
    //////////////////////////////////////////////////////////////////////////////////////////////////// Field
    ////////////////////////////////////////////////////////////////////////////////////////// Private

    #region Field

    /// <summary>
    /// 버텍스 딕셔너리
    /// </summary>
    private Dictionary<string, Dictionary<string, int>> vertexDictionary = new Dictionary<string, Dictionary<string, int>>();

    #endregion

    //////////////////////////////////////////////////////////////////////////////////////////////////// Method
    ////////////////////////////////////////////////////////////////////////////////////////// Public

    #region 에지 추가하기 - AddEdge(startNode, endNode, weight)

    /// <summary>
    /// 에지 추가하기
    /// </summary>
    /// <param name="startNode">시작 노드</param>
    /// <param name="endNode">종료 노드</param>
    /// <param name="weight">가중치</param>
    public void AddEdge(string startNode, string endNode, int weight)
    {
        if(!this.vertexDictionary.ContainsKey(startNode))
        {
            this.vertexDictionary[startNode] = new Dictionary<string, int>();
        }

        this.vertexDictionary[startNode][endNode] = weight;
    }

    #endregion
    #region 최단 경로 리스트 구하기 - GetShortestPathList(startNode, endNode)

    /// <summary>
    /// 최단 경로 리스트 구하기
    /// </summary>
    /// <param name="startNode">시작 노드</param>
    /// <param name="endNode">종료 노드</param>
    /// <returns>최단 경로 리스트</returns>
    public List<string> GetShortestPathList(string startNode, string endNode)
    {
        Dictionary<string, int> distanceDictionary = new Dictionary<string, int>();

        Dictionary<string, string> previousNodeDictionary = new Dictionary<string, string>();

        List<string> nodeList = new List<string>();

        List<string> pathList = null;

        foreach(KeyValuePair<string, Dictionary<string, int>> keyValurPair in vertexDictionary)
        {
            if(keyValurPair.Key == startNode)
            {
                distanceDictionary[keyValurPair.Key] = 0;
            }
            else
            {
                distanceDictionary[keyValurPair.Key] = int.MaxValue;
            }

            nodeList.Add(keyValurPair.Key);
        }

        while(nodeList.Count != 0)
        {
            nodeList.Sort((x, y) => distanceDictionary[x].CompareTo(distanceDictionary[y]));

            string smallestNode = nodeList[0];

            nodeList.Remove(smallestNode);

            if(smallestNode == endNode)
            {
                pathList = new List<string>();

                while(previousNodeDictionary.ContainsKey(smallestNode))
                {
                    pathList.Add(smallestNode);

                    smallestNode = previousNodeDictionary[smallestNode];
                }

                pathList.Add(startNode);

                pathList.Reverse();
            }

            if(distanceDictionary[smallestNode] == int.MaxValue)
            {
                break;
            }

            if(vertexDictionary.ContainsKey(smallestNode))
            {
                foreach(KeyValuePair<string, int> neighbor in vertexDictionary[smallestNode])
                {
                    if (!distanceDictionary.ContainsKey(neighbor.Key))
                    {
                        distanceDictionary[neighbor.Key] = int.MaxValue;
                        nodeList.Add(neighbor.Key);
                    }

                    var alt = distanceDictionary[smallestNode] + neighbor.Value;
                    if (alt < distanceDictionary[neighbor.Key])
                    {
                        distanceDictionary[neighbor.Key] = alt;
                        previousNodeDictionary[neighbor.Key] = smallestNode;
                    }
                }
            }
        }

        return pathList;
    }

    #endregion
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

namespace TestProject;

/// <summary>

/// 그래프

/// </summary>

public class Graph

{

//////////////////////////////////////////////////////////////////////////////////////////////////// Field

////////////////////////////////////////////////////////////////////////////////////////// Private

#region Field

/// <summary>

/// 버텍스 딕셔너리

/// </summary>

private Dictionary<string, Dictionary<string, int>> vertexDictionary = new Dictionary<string, Dictionary<string, int>>();

#endregion

//////////////////////////////////////////////////////////////////////////////////////////////////// Method

////////////////////////////////////////////////////////////////////////////////////////// Public

#region 에지 추가하기 - AddEdge(startNode, endNode, weight)

/// <summary>

/// 에지 추가하기

/// </summary>

/// <param name="startNode">시작 노드</param>

/// <param name="endNode">종료 노드</param>

/// <param name="weight">가중치</param>

public void AddEdge(string startNode, string endNode, int weight)

{

if(!this.vertexDictionary.ContainsKey(startNode))

{

this.vertexDictionary[startNode] = new Dictionary<string, int>();

}

this.vertexDictionary[startNode][endNode] = weight;

}

#endregion

#region 최단 경로 리스트 구하기 - GetShortestPathList(startNode, endNode)

/// <summary>

/// 최단 경로 리스트 구하기

/// </summary>

/// <param name="startNode">시작 노드</param>

/// <param name="endNode">종료 노드</param>

/// <returns>최단 경로 리스트</returns>

public List<string> GetShortestPathList(string startNode, string endNode)

{

Dictionary<string, int> distanceDictionary = new Dictionary<string, int>();

Dictionary<string, string> previousNodeDictionary = new Dictionary<string, string>();

List<string> nodeList = new List<string>();

List<string> pathList = null;

foreach(KeyValuePair<string, Dictionary<string, int>> keyValurPair in vertexDictionary)

{

if(keyValurPair.Key == startNode)

{

distanceDictionary[keyValurPair.Key] = 0;

}

else

{

distanceDictionary[keyValurPair.Key] = int.MaxValue;

}

nodeList.Add(keyValurPair.Key);

}

while(nodeList.Count != 0)

{

nodeList.Sort((x, y) => distanceDictionary[x].CompareTo(distanceDictionary[y]));

string smallestNode = nodeList[0];

nodeList.Remove(smallestNode);

if(smallestNode == endNode)

{

pathList = new List<string>();

while(previousNodeDictionary.ContainsKey(smallestNode))

{

pathList.Add(smallestNode);

smallestNode = previousNodeDictionary[smallestNode];

}

pathList.Add(startNode);

pathList.Reverse();

}

if(distanceDictionary[smallestNode] == int.MaxValue)

{

break;

}

if(vertexDictionary.ContainsKey(smallestNode))

{

foreach(KeyValuePair<string, int> neighbor in vertexDictionary[smallestNode])

{

if (!distanceDictionary.ContainsKey(neighbor.Key))

{

distanceDictionary[neighbor.Key] = int.MaxValue;

nodeList.Add(neighbor.Key);

}

var alt = distanceDictionary[smallestNode] + neighbor.Value;

if (alt < distanceDictionary[neighbor.Key])

{

distanceDictionary[neighbor.Key] = alt;

previousNodeDictionary[neighbor.Key] = smallestNode;

}

return pathList;

}

#endregion

}

▶ Program.cs


namespace TestProject;

/// <summary>
/// 프로그램
/// </summary>
class Program
{
    //////////////////////////////////////////////////////////////////////////////////////////////////// Method
    ////////////////////////////////////////////////////////////////////////////////////////// Static
    //////////////////////////////////////////////////////////////////////////////// Private

    #region 프로그램 시작하기 - Main()

    /// <summary>
    /// 프로그램 시작하기
    /// </summary>
    static void Main()
    {
        Graph graph = new Graph();

        graph.AddEdge("A", "B", 4);
        graph.AddEdge("A", "C", 2);
        graph.AddEdge("A", "D", 7);
        graph.AddEdge("B", "D", 1);
        graph.AddEdge("B", "C", 3);
        graph.AddEdge("D", "E", 5);
        graph.AddEdge("E", "F", 2);

        List<string> shortestPathList = graph.GetShortestPathList("A", "F");

        Console.WriteLine("A에서 F까지의 최단 경로 :");
        Console.WriteLine(string.Join(" -> ", shortestPathList));
    }

    #endregion
}

namespace TestProject;

/// <summary>

/// 프로그램

/// </summary>

class Program

{

//////////////////////////////////////////////////////////////////////////////////////////////////// Method

////////////////////////////////////////////////////////////////////////////////////////// Static

//////////////////////////////////////////////////////////////////////////////// Private

#region 프로그램 시작하기 - Main()

/// <summary>

/// 프로그램 시작하기

/// </summary>

static void Main()

{

Graph graph = new Graph();

graph.AddEdge("A", "B", 4);

graph.AddEdge("A", "C", 2);

graph.AddEdge("A", "D", 7);

graph.AddEdge("B", "D", 1);

graph.AddEdge("B", "C", 3);

graph.AddEdge("D", "E", 5);

graph.AddEdge("E", "F", 2);

List<string> shortestPathList = graph.GetShortestPathList("A", "F");

Console.WriteLine("A에서 F까지의 최단 경로 :");

Console.WriteLine(string.Join(" -> ", shortestPathList));

}

#endregion

}

TestProject.zip

[C#/COMMON/.NET6] Hill Climbing 알고리즘 : 최적해 구하기

■ Hill Climbing 알고리즘을 사용해 최적해를 구하는 방법을 보여준다. ▶ Program.cs


namespace TestProject;

public class Program
{
    //////////////////////////////////////////////////////////////////////////////////////////////////// Method
    ////////////////////////////////////////////////////////////////////////////////////////// Static
    //////////////////////////////////////////////////////////////////////////////// Private

    #region 목표 함수 처리하기 - ObjectiveFunction(x)

    /// <summary>
    /// 목표 함수 처리하기
    /// </summary>
    /// <param name="x">X 인자</param>
    /// <returns>목표 함수</returns>
    private static double ObjectiveFunction(double x)
    {
        return -(x * x) + 5 * x + 10; // 예 : f(x) = -x^2 + 5x + 10
    }

    #endregion
    #region 최적화하기 - Optimize(start, stepSize, maximumIterationCount)

    /// <summary>
    /// 최적화하기
    /// </summary>
    /// <remarks>Hill Climbing 알고리즘을 사용한다.</remarks>
    /// <param name="start">시작</param>
    /// <param name="stepSize">단계 크기</param>
    /// <param name="maximumIterationCount">최대 반복 수</param>
    /// <returns>최적해</returns>
    private static double Optimize(double start, double stepSize, int maximumIterationCount)
    {
        double currentX     = start;
        double currentValue = ObjectiveFunction(currentX);

        for(int i = 0; i < maximumIterationCount; i++)
        {
            double leftX  = currentX - stepSize;
            double rightX = currentX + stepSize;

            double leftValue  = ObjectiveFunction(leftX);
            double rightValue = ObjectiveFunction(rightX);

            if(leftValue > currentValue && leftValue > rightValue)
            {
                currentX     = leftX;
                currentValue = leftValue;
            }
            else if(rightValue > currentValue)
            {
                currentX     = rightX;
                currentValue = rightValue;
            }
            else
            {
                break;
            }
        }

        return currentX;
    }

    #endregion

    #region 프로그램 시작하기 - Main()

    /// <summary>
    /// 프로그램 시작하기
    /// </summary>
    private static void Main()
    {
        double startX                = 0;
        double stepSize              = 0.1;
        int    maximumIterationCount = 100;

        double result = Optimize(startX, stepSize, maximumIterationCount);

        Console.WriteLine($"최적해 : x = {result}, f(x) = {ObjectiveFunction(result)}");
    }

    #endregion
}

namespace TestProject;

public class Program

{

//////////////////////////////////////////////////////////////////////////////////////////////////// Method

////////////////////////////////////////////////////////////////////////////////////////// Static

//////////////////////////////////////////////////////////////////////////////// Private

#region 목표 함수 처리하기 - ObjectiveFunction(x)

/// <summary>

/// 목표 함수 처리하기

/// </summary>

/// <param name="x">X 인자</param>

/// <returns>목표 함수</returns>

private static double ObjectiveFunction(double x)

{

return -(x * x) + 5 * x + 10; // 예 : f(x) = -x^2 + 5x + 10

}

#endregion

#region 최적화하기 - Optimize(start, stepSize, maximumIterationCount)

/// <summary>

/// 최적화하기

/// </summary>

/// <remarks>Hill Climbing 알고리즘을 사용한다.</remarks>

/// <param name="start">시작</param>

/// <param name="stepSize">단계 크기</param>

/// <param name="maximumIterationCount">최대 반복 수</param>

/// <returns>최적해</returns>

private static double Optimize(double start, double stepSize, int maximumIterationCount)

{

double currentX = start;

double currentValue = ObjectiveFunction(currentX);

for(int i = 0; i < maximumIterationCount; i++)

{

double leftX = currentX - stepSize;

double rightX = currentX + stepSize;

double leftValue = ObjectiveFunction(leftX);

double rightValue = ObjectiveFunction(rightX);

if(leftValue > currentValue && leftValue > rightValue)

{

currentX = leftX;

currentValue = leftValue;

}

else if(rightValue > currentValue)

{

currentX = rightX;

currentValue = rightValue;

}

else

{

break;

}

return currentX;

}

#endregion

#region 프로그램 시작하기 - Main()

/// <summary>

/// 프로그램 시작하기

/// </summary>

private static void Main()

{

double startX = 0;

double stepSize = 0.1;

int maximumIterationCount = 100;

double result = Optimize(startX, stepSize, maximumIterationCount);

Console.WriteLine($"최적해 : x = {result}, f(x) = {ObjectiveFunction(result)}");

}

#endregion

}

TestProject.zip

[PYTHON/COMMON] 카라츠바(Karatsuba) 알고리즘을 사용해 큰 수 곱하기

■ 카라츠바(Karatsuba) 알고리즘을 사용해 큰 수를 곱하는 방법을 보여준다. ▶ 예제 코드 (PY)


def multiplyWthKaratsubaAlgorithm(x, y):
    xString = str(x)
    yString = str(y)

    maximumLength = max(len(xString), len(yString))

    if maximumLength == 1:
        return x * y

    middleIndex = maximumLength // 2

    if middleIndex == 1:
        return x * y

    firstX = int(xString[:-middleIndex])
    lastX  = int(xString[-middleIndex:])
    firstY = int(yString[:-middleIndex])
    lastY  = int(yString[-middleIndex:])

    firstXY = multiplyWthKaratsubaAlgorithm(firstX, firstY)
    lastXY  = multiplyWthKaratsubaAlgorithm(lastX, lastY)
    xy      = multiplyWthKaratsubaAlgorithm((firstX + lastX), (firstY + lastY)) - firstXY - lastXY

    targetValue = firstXY * 10 ** (2 * middleIndex) + xy * 10 ** middleIndex + lastXY

    return targetValue

x = 123456789012345678901234567890
y = 987654321098765432109876543210

targetValue = multiplyWthKaratsubaAlgorithm(x, y)

print(targetValue)

"""
121932631137021795226185032733622923332237463801111263526900
"""

def multiplyWthKaratsubaAlgorithm(x, y):

xString = str(x)

yString = str(y)

maximumLength = max(len(xString), len(yString))

if maximumLength == 1:

return x * y

middleIndex = maximumLength // 2

if middleIndex == 1:

return x * y

firstX = int(xString[:-middleIndex])

lastX = int(xString[-middleIndex:])

firstY = int(yString[:-middleIndex])

lastY = int(yString[-middleIndex:])

firstXY = multiplyWthKaratsubaAlgorithm(firstX, firstY)

lastXY = multiplyWthKaratsubaAlgorithm(lastX, lastY)

xy = multiplyWthKaratsubaAlgorithm((firstX + lastX), (firstY + lastY)) - firstXY - lastXY

targetValue = firstXY * 10 ** (2 * middleIndex) + xy * 10 ** middleIndex + lastXY

return targetValue

x = 123456789012345678901234567890

y = 987654321098765432109876543210

targetValue = multiplyWthKaratsubaAlgorithm(x, y)

print(targetValue)

"""

121932631137021795226185032733622923332237463801111263526900

"""

[PYTHON/COMMON] 비트 연산자 사용하기

■ 비트 연산자를 사용하는 방법을 보여준다. ▶ 예제 코드 (PY)


x = 0b0110
y = 0b1010

print(bin(x | y ), x | y ) # 0b1110 14
print(bin(x & y ), x & y ) # 0b10 2
print(bin(x ^ y ), x ^ y ) # 0b1100 12
print(bin(x << 1), x << 1) # 0b1100 12
print(bin(y >> 1), y >> 1) # 0b101 5
print(bin(~x    ), ~x    ) # -0b111 -7

x = 0b0110

y = 0b1010

print(bin(x | y ), x | y ) # 0b1110 14

print(bin(x & y ), x & y ) # 0b10 2

print(bin(x ^ y ), x ^ y ) # 0b1100 12

print(bin(x << 1), x << 1) # 0b1100 12

print(bin(y >> 1), y >> 1) # 0b101 5

print(bin(~x ), ~x ) # -0b111 -7

[PYTHON/COMMON] 그래프에서 포드-풀커슨(Ford Fulkerson) 알고리즘을 사용해 최대 유량 구하기

■ 그래프에서 포드-풀커슨(Ford Fulkerson) 알고리즘을 사용해 최대 유량을 구하는 방법을 보여준다. ▶ main.py


def getFordFulkersonMaximumFlow(graphListList, source, sink):
    def bfs(graph):
        visitedList = [False] * len(graph)
        queueList   = []

        queueList.append(source)

        visitedList[source] = True

        while queueList:
            u = queueList.pop(0)

            for index, value in enumerate(graph[u]):
                if visitedList[index] == False and value > 0:
                    queueList.append(index)

                    visitedList[index] = True

                    parentList[index] = u

                    if index == sink:
                        return True
        return False

    parentList  = [-1] * len(graphListList)
    maximumFlow = 0

    while bfs(graphListList):
        pathFlow = float("inf")
        s        = sink

        while(s != source):
            pathFlow = min(pathFlow, graphListList[parentList[s]][s])
            s        = parentList[s]

        maximumFlow += pathFlow

        v = sink

        while(v != source):
            u = parentList[v]

            graphListList[u][v] -= pathFlow
            graphListList[v][u] += pathFlow

            v = parentList[v]

    return maximumFlow

graphListList = [
    [0, 16, 13,  0,  0,  0],
    [0,  0, 10, 12,  0,  0],
    [0,  4,  0,  0, 14,  0],
    [0,  0,  9,  0,  0, 20],
    [0,  0,  0,  7,  0,  4],
    [0,  0,  0,  0,  0,  0]
]

maximumFlow = getFordFulkersonMaximumFlow(graphListList, 0, 5)

print("최대 유량 :", maximumFlow)

"""
최대 유량 : 23
"""

def getFordFulkersonMaximumFlow(graphListList, source, sink):

def bfs(graph):

visitedList = [False] * len(graph)

queueList = []

queueList.append(source)

visitedList[source] = True

while queueList:

u = queueList.pop(0)

for index, value in enumerate(graph[u]):

if visitedList[index] == False and value > 0:

queueList.append(index)

visitedList[index] = True

parentList[index] = u

if index == sink:

return True

return False

parentList = [-1] * len(graphListList)

maximumFlow = 0

while bfs(graphListList):

pathFlow = float("inf")

s = sink

while(s != source):

pathFlow = min(pathFlow, graphListList[parentList[s]][s])

s = parentList[s]

maximumFlow += pathFlow

v = sink

while(v != source):

u = parentList[v]

graphListList[u][v] -= pathFlow

graphListList[v][u] += pathFlow

v = parentList[v]

return maximumFlow

graphListList = [

[0, 16, 13, 0, 0, 0],

[0, 0, 10, 12, 0, 0],

[0, 4, 0, 0, 14, 0],

[0, 0, 9, 0, 0, 20],

[0, 0, 0, 7, 0, 4],

[0, 0, 0, 0, 0, 0]

]

maximumFlow = getFordFulkersonMaximumFlow(graphListList, 0, 5)

print("최대 유량 :", maximumFlow)

"""

최대 유량 : 23

"""

[PYTHON/COMMON] 포인트 리스트를 둘러싸는 외곽선(Convex Hull) 구하기

■ 포인트 리스트를 둘러싸는 외곽선(Convex Hull)을 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


def getOrientation(pointTuple1, pointTuple2, pointTuple3):
    value = (pointTuple2[1] - pointTuple1[1]) * (pointTuple3[0] - pointTuple2[0]) - (pointTuple2[0] - pointTuple1[0]) * (pointTuple3[1] - pointTuple2[1])
    if value == 0:
        return 0  # 일직선 상에 위치한 경우
    elif value > 0:
        return 1  # 반시계 방향인 경우
    else:
        return 2  # 시계 방향인 경우

def getConvexHullPointTupleList(sourcePointTupleList):
    sourcePointTupleListLength = len(sourcePointTupleList)

    if sourcePointTupleListLength < 3:
        return None

    convexHullPointTupleList = []

    mostLeftIndex = 0

    for pointIndex2 in range(1, sourcePointTupleListLength):
        if sourcePointTupleList[pointIndex2][0] < sourcePointTupleList[mostLeftIndex][0]:
            mostLeftIndex = pointIndex2
        elif sourcePointTupleList[pointIndex2][0] == sourcePointTupleList[mostLeftIndex][0] and sourcePointTupleList[pointIndex2][1] < sourcePointTupleList[mostLeftIndex][1]:
            mostLeftIndex = pointIndex2

    pointIndex1 = mostLeftIndex
    pointIndex3 = None

    while True:
        convexHullPointTupleList.append(sourcePointTupleList[pointIndex1])

        pointIndex3 = (pointIndex1 + 1) % sourcePointTupleListLength

        for pointIndex2 in range(sourcePointTupleListLength):
            if getOrientation(sourcePointTupleList[pointIndex1], sourcePointTupleList[pointIndex2], sourcePointTupleList[pointIndex3]) == 2:
                pointIndex3 = pointIndex2

        pointIndex1 = pointIndex3

        if pointIndex1 == mostLeftIndex:
            break

    return convexHullPointTupleList

sourcePointTupleList = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]

convexHullPointTupleList = getConvexHullPointTupleList(sourcePointTupleList)

print(convexHullPointTupleList) # [(0, 0), (3, 1), (4, 4), (0, 3)]

def getOrientation(pointTuple1, pointTuple2, pointTuple3):

value = (pointTuple2[1] - pointTuple1[1]) * (pointTuple3[0] - pointTuple2[0]) - (pointTuple2[0] - pointTuple1[0]) * (pointTuple3[1] - pointTuple2[1])

if value == 0:

return 0 # 일직선 상에 위치한 경우

elif value > 0:

return 1 # 반시계 방향인 경우

else:

return 2 # 시계 방향인 경우

def getConvexHullPointTupleList(sourcePointTupleList):

sourcePointTupleListLength = len(sourcePointTupleList)

if sourcePointTupleListLength < 3:

return None

convexHullPointTupleList = []

mostLeftIndex = 0

for pointIndex2 in range(1, sourcePointTupleListLength):

if sourcePointTupleList[pointIndex2][0] < sourcePointTupleList[mostLeftIndex][0]:

mostLeftIndex = pointIndex2

elif sourcePointTupleList[pointIndex2][0] == sourcePointTupleList[mostLeftIndex][0] and sourcePointTupleList[pointIndex2][1] < sourcePointTupleList[mostLeftIndex][1]:

mostLeftIndex = pointIndex2

pointIndex1 = mostLeftIndex

pointIndex3 = None

while True:

convexHullPointTupleList.append(sourcePointTupleList[pointIndex1])

pointIndex3 = (pointIndex1 + 1) % sourcePointTupleListLength

for pointIndex2 in range(sourcePointTupleListLength):

if getOrientation(sourcePointTupleList[pointIndex1], sourcePointTupleList[pointIndex2], sourcePointTupleList[pointIndex3]) == 2:

pointIndex3 = pointIndex2

pointIndex1 = pointIndex3

if pointIndex1 == mostLeftIndex:

break

return convexHullPointTupleList

sourcePointTupleList = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]

convexHullPointTupleList = getConvexHullPointTupleList(sourcePointTupleList)

print(convexHullPointTupleList) # [(0, 0), (3, 1), (4, 4), (0, 3)]

[PYTHON/COMMON] 분할 가능 배낭 문제(Fractional Knapsack Problem) 구현하기

■ 분할 가능 배낭 문제(Fractional Knapsack Problem)를 구현하는 방법을 보여준다. ▶ 예제 코드 (PY)


from dataclasses import dataclass

@dataclass
class Item:
    name   : str
    value  : int
    weight : int

    def __init__(self, name, value, weight):
        self.name   = name   # 항목명
        self.value  = value  # 항목의 가치
        self.weight = weight # 항목의 무게

def solveKnapsackFractional(sourceItemList, capacity):
    sourceItemList.sort(key = lambda x : x.value / x.weight, reverse = True)

    maximumValue = 0

    knapsackItemList = []

    for sourceItem in sourceItemList:
        if sourceItem.weight <= capacity:
            knapsackItemList.append(sourceItem)

            capacity -= sourceItem.weight
        else:
            fraction = capacity / sourceItem.weight

            value = sourceItem.value * fraction

            if value > 0:
                knapsackItemList.append(Item(sourceItem.name, value, sourceItem.weight * fraction))

            break

    for knapsackItem in knapsackItemList:
        maximumValue += knapsackItem.value

    return knapsackItemList, maximumValue

sourceItemList = [
    Item("물건 1", 120, 30),
    Item("물건 2", 200, 50),
    Item("물건 3", 150, 20),
    Item("물건 4",  80, 70),
    Item("물건 5", 100, 60)
]

capacity = 100

knapsackItemList, totalValue = solveKnapsackFractional(sourceItemList, capacity)

print(knapsackItemList)
print(totalValue)

"""
[Item(name='물건 3', value=150, weight=20), Item(name='물건 1', value=120, weight=30), Item(name='물건 2', value=200, weight=50)]
470
"""

from dataclasses import dataclass

@dataclass

class Item:

name : str

value : int

weight : int

def __init__(self, name, value, weight):

self.name = name # 항목명

self.value = value # 항목의 가치

self.weight = weight # 항목의 무게

def solveKnapsackFractional(sourceItemList, capacity):

sourceItemList.sort(key = lambda x : x.value / x.weight, reverse = True)

maximumValue = 0

knapsackItemList = []

for sourceItem in sourceItemList:

if sourceItem.weight <= capacity:

knapsackItemList.append(sourceItem)

capacity -= sourceItem.weight

else:

fraction = capacity / sourceItem.weight

value = sourceItem.value * fraction

if value > 0:

knapsackItemList.append(Item(sourceItem.name, value, sourceItem.weight * fraction))

break

for knapsackItem in knapsackItemList:

maximumValue += knapsackItem.value

return knapsackItemList, maximumValue

sourceItemList = [

Item("물건 1", 120, 30),

Item("물건 2", 200, 50),

Item("물건 3", 150, 20),

Item("물건 4", 80, 70),

Item("물건 5", 100, 60)

]

capacity = 100

knapsackItemList, totalValue = solveKnapsackFractional(sourceItemList, capacity)

print(knapsackItemList)

print(totalValue)

"""

[Item(name='물건 3', value=150, weight=20), Item(name='물건 1', value=120, weight=30), Item(name='물건 2', value=200, weight=50)]

470

"""

[PYTHON/NUMPY] 스트라센의 행렬 곱셈(Strassen’s Matrix Multiplication) 알고리즘을 사용해 행렬 곱하기

■ 스트라센의 행렬 곱셈(Strassen's Matrix Multiplication) 알고리즘을 사용해 행렬을 곱하는 방법을 보여준다. ▶ main.py


import numpy as np

def multiplyMatrixWithStrassenAlgorithm(matrix1, matrix2):
    matrix1Length = len(matrix1)

    if matrix1Length == 1:
        return matrix1 * matrix2

    newSize = matrix1Length // 2

    a11 = matrix1[:newSize, :newSize]
    a12 = matrix1[:newSize, newSize:]
    a21 = matrix1[newSize:, :newSize]
    a22 = matrix1[newSize:, newSize:]

    b11 = matrix2[:newSize, :newSize]
    b12 = matrix2[:newSize, newSize:]
    b21 = matrix2[newSize:, :newSize]
    b22 = matrix2[newSize:, newSize:]

    m1 = multiplyMatrixWithStrassenAlgorithm(a11 + a22, b11 + b22)
    m2 = multiplyMatrixWithStrassenAlgorithm(a21 + a22, b11)
    m3 = multiplyMatrixWithStrassenAlgorithm(a11, b12 - b22)
    m4 = multiplyMatrixWithStrassenAlgorithm(a22, b21 - b11)
    m5 = multiplyMatrixWithStrassenAlgorithm(a11 + a12, b22)
    m6 = multiplyMatrixWithStrassenAlgorithm(a21 - a11, b11 + b12)
    m7 = multiplyMatrixWithStrassenAlgorithm(a12 - a22, b21 + b22)

    c11 = m1 + m4 - m5 + m7
    c12 = m3 + m5
    c21 = m2 + m4
    c22 = m1 - m2 + m3 + m6

    return np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))

sourcMatrix1 = np.array(
    [
        [1 , 2 , 3 , 4 ],
        [5 , 6 , 7 , 8 ],
        [9 , 10, 11, 12],
        [13, 14, 15, 16]
    ]
)

sourceMatrix2 = np.array(
    [
        [17, 18, 19, 20],
        [21, 22, 23, 24],
        [25, 26, 27, 28],
        [29, 30, 31, 32]
    ]
)

targetMatrix = multiplyMatrixWithStrassenAlgorithm(sourcMatrix1, sourceMatrix2)

print(targetMatrix)

"""
[[ 250  260  270  280]
 [ 618  644  670  696]
 [ 986 1028 1070 1112]
 [1354 1412 1470 1528]]
"""

import numpy as np

def multiplyMatrixWithStrassenAlgorithm(matrix1, matrix2):

matrix1Length = len(matrix1)

if matrix1Length == 1:

return matrix1 * matrix2

newSize = matrix1Length // 2

a11 = matrix1[:newSize, :newSize]

a12 = matrix1[:newSize, newSize:]

a21 = matrix1[newSize:, :newSize]

a22 = matrix1[newSize:, newSize:]

b11 = matrix2[:newSize, :newSize]

b12 = matrix2[:newSize, newSize:]

b21 = matrix2[newSize:, :newSize]

b22 = matrix2[newSize:, newSize:]

m1 = multiplyMatrixWithStrassenAlgorithm(a11 + a22, b11 + b22)

m2 = multiplyMatrixWithStrassenAlgorithm(a21 + a22, b11)

m3 = multiplyMatrixWithStrassenAlgorithm(a11, b12 - b22)

m4 = multiplyMatrixWithStrassenAlgorithm(a22, b21 - b11)

m5 = multiplyMatrixWithStrassenAlgorithm(a11 + a12, b22)

m6 = multiplyMatrixWithStrassenAlgorithm(a21 - a11, b11 + b12)

m7 = multiplyMatrixWithStrassenAlgorithm(a12 - a22, b21 + b22)

c11 = m1 + m4 - m5 + m7

c12 = m3 + m5

c21 = m2 + m4

c22 = m1 - m2 + m3 + m6

return np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))

sourcMatrix1 = np.array(

[

[1 , 2 , 3 , 4 ],

[5 , 6 , 7 , 8 ],

[9 , 10, 11, 12],

[13, 14, 15, 16]

]

)

sourceMatrix2 = np.array(

[

[17, 18, 19, 20],

[21, 22, 23, 24],

[25, 26, 27, 28],

[29, 30, 31, 32]

]

)

targetMatrix = multiplyMatrixWithStrassenAlgorithm(sourcMatrix1, sourceMatrix2)

print(targetMatrix)

"""

[[ 250 260 270 280]

[ 618 644 670 696]

[ 986 1028 1070 1112]

[1354 1412 1470 1528]]

"""

▶ requirements.txt


numpy==2.0.0

numpy==2.0.0

※ pip install numpy

[PYTHON/COMMON] 그래프에서 다익스트라 알고리즘(Dijkstra Algorithm) 최단 경로 구하기

■ 그래프에서 다익스트라 알고리즘(Dijkstra Algorithm)을 사용해 최단 경로를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import heapq
import sys

def getDijkstraShortestPathDictionary(graphDictionaryDictionary, startNode):
    distanceDictionary = {node : sys.maxsize for node in graphDictionaryDictionary}

    distanceDictionary[startNode] = 0

    queueList = []

    heapq.heappush(queueList, (distanceDictionary[startNode], startNode))

    while queueList:
        currentDistance, node = heapq.heappop(queueList)

        if distanceDictionary[node] < currentDistance:
            continue

        for adjacentNode, distance in graphDictionaryDictionary[node].items():
            weightedDistance = currentDistance + distance

            if weightedDistance < distanceDictionary[adjacentNode]:
                distanceDictionary[adjacentNode] = weightedDistance

                heapq.heappush(queueList, (weightedDistance, adjacentNode))

    return distanceDictionary

graphDictionaryDictionary = {
    "A" : {"B" : 10, "C" : 3         },
    "B" : {"C" :  1, "D" : 2         },
    "C" : {"B" :  4, "D" : 8, "E" : 2},
    "D" : {"E" :  7                  },
    "E" : {"D" :  9                  }
}

shortestPathDictionary = getDijkstraShortestPathDictionary(graphDictionaryDictionary, "B")

print(shortestPathDictionary)

"""
{'A': 9223372036854775807, 'B': 0, 'C': 1, 'D': 2, 'E': 3}
"""

import heapq

import sys

def getDijkstraShortestPathDictionary(graphDictionaryDictionary, startNode):

distanceDictionary = {node : sys.maxsize for node in graphDictionaryDictionary}

distanceDictionary[startNode] = 0

queueList = []

heapq.heappush(queueList, (distanceDictionary[startNode], startNode))

while queueList:

currentDistance, node = heapq.heappop(queueList)

if distanceDictionary[node] < currentDistance:

continue

for adjacentNode, distance in graphDictionaryDictionary[node].items():

weightedDistance = currentDistance + distance

if weightedDistance < distanceDictionary[adjacentNode]:

distanceDictionary[adjacentNode] = weightedDistance

heapq.heappush(queueList, (weightedDistance, adjacentNode))

return distanceDictionary

graphDictionaryDictionary = {

"A" : {"B" : 10, "C" : 3 },

"B" : {"C" : 1, "D" : 2 },

"C" : {"B" : 4, "D" : 8, "E" : 2},

"D" : {"E" : 7 },

"E" : {"D" : 9 }

}

shortestPathDictionary = getDijkstraShortestPathDictionary(graphDictionaryDictionary, "B")

print(shortestPathDictionary)

"""

{'A': 9223372036854775807, 'B': 0, 'C': 1, 'D': 2, 'E': 3}

"""

[PYTHON/COMMON] 그래프에서 너비 우선 탐색(Breadth-First Search) 최단 경로 구하기 (노드간 가중치 포함)

■ 그래프에서 너비 우선 탐색(Breadth-First Search)을 사용해 노드간 가중치 포함해 최단 경로를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from collections import deque

def getBreadthFirstSearchShortestPathTuple(graphDictionary, startNode, distanceDictionary):
    visitedNodeList   = [startNode]
    adjacentNodeDeque = deque([startNode])

    while adjacentNodeDeque:
        node = adjacentNodeDeque.popleft()
        for adjacentNode in graphDictionary[node]:
            if adjacentNode not in visitedNodeList:
                visitedNodeList.append(adjacentNode)
                adjacentNodeDeque.append(adjacentNode)
                distanceDictionary[adjacentNode] = distanceDictionary[node] + 1

    return visitedNodeList, distanceDictionary

graphDictionary = {
    "A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.
    "B" : ["A", "E", "C"],
    "C" : ["B", "E", "D"],
    "D" : ["C", "G", "H"],
    "E" : ["B", "C", "G"],
    "F" : ["A", "G"     ],
    "G" : ["E", "F", "D"],
    "H" : ["D"          ],
    "I" : ["A"          ]
}

distanceDictionary = dict.fromkeys(graphDictionary.keys(), 0)

shortestPathTuple = getBreadthFirstSearchShortestPathTuple(graphDictionary, "B", distanceDictionary)

print(shortestPathTuple)

"""
(
    ['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'],                                    # B 노드에서 제일 가까운 노드 순서로 나열된다.
    {'A' : 1, 'B' : 0, 'C' : 1, 'D' : 2, 'E' : 1, 'F' : 2, 'G' : 2, 'H' : 3, 'I' : 2} # B 노드에서 각 노드의 가중치를 나타낸다.
)
"""

from collections import deque

def getBreadthFirstSearchShortestPathTuple(graphDictionary, startNode, distanceDictionary):

visitedNodeList = [startNode]

adjacentNodeDeque = deque([startNode])

while adjacentNodeDeque:

node = adjacentNodeDeque.popleft()

for adjacentNode in graphDictionary[node]:

if adjacentNode not in visitedNodeList:

visitedNodeList.append(adjacentNode)

adjacentNodeDeque.append(adjacentNode)

distanceDictionary[adjacentNode] = distanceDictionary[node] + 1

return visitedNodeList, distanceDictionary

graphDictionary = {

"A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.

"B" : ["A", "E", "C"],

"C" : ["B", "E", "D"],

"D" : ["C", "G", "H"],

"E" : ["B", "C", "G"],

"F" : ["A", "G" ],

"G" : ["E", "F", "D"],

"H" : ["D" ],

"I" : ["A" ]

}

distanceDictionary = dict.fromkeys(graphDictionary.keys(), 0)

shortestPathTuple = getBreadthFirstSearchShortestPathTuple(graphDictionary, "B", distanceDictionary)

print(shortestPathTuple)

"""

(

['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'], # B 노드에서 제일 가까운 노드 순서로 나열된다.

{'A' : 1, 'B' : 0, 'C' : 1, 'D' : 2, 'E' : 1, 'F' : 2, 'G' : 2, 'H' : 3, 'I' : 2} # B 노드에서 각 노드의 가중치를 나타낸다.

)

"""

[PYTHON/COMMON] 그래프에서 너비 우선 탐색(Breadth-First Search) 최단 경로 구하기

■ 그래프에서 너비 우선 탐색(Breadth-First Search)을 사용해 최단 경로를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from collections import deque

def getBreadthFirstSearchShortestPathList(graphDictionary, startNode):
    visitedNodeList   = []
    adjacentNodeDeque = deque([startNode])

    while adjacentNodeDeque:
        node = adjacentNodeDeque.popleft()
        if node not in visitedNodeList:
            visitedNodeList.append(node)
            adjacentNodeDeque.extend(graphDictionary[node])

    return visitedNodeList

graphDictionary = {
    "A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.
    "B" : ["A", "E", "C"],
    "C" : ["B", "E", "D"],
    "D" : ["C", "G", "H"],
    "E" : ["B", "C", "G"],
    "F" : ["A", "G"     ],
    "G" : ["E", "F", "D"],
    "H" : ["D"          ],
    "I" : ["A"          ]
}

shortestPathList = getBreadthFirstSearchShortestPathList(graphDictionary, "B")

print(shortestPathList)

"""
['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'] # B 노드에서 제일 가까운 노드 순서로 나열된다.
"""

from collections import deque

def getBreadthFirstSearchShortestPathList(graphDictionary, startNode):

visitedNodeList = []

adjacentNodeDeque = deque([startNode])

while adjacentNodeDeque:

node = adjacentNodeDeque.popleft()

if node not in visitedNodeList:

visitedNodeList.append(node)

adjacentNodeDeque.extend(graphDictionary[node])

return visitedNodeList

graphDictionary = {

"A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.

"B" : ["A", "E", "C"],

"C" : ["B", "E", "D"],

"D" : ["C", "G", "H"],

"E" : ["B", "C", "G"],

"F" : ["A", "G" ],

"G" : ["E", "F", "D"],

"H" : ["D" ],

"I" : ["A" ]

}

shortestPathList = getBreadthFirstSearchShortestPathList(graphDictionary, "B")

print(shortestPathList)

"""

['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'] # B 노드에서 제일 가까운 노드 순서로 나열된다.

"""

[PYTHON/COMMON] 그래프에서 깊이 우선 탐색(Depth-First Search) 최단 경로 구하기

■ 그래프에서 깊이 우선 탐색(Depth-First Search)을 사용해 최단 경로를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


def getDepthFirstSearchShotestPathList(graphDictionary, startNode):
    visitedNodeList  = []
    adjacentNodeList = [startNode]

    while adjacentNodeList:
        node = adjacentNodeList.pop()
        if node not in visitedNodeList:
            visitedNodeList.append(node)
            adjacentNodeList.extend(graphDictionary[node])

    return visitedNodeList

graphDictionary = {
    "A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.
    "B" : ["A", "C", "E"],
    "C" : ["B", "D", "E"],
    "D" : ["C", "G", "H"],
    "E" : ["B", "C", "G"],
    "F" : ["A", "G"     ],
    "G" : ["D", "E", "F"],
    "H" : ["D"          ],
    "I" : ["A"          ]
}

shortestPathList = getDepthFirstSearchShotestPathList(graphDictionary, "B")

print(shortestPathList)

"""
['B', 'E', 'G', 'F', 'A', 'I', 'D', 'H', 'C'] # B 노드에서 제일 가까운 노드 순서로 나열된다.
"""

def getDepthFirstSearchShotestPathList(graphDictionary, startNode):

visitedNodeList = []

adjacentNodeList = [startNode]

while adjacentNodeList:

node = adjacentNodeList.pop()

if node not in visitedNodeList:

visitedNodeList.append(node)

adjacentNodeList.extend(graphDictionary[node])

return visitedNodeList

graphDictionary = {

"A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다.

"B" : ["A", "C", "E"],

"C" : ["B", "D", "E"],

"D" : ["C", "G", "H"],

"E" : ["B", "C", "G"],

"F" : ["A", "G" ],

"G" : ["D", "E", "F"],

"H" : ["D" ],

"I" : ["A" ]

}

shortestPathList = getDepthFirstSearchShotestPathList(graphDictionary, "B")

print(shortestPathList)

"""

['B', 'E', 'G', 'F', 'A', 'I', 'D', 'H', 'C'] # B 노드에서 제일 가까운 노드 순서로 나열된다.

"""

[PYTHON/COMMON] 그래프에서 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 최단 경로 구하기

■ 그래프에서 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)을 최단 경로를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import sys

def getFloydWarshallShortestPathListList(nodeCount, adjacentListList):
    distanceListList = [[sys.maxsize] * nodeCount for _ in range(nodeCount)]

    for y, x, edge in adjacentListList:
        distanceListList[y - 1][x - 1] = edge

    for k in range(nodeCount):
        distanceListList[k][k] = 0
        for y in range(nodeCount):
            for x in range(nodeCount):
                distanceListList[y][x] = min(distanceListList[y][x], distanceListList[y][k] + distanceListList[k][x])

    return distanceListList

nodeCount        = 4                                                         # 노드 수
adjacentListList = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]] # [1, 3, -2]는 node1에서 node3까지 edge가 -2이다.

shortestPathListList = getFloydWarshallShortestPathListList(nodeCount, adjacentListList)

print(shortestPathListList)

"""
[[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]]

=================================
       node1  node2  node3  node4
=====  =====  =====  =====  =====
node1      0     -1     -2      0
node2      4      0      2      4
node3      5      1      0      2
node4      3     -1      1      0
=================================
"""

import sys

def getFloydWarshallShortestPathListList(nodeCount, adjacentListList):

distanceListList = [[sys.maxsize] * nodeCount for _ in range(nodeCount)]

for y, x, edge in adjacentListList:

distanceListList[y - 1][x - 1] = edge

for k in range(nodeCount):

distanceListList[k][k] = 0

for y in range(nodeCount):

for x in range(nodeCount):

distanceListList[y][x] = min(distanceListList[y][x], distanceListList[y][k] + distanceListList[k][x])

return distanceListList

nodeCount = 4 # 노드 수

adjacentListList = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]] # [1, 3, -2]는 node1에서 node3까지 edge가 -2이다.

shortestPathListList = getFloydWarshallShortestPathListList(nodeCount, adjacentListList)

print(shortestPathListList)

"""

[[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]]

=================================

node1 node2 node3 node4

===== ===== ===== ===== =====

node1 0 -1 -2 0

node2 4 0 2 4

node3 5 1 0 2

node4 3 -1 1 0

=================================

"""

[PYTHON/COMMON] inf 변수 : float 타입의 양/음 무한대 값 구하기

■ inf 변수를 사용해 float 타입의 양/음 무한대 값을 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import math

positiveInfiniteFloatValue =  math.inf
negativeInfiniteFloatValue = -math.inf

print(positiveInfiniteFloatValue)
print(negativeInfiniteFloatValue)

"""
inf
-inf
"""

import math

positiveInfiniteFloatValue = math.inf

negativeInfiniteFloatValue = -math.inf

print(positiveInfiniteFloatValue)

print(negativeInfiniteFloatValue)

"""

inf

-inf

"""

[PYTHON/COMMON] float 클래스 : 생성자를 사용해 양/음 무한대 값 구하기

■ float 클래스의 생성자를 사용해 양/음 무한대 값을 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import math

positiveInfiniteFloatValue  =  float('inf' )
negativeInfiniteFloatValue1 =  float('-inf')
negativeInfiniteFloatValue2 = -float('inf' )

print(positiveInfiniteFloatValue )
print(negativeInfiniteFloatValue1)
print(negativeInfiniteFloatValue2)

"""
inf
-inf
-inf
"""

import math

positiveInfiniteFloatValue = float('inf' )

negativeInfiniteFloatValue1 = float('-inf')

negativeInfiniteFloatValue2 = -float('inf' )

print(positiveInfiniteFloatValue )

print(negativeInfiniteFloatValue1)

print(negativeInfiniteFloatValue2)

"""

inf

-inf

"""

[PYTHON/COMMON] maxsize 변수 : int 타입의 최소/최대값 구하기

■ maxsize 변수를 사용해 int 타입의 최소/최대값을 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import sys

maximumInteger =   sys.maxsize
minimumInteger = -(sys.maxsize + 1)

print(maximumInteger)
print(minimumInteger)

"""
9223372036854775807
-9223372036854775808
"""

import sys

maximumInteger = sys.maxsize

minimumInteger = -(sys.maxsize + 1)

print(maximumInteger)

print(minimumInteger)

"""

9223372036854775807

-9223372036854775808

"""

[PYTHON/COMMON] 소인수 분해(Factorization) 리스트 구하기

■ 소인수 분해(Factorization) 리스트를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import math

def getPrimeNumberList(value):
    isPrimeNumberList = [True] * value
    maximumLength     = math.ceil(math.sqrt(value))
    for i in range(2, maximumLength):
        if isPrimeNumberList[i]:
            for j in range(i + i, value, i):
                isPrimeNumberList[j] = False
    return [i for i in range(2, value) if isPrimeNumberList[i]]

def getFactorizationList(value):
    factorizationList = []
    for primeNumber in getPrimeNumberList(value):
        count = 0
        while value % primeNumber == 0:
            value /= primeNumber
            count += 1
        if count > 0:
            factorizationList.append((primeNumber, count))

    return factorizationList

factorizationList = getFactorizationList(12)

print(factorizationList)

"""
[(2, 2), (3, 1)]
"""

import math

def getPrimeNumberList(value):

isPrimeNumberList = [True] * value

maximumLength = math.ceil(math.sqrt(value))

for i in range(2, maximumLength):

if isPrimeNumberList[i]:

for j in range(i + i, value, i):

isPrimeNumberList[j] = False

return [i for i in range(2, value) if isPrimeNumberList[i]]

def getFactorizationList(value):

factorizationList = []

for primeNumber in getPrimeNumberList(value):

count = 0

while value % primeNumber == 0:

value /= primeNumber

count += 1

if count > 0:

factorizationList.append((primeNumber, count))

return factorizationList

factorizationList = getFactorizationList(12)

print(factorizationList)

"""

[(2, 2), (3, 1)]

"""

[PYTHON/COMMON] 약수 리스트 구하기

■ 약수 리스트를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


import math

def getDivisorList(value):
    divisorList = []
    length = int(math.sqrt(value)) + 1
    for i in range(1, length):
        if value % i == 0:
            divisorList.append(i)
            divisorList.append(value // i)
    divisorList.sort()
    return divisorList

divisorList = getDivisorList(90)

print(divisorList)

"""
[1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]
"""

import math

def getDivisorList(value):

divisorList = []

length = int(math.sqrt(value)) + 1

for i in range(1, length):

if value % i == 0:

divisorList.append(i)

divisorList.append(value // i)

divisorList.sort()

return divisorList

divisorList = getDivisorList(90)

print(divisorList)

"""

[1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]

"""

[PYTHON/COMMON] N개의 수에서 최소 공배수(LCM, Least Common Multiple) 구하기

■ N개의 수에서 최소 공배수(LCM, Least Common Multiple)를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from math import gcd

def lcm(sourceList):
    def __lcm(x, y):
        return x * y // gcd(x, y)

    while True:
        sourceList.append(__lcm(sourceList.pop(), sourceList.pop()))

        if len(sourceList) == 1:
            return sourceList[0]

print(lcm([2, 6, 8, 14])) # 168

from math import gcd

def lcm(sourceList):

def __lcm(x, y):

return x * y // gcd(x, y)

while True:

sourceList.append(__lcm(sourceList.pop(), sourceList.pop()))

if len(sourceList) == 1:

return sourceList[0]

print(lcm([2, 6, 8, 14])) # 168

[PYTHON/COMMON] 최소 공배수(LCM, Least Common Multiple) 구하기

■ 최소 공배수(LCM, Least Common Multiple)를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from math import gcd

def lcm(x, y):
   return x * y // gcd(x, y)

print(lcm(1071, 1029))

"""
52479
"""

from math import gcd

def lcm(x, y):

return x * y // gcd(x, y)

print(lcm(1071, 1029))

"""

52479

"""

[PYTHON/COMMON] product 클래스 : 곱집합(Cartesian product) 리스트 구하기

■ product 클래스를 사용해 곱집합(Cartesian product) 리스트를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from itertools import permutations

sourceList = [1,2,3]

permutations1 = permutations(sourceList, 2)

targetList = list(permutations1)

print(list(targetList))

"""
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
"""

from itertools import permutations

sourceList = [1,2,3]

permutations1 = permutations(sourceList, 2)

targetList = list(permutations1)

print(list(targetList))

"""

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

"""

[PYTHON/COMMON] combinations 클래스 : 조합(combination) 리스트 구하기

■ combinations 클래스를 사용해 조합(combination) 리스트를 구하는 방법을 보여준다. ▶ 예제 코드 (PY)


from itertools import combinations

sourceList = [1,2,3]

combinations1 = combinations(sourceList, 2)

targetList = list(combinations1)

print(list(targetList))

"""
[(1, 2), (1, 3), (2, 3)]
"""

from itertools import combinations

sourceList = [1,2,3]

combinations1 = combinations(sourceList, 2)

targetList = list(combinations1)

print(list(targetList))

"""

[(1, 2), (1, 3), (2, 3)]

"""