Python

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

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

[백준] 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..

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

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

[알고리즘] 백트래킹(Backtracking)을 알아보자

요즘 백준 문제집을 풀고있는데, 백트래킹 개념의 문제가 나와서 한번 개념을 블로그에 정리해보려고 한다. # 등장 배경 이 글을 읽고있는 분들이라면 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 유명한 완전탐색 알고리즘은 한번쯤 들어본 적이 있을 것이다. 이러한 알고리즘은 모든 가능한 경우의 수를 탐색하는 특징이 있는데, 백트래킹도 이와 비슷한 motivation을 공유한다. 즉, '가능한 모든 방법'을 탐색하는 데에 관심사가 있는 것 ! 하지만 DFS와 BFS는 정말 모든 노드를 탐색한다. 그러다보면 해답이 될 가능성이 없는 그래프의 노드까지 "모두" 탐색하게 되는 것이다. 우리는 알고리즘 문제를 풀고있으므로, 전혀 가능성이 없는 노드는 관심이 없을 것이다. 따라서 백트래킹(Backtracki..

[알고리즘] 특정 기준으로 리스트 정렬하기 (python) - key=lambda

요즘 정렬 문제를 많이 풀다보면, 리스트를 특정 기준으로 정렬해야할 때가 많다. 단순히 .sort(), sorted()로의 오름차순 내림차순으로는 풀 수 없는 문제도 많이 만났고, 이럴때는 key=lambda 함수를 사용하면 된다! 오늘은 이러한 용법에 대해 포스팅 해보도록 하겠다. :) 이 게시글은 여기를 참고하였다. # key=lambda 용법 우선 key=lambda 용법은 sorted 함수의 인자로 쓰인다. 그리고 다음과 같이 사용한다. # key가 하나일 때 모든 정렬의 기반은 오름차순 정렬이다. ex 1) 리스트의 각 원소를 기준으로 정렬하기 (일반 오름차순) 참고로 문자열을 다음과 같이 정렬하면 사전순으로 정렬이 된다. arr = ['abc', 'bac', 'bca'] sorted(arr, ..

[코테] 자주 쓰이는 Python 기본 함수 정리 (계속 업데이트)

블로그 주인이 계속 공부하면서 업데이트 될 예정입니다. 구현 등의 코딩테스트 문제 유형에 기출되었던 기본적인 내장 Python 함수 모음입니다! 자세한 내용은 제 github repo를 참고해주세요 :D 개인 기록용이긴 합니다ㅎㅎ.. GitHub - daeunni/For_codingtest: 다은이의 알고리즘 아카이브 📝🔥 다은이의 알고리즘 아카이브 📝🔥. Contribute to daeunni/For_codingtest development by creating an account on GitHub. github.com ord( ) / chr( ) ord()는 문자열을 아스키코드(숫자)로 반환하는 함수이고, chr()은 아스키코드를 문자열로 반환하는 함수! chr(65) >>> A ord('a') >>..

[백준] 에디터(Python) - Stack

# 문제 # 입출력 # Idea 스택을 이용한 문제다. 이 문제의 특징은 주어진 시간제한이 매우 짧기 때문에, insert와 pop(i) 등을 사용해서는 시간복잡도가 커지기 때문에 사용할 수 없다. (시간초과가 뜬다) 그래서 pop()와 append()만을 이용해 스택으로 구현해야한다. 그렇다면 이 문제를 어떻게 스택으로 구현하느냐? 필자는 처음에 각각의 L, D, B, P 경우를 하나하나 스택으로 구현할 수 있도록 경우를 생각했는데, 이럴 경우에 예외처리가 너무 복잡하고 까다로워져서 난항을 겪었다. 따라서 이 문제의 핵심 아이디어는 커서의 위치를 기준으로 데이터를 두개의 스택으로 나누는 것이다! 처음에는 하나의 스택에 데이터를 모두 몰아넣는다. 그리고 앞서 언급한 pop과 append의 스택 연산을 이..

[TIL] pip, conda로 특정 버전의 패키지 설치하기 (업그레이드, 다운그레이드)

우선 패키지의 버전을 확인하고 싶을 때는 보통 다음과 같이 하면 된다. $ python >>> import numpy >>> numpy.__version__ '1.14.5' pip와 conda로 패키지를 설치하는 것이 다르다는 것은 모두 알고있을 것이다. (pip로 설치한 패키지는 conda로 다운그레이드 해도 버전이 바뀌지 않는다..) 따라서 각각 특정 버전의 패키지를 어떻게 설치하는지 설명하자면 다음과 같다. # pip python -m pip install numpy==x.y.z 참고로 pip에서 특정 패키지의 버전이나 설치여부를 확인하고 싶을 때는 다음과 같이 하면 된다. pip show 패키지 이름 # conda conda install 패키지명=원하는 버전 conda install tensor..