알고리즘/개념

    알고리즘/개념

    [개념 정리] 파이썬 set

    파이썬에서 사용하는 자료구조 set에 대해 알아볼 것이다. 매번 set자료구조를 사용하는 일은 많은데, 효율성 있게 활용해야 하고 기억해두고 싶어서 포스팅 한다. 1. Set파이썬에서 set은 집합 자료형으로 사용된다. 주된 특징으로는 순서를 보장하지 않고, 중복된 원소를 포함하지 않는다. 특징으로 유추하면 set은 해시테이블로 구현되어 있음을 생각해볼 수 있다. 순서를 보장하지 않는다.중복된 원소를 포함하지 않는다.set() 생성자 혹은 {}를 이용해 생성한다.mutable 객체이다.2. 교집합, 합집합, 차집합1) 교집합교집합은 말 그대로 두개의 set에 중복으로 존재하는 원소를 말한다. s1 = set([1, 2, 3, 4, 5])s2 = set([4, 5, 6, 7, 8])# 교집합 메서드 int..

    [개념정리] 파이썬 다중 집합의 교집합, 합집합
    알고리즘/개념

    [개념정리] 파이썬 다중 집합의 교집합, 합집합

    코테 연습할때마다 잊을만 하면 나오는 다중집합이다. 굳이 몰라도 되지만, 모른채 쓰려면 머지소트를 구현해야 하는 굉장한 번거로움이 있기때문에 알아두는게 좋을 것 같아서 포스팅 한다.1. 다중 집합이란?기존에 파이썬에서 집합은 보통 set으로 사용한다. 그리고, set의 특징은 중복된 원소를 허용하지 않는다는 점이 있다.하지만, 중복된 원소를 포함하기 위해 사용되는 개념이 다중집합이고 개념만 다중집합이며 실제로는 리스트에 담아서 나타낸다.a = [1,2,2,3,4,5]b = [1,1,2,3,4,6]일반 집합의 합집합: [1,2,3,4,5,6]일반 집합의 교집합: [1,2,3,4]다중 집합의 합집합: [1,1,2,2,3,4,5,6] 다중 집합의 교집합: [1,2,3,4]이렇게 된다. 나는 처음에 다중 집합의..

    [개념정리] Python 가변객체, 불변객체, 얕은 복사, 깊은 복사
    알고리즘/개념

    [개념정리] Python 가변객체, 불변객체, 얕은 복사, 깊은 복사

    뉴스 클러스터링 문제를 풀다가 어떻게 여기까지 왔는지 모르겠지만... 아무튼 개념을 명확하게 짚고 넘어가야겠다. 일반 파이썬 교재에는 이 개념이 제대로 설명되어있지 않았다. 그래서 전문가를 위한 파이썬 교재를 펼쳤다. 1. 변수는 상자가 아니다. 파이썬의 변수는 모두 객체로 이뤄져 있는데, 이때 이 객체의 개념은 자바에서의 참조 변수와 같다. (보통 객체와 생성된 참조변수의 관계를 붕어빵 틀과 붕어빵으로 설명하는 경우가 있는데, 잘못된 설명인 것 같다.) 그래서 파이썬에서 변수는 다음과 같은 그림으로 표현할 수 있다. 어떤 객체라는 물체에 변수를 붙여서 같은 객체를 가리키게 하는 것이다. 변수는 객체에 붙은 레이블이라고 표현할 수 있다. 실제로, 이 개념을 프로그래밍을 할때 '변수1'이 객체에 할당되었다..

    [개념 정리] Python None 리턴하는 경우 / 재귀함수 None 리턴
    알고리즘/개념

    [개념 정리] Python None 리턴하는 경우 / 재귀함수 None 리턴

    예상 대진표 문제를 풀이하다가 만나게 된 문제, 정확히 알지 못해서 기본적인 개념이지만 정확하게 정리해두려고 한다. 1. 내가 헷갈린점 1) 파이썬 return 안해도 돼! -> 알아서 return 해주는 것 파이썬에서 함수가 return문이 없어도 되고, 없으면 리턴 없이 끝나는 줄 알았다. 알고보니 아니었음 .. 암튼 return문이 없으면 자동으로 return None을 하게 된다. 2) 재귀함수에서 재귀가 종료되는 경우 def dfs(): if 재귀 종료 조건: return cnt dfs() 이러한 함수가 있다고 하면, 나는 이런 트리 동작을 생각했다. 근데 이게 아니라 이거였다. 재귀가 종료되면, 해당 재귀에서 cnt를 리턴하고 해당 함수는 종료된다. 그리고, 해결되지 않은 나머지 함수에서는 자..

    [개념정리] 다익스트라 알고리즘
    알고리즘/개념

    [개념정리] 다익스트라 알고리즘

    최단 경로 문제 중, 하나의 정점에서 다른 모든 정점까지 가는 데에 걸리는 최단 비용을 구하는 알고리즘이다. 다익스트라 알고리즘은 욕심쟁이 알고리즘과 비슷하다. 현재의 정점에서 갈 수 있는 모든 정점을 확인하고, 그중에서 가장 비용이 적은 정점을 선택해 최선의 선택을 하게 된다. 동작 방식은 BFS와 비슷하다. 현재의 정점에서 갈 수 있는 모든 정점을 힙에 넣고, 그중에서 가장 비용이 적은 노드를 선택해 가장 짧은 경로를 업데이트 해나가는 것이다. 다익스트라 알고리즘을 구현하는 자료구조는 우선순위 큐를 사용해도 되지만, 파이썬에서는 대부분 최소힙을 사용한다. (가장 상위노드에 가장 적은 값이 오는 구조) 1. 예시 다음과 같은 그래프가 있을때, A에서 각 정점으로 도달하는 최소비용을 가진 경로를 구하라는..

티스토리툴바