프로그래밍/자료구조 & 알고리즘

    NQueen 문제 파이썬과 자바스크립트 풀이
    프로그래밍/자료구조 & 알고리즘

    NQueen 문제 파이썬과 자바스크립트 풀이

    백준 9663번 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 구상 N*N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치해야한다. 퀸의 움직임은 직선방향, 대각선방향이다. 그렇다면 생각나는 기본적인 로직은 우리는 퀸을 한줄에 하나씩만 배치할 수 있다는 것이다. 우선 배치한다고 생각해보고 하나씩 손으로 배치를 해보자. 두 번째 줄에선는 1,2번째 칸에 퀸을 배치할 수 없다. 두번째 줄에도 배치했으니 이제 세번째로 넘어간다. 세번째줄에 배치가 불가능하다. 따라서 다시 두번째 줄로 돌아가 4번째 칸에 배치한다. (3번..

    백트랙킹 기법 정리
    프로그래밍/자료구조 & 알고리즘

    백트랙킹 기법 정리

    백트랙킹(backtracking)이 무엇인가? 뭐 탐색을 하면서 그냥 필요없는 경로는 손절치고 가지치기하는 알고리즘이다. DFS랑 유사하다 이정도로 대충 알고있었다. 따라서 이번에 공부하면서 정리해보려한다. ✏️ Backtracking 정의는 이렇다. '해를 찾는 도중에 해가 아니어서 막히면 다시 되돌아가서 다시 해를 찾는 기법.' 이걸 가지치기(pruning)이라고 하는데 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 구현방식? DFS등으로 모든 경우의수를 탐색하는 과정에서 조건문등으로 답이 절대 될 수 없는 상황을 정의하고 그런 상황에서는 탐색을 중지시키고 다시 처음으로 가서 다른 경우를 탐색하게끔 구현할 수 있다. 트리에 대해서 DFS 실시 각 노드가 유망한지(promising) 점검 해당 ..

    프로그래밍/자료구조 & 알고리즘

    DFS와 BFS 각각 사용하는 경우

    ✏️ DFS와 BFS의 구현방법과 차이 설명 아래글에 설명해두었으니 이 내용은 여기서 확인바란다. 백준 1260: DFS와 BFS 해설- python ✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에.. duckracoon.tistory.com ✏️ DFS와 BFS 각각 어떤 상황에서 사용할까? 어떤 문제를 풀때 DFS를 써야할지, 어떤 문제를 풀때 BFS를 쓸지 난감한 경험때문에 정리한다. When is it practical to use Depth-First Search (DFS) vs..

    파이썬 collections deque 사용법과 응용
    프로그래밍/자료구조 & 알고리즘

    파이썬 collections deque 사용법과 응용

    ✏️ deque Stack이나 queue처럼 한 방향에서 삽입과 삭제가 일어나는게 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다. 파이썬에서 list를 사용하는 것과 유사하지만 deque를 사용하는 이유는 시간복잡도 때문이다. 리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 끝이 아니라 뒤에있는 원소들을 앞으로 하나씩 당겨주는 연산을 더 수행하게된다. 따라서 list의 삭제연산은 O(n)이 걸리는데 반면 deque의 삭제연산은 O(1)이다. 따라서 push, pop이 빈번한 알고리즘의 경우 list보다 deque를 사용하는 것이 효율적이다. ✏️ collections.deque 1. collections.deque.append(x) : deque의 맨..

    프로그래밍/자료구조 & 알고리즘

    파이썬 heapq 모듈 사용법과 응용

    ✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으로써 일반 리스트를 마치 최소 힙처럼 다룰수 있게 된다. 그냥 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘겨서 사용하면된다. 즉 heapq모듈을 통해서 원소를 추가하고 삭제하면 그 리스트는 최소힙이 된다. heap=[] ✏️ 최소힙 원소추가 heappush(), 첫번째 인자는 원소를 추가할 대상 리스트, 두번째 인자는 추가할 원소 시간복잡도: O(logN) heapq.heappush(heap, 4) heapq.heappush(heap, 1) heap..

    그리디 알고리즘 개념정리와 문제
    프로그래밍/자료구조 & 알고리즘

    그리디 알고리즘 개념정리와 문제

    ✏️ 그리디 알고리즘 간단하게 이야기하면 뒷 일은 생각안하고 당장에 눈 앞에 있는 것중에 가장 좋은 것만을 택하는 알고리즘이라고 볼 수 있다. 시작점부터 시작해서 가장 큰수를 얻어야하는 문제가 있다. 여기서 노란색 화살표로 표현된 것이 그리디 알고리즘, 주황색 화살표로 표현한 것이 최적해이다. 처음에 10을 거쳐야 가장 큰 수인 500을 얻을 수 있지만 그리디 알고리즘은 당장에 가장 큰 수인 15를 먼저 선택했기떄문에 20을 출력하게 된다. 그리디(Greedy)알고리즘은 이처럼 최적해를 보장해주지 않는다. ✏️ 그리디 알고리즘의 사용조건 첫째. 그리디 알고리즘은 최적해를 보장해주지 않는다고 했다. 즉, 그리디 알고리즘을 이용했을때 최적해가 나오는 문제에 그리디알고리즘을 이용할 수 있다. 이를 만족시킬 조..

    [알고리즘] Lower Bound와 Upper Bound
    프로그래밍/자료구조 & 알고리즘

    [알고리즘] Lower Bound와 Upper Bound

    ✏️ 무엇인가? Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값이 나오는 마지막 위치를 찾는 과정'이다. Array = [1, 1, 2, 2, 3, 4, 4, 4, 6] 이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다. ✏️ 구현과정의 고민 사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나..

    Binary Search (이진탐색) 알고리즘
    프로그래밍/자료구조 & 알고리즘

    Binary Search (이진탐색) 알고리즘

    ✏️ 이진탐색알고리즘의 작동방식 이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다. 분할(Devide) 리스트를 중간값을 기준으로 두개의 리스트로 분할한다. 정복(Conquer) - 검색할 숫자 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다. - 검색할 숫자 == 중간값 이면 값을 리턴한다. ✏️ 이진탐색알고리즘 구현 (Python) 재귀적 구현 def BS(array, target, start, end): if start>end: return None mid=(start+end)//2 if array[mid]==target: return mid elif array[mid]>target: return B..

    [Python & Algorithm] Dynamic Programming(동적프로그래밍)
    프로그래밍/자료구조 & 알고리즘

    [Python & Algorithm] Dynamic Programming(동적프로그래밍)

    ✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..

    [Python & Data Structure] Graph
    프로그래밍/자료구조 & 알고리즘

    [Python & Data Structure] Graph

    ✏️ Graph (그래프의 개념) 연결되어 있는 객체간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태이며, Tree 도 그래프의 특수한 경우이다. 하나의 점을 Vertex 라고 한다. 하나의 선을 Edge 라고 한다. Link 라고도 함. ✏️ Graph (용어) 비가중치 그래프 / 가중치 그래프 : 비가중치 그래프는 각 vertex 간의 연결 유무만을 판단한다. 가중치 그래프는 각 간선(edge)에 가중치를 부여한 형태로 예를 들면 edge에 비용을 부과하는 형식으로 가중치가 부과될 수 있다. 위의 그림은 가중치 그래프이다. 무향(undirected) 그래프 / 유향(directed) 그래프 : 무향 edge는 양방향의 의미를 가진다. (A,B)=(B,A) 로 순서에 의미를 가지지 않..

티스토리툴바