분류 전체보기

[백준] 스타트와 링크(Python) - 백트래킹

# 문제 문제가 복잡해 보일 수 있지만, 사실 아래와 같은 diagonal 하게 대칭인 능력치 행렬이 주어지면, 두 팀의 능력치 차이가 최소가 되도록 팀을 나누고, 그 최소값을 반환하는 문제이다. # 입출력 # Idea 이 문제는 생각보다 이해하기도, 아이디어를 생각하기도 어려웠던 문제다. 그럼에도 불구하고 내가 문제를 풀 때부터 계속 들었던 생각은 능력치 행렬은 대각선 대칭 행렬이라는 것! 이 점을 잘 이용하고 싶었는데, 풀이과정이 잘 생각나지는 않았다. 따라서 이 문제는 아래와 같은 아이디어로 접근하면 된다. 우선 내 가장 큰 고민은 DFS의 노드로 어떤 것을 넣을까였는데, 1부터 N까지 담긴 노드를 그냥 생성하고 이들로 visited 여부를 체크해 팀을 나눈다고 생각하면 편하다. 위 그림에서 노란색..

[PyTorch] torch-sparse, torch-scatter, torch-geometric 패키지 install 하기 + 오류 해결 방법

GNN관련 코드를 보다가 원래 pip install torch-sparse만 해도 예전에는 설치가 잘 되었었는데, 어느 순간부터 이렇게 했더니 패키지 종속관계가 맞지 않는 문제가 발생해 설치가 되지 않았다. 아마 업데이트가 된 모양인데...! 생각보다 설치하는 과정이 까다로워서 블로그에 정리해보려고 한다. torch-geometric과 torch-sparse, torch-scatter 등은 무언가 dependency가 존재하는 패키지인 듯 했다. (나는 torch-sparse와 torch-scatter 패키지만 필요한 상황이었다.) 우선 torch-geometric의 공식 홈페이지인 이 곳에 방문하면, torch가 1.8.0 이상이면 다음과 같이 설치하라고 안내한다. > conda install pyg ..

[알고리즘] 수학 관련 알고리즘 Code - 에라토스테네스의 체, 유클리드 호제법

기초적인 수학적 알고리즘의 코드를 모아놓은 간단한 포스팅이다! 소수를 구하는 알고리즘과 최대공약수를 구하는 알고리즘! 1. 에라토스테네스의 체 소수를 구하는 알고리즘 특정 배수를 지워가는 식으로 전개된다. def era(n): """ Input : 몇까지 탐색할지 Output : n까지 숫자 중 소수를 포함한 리스트 """ a = [False, False] + [True] * (n-1) primes = [] for i in range(2, n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False # 배수를 지운다! return primes 2. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..

[백준] N-Queens 문제(Python) - 백트래킹

# 문제 즉, 상하좌우 대각선으로 이동하는 N개의 퀸을 서로 부딪히지 않도록 배열하는 방법 수를 리턴하는 문제이다. 백트래킹의 전형적인 문제 유형이라고 한다. 아래의 예시처럼 말을 놓는 경우의 수는 하나의 경우의 수가 될 것이다. # 입출력 # Idea 우선 해당 문제는 백트래킹 문제로, DFS 방법으로 문제를 푸는 방법을 고안할 수 있다. (백트래킹에 대해 궁금하신 분들은 여기를 참고!) 특히 이 문제를 처음 봤을 때, 나는 다음과 같이 DFS노드를 뻗으면 어떨지 생각을 했다. 각 raw별 좌표를 노드로 놓고, Depth는 raw 단위가 되도록 노드를 뻗는 것이다. 특히 백트래킹은 유망한 노드(정답이 될 가능성이 있는 노드)이면 계속 DFS 탐색을 하고, 그렇지 않으면 탐색을 멈추고 위 depth의 노..

[CV] Adversarial Learning(적대적 학습)이란? + 응용

오늘은 PointAugment paper를 읽다가 main 원리로 나온 Adversarial learning에 대해 포스팅해보려고 한다. 주로 적대적 학습이라고 하는데, 그냥 내가 이해한 내용을 간단히 정리해보려고 한다. (미팅준비로 인해... 자세한 포스팅은... 미뤄두겠다.) # Idea 우선 적대적 학습에서, 적대적(adversarial)이란 '서로 대립관계에 있는' 이라는 뜻이다. 흔히 들어봤을 GAN의 속 의미가 Generative adversarial networks 인데, 여기 들어가는 adversarial과 비슷한 의미라고 이해할 수 있다. GAN은 흔히 두개의 네트워크가 경쟁하며 학습하는 모델이라고 잘 알려져 있는데, Discriminator를 잘 속이기 위한 데이터를 Generator가..

[백준] 1,2,3 더하기(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제 # 입출력 # Idea 이전 문제처럼 1차원 dfs를 이용하는 문제라고 생각했다. 그 이유는 오직 1, 2, 3으로 이루어진 노드의 그래프를 n depth만큼 뻗으면 되는 1차원 dfs로 접근했기 때문이다. 특히, 오직 매번 depth의 노드가 1,2,3으로 이루어지기 때문에 이전 문제와 달리 visited 체크를 하지 않아도 된다고 생각했다. 이러한 아이디어를 그림으로 구체화하면 다음과 같다. 따라서 만약 위 빨간색 경로의 dfs를 탐색한다면, depth가 깊어질수록 나오는 노드를 점차 cur_sum이라는 변수에 더해서, 만약 cur_sum이 n과 같다면 최종 count를 저장하는 변수에 1을 더하고 재귀함수를 탈출하도록 하면 된다. 그리고 만약 count에 1을 더하고 탈출했다면, 이전 de..

[Linux] 리눅스 mv 명령어 - 폴더 이름 바꾸기, 폴더 이동하기

오늘은 리눅스 명령어 중 mv에 대해 TIL을 적으려고 한다 ㅎㅎ 기능이 크게 두가지라 유용하게 쓰일 것 같다 ! # 폴더 이름 바꾸기 mv를 다음과 같이 사용하면 폴더 이름을 바꿀 수 있다. mv 원본이름 바꿀이름 # 폴더 이동하기 사실 mv는 원래 폴더를 특정 장소로 이동시키는 명령어이다. 따라서 다음과 같이 편리하게 사용하면 된다. mv 원본위치 이동할위치 위 두 작업을 동시에 하면 폴더 이름도 바꾸면서, 폴더를 이동할 수 있다!

[백준] 로또(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제 단순히 combination을 구하는 것 같은 아주 간단한 문제이지만, 사실 dfs로 풀어야 진가를 볼 수 있는 문제이기도 했다! # 입출력 K가 집합 S에 포함되는 수의 개수인데 생각보다 6에서 13 사이이면 작은 범위라고 생각했다. 그래서 처음으로 itertools 모듈을 고려하게 된 것 같다. # Idea 처음에는 앞서 언급한대로 from itertools import combinations 을 사용했다. 범위가 작게 주어졌다고 생각했기 때문이다. 이런 방식으로 구한 답도 맞았지만, 이 문제는 백트래킹 단원의 문제인 만큼 dfs로 접근하는 것이 중요한 문제였던 것 같다. 사실 이제 dfs는 좀 익숙한 상태였는데, 모두 2차원 그래프를 대상으로 한 dfs 문제를 풀이했었다. 그래서 이 문제는..