Programming/Algorithm31

• 

  [백준] 2178번 미로 탐색 파이썬 해설 출처: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS로 분류된 문제이다. BFS를 풀어본 적이 있다면 해당 문제의 코드를 조금만 변형하면 문제를 풀 수 있을 것이다. 풀이 BFS알고리즘의 기본적인 방법으로 문제에 접근했다. from collections import deque import sys input = sys.stdin.readline find_arr = [(-1, 0), (0, -1), (0, 1), (1, 0)] 먼저 문제의 규칙을 적용할 수 있는 리스트를.. Programming/Algorithm 2019. 9. 26.

• 

  [백준] 1654번 랜선 자르기 파이썬 해설 출처: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색을 사용하면 쉽게 풀 수 있는 문제이다. 이분 탐색의 대표적인 예제인 "나무 자르기" 같은 문제를 풀었다면, 약간의 변화만 줘도 이 문제를 맞힐 수 있을 것이다. 풀이 이진 검색 알고리즘 이라고도 불리는 이분 탐색 .. Programming/Algorithm 2019. 9. 25.

• 

  [백준] 1904번 01타일 파이썬 해설 출처 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net DP문제의 가장 기본적인 "타일" 문제를 정리해보자! DP에 대한 정의는 나름 여기에 정리해두었다. 풀이 문제의 특징을 잘 정리.. Programming/Algorithm 2019. 9. 24.

• 

  [백준] 2579번 계단오르기 파이썬 해설 하루에 적어도 한 문제는 풀고 싶은데, 요즘 너무 바빠서 블로그에 풀이를 남기는 건 일주일에 한 번 꼴로 하게 될 것 같다.. 빨리 취업해서 역량을 펼치고 싶다. DP - Dynamic Programming 백준의 카테고리 중 "분류 별 풀어보기"를 들어가보면 가장 많은 문제를 차지하고 있는 문제 유형이다. 동적 프로그래밍이라는 알고리즘? 풀이방법? 나는 알고리즘이라는 말 보단 풀이 방법이라는 단어가 더 어울리는 것 같다. 정의는 위키백과에 찾아보면 되고, 내가 생각하는 동적 프로그래밍을 재 정의해보면 "재활용"이라고 생각한다. 구현하는 건 어려울게 하나도 없다. 정말 이전의 값을 재활용해서 불필요한 반복을 없애고, 그만큼 시간 복잡도를 줄이도록 구현하면 된다. 문제 풀이를 위한 조건 간단하게 정리 1... Programming/Algorithm 2019. 9. 13.

• 

  [백준] 1197번 최소 스패닝 트리 - Kruskal - union find 오픈 S/W 컨트리뷰톤과 카카오 코딩 테스트를 위해 열심히 알고리즘 공부를 하는 중이다. 한 문제를 풀기 위해 여러 개의 알고리즘을 공부하게 되니 시간이 오래 걸리는 것 같다. 간단하게 코드만 정리하고 다음 공부를 하러 가야겠다. Kruskal과 Union Find - Kruskal 알고리즘 최소 신장 트리(MST)를 만들 때 사용하는 알고리즘의 종류 중 하나다. 노드가 많고 산선이 적을 때 유리하다고 하는데, 최소 신장 트리를 만드는 알고리즘 중에서는 가장 쉽기 때문에 공부를 시작했다. 시간 복잡도는 ​ O(E * logV) 모든 간선을 비용의 오름차순으로 정렬한 다음 간선을 차례대로 선택한다. - Union Find 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재.. Programming/Algorithm 2019. 9. 4.

• 

  [백준] 2042번 구간 합 구하기 파이썬 해설 -세그먼트 트리 알고리즘 공부 혼자 하는 게 생각보다 어렵..지만 꾸준히 해야지! 나는 원래 C언어로 알고리즘 문제를 풀었다. 임베디드 전공이다 보니 전공과목에서 프로그래밍 언어를 C/C++ 만 배웠기 때문이다. 하지만 임베디드를 넘어서 다양한 분야에 만능 프로그래머가 되고 싶어서 파이썬을 시작하게 되었고, 요즈음은 파이썬으로만 문제를 푼다. 쓸데없는 소리를 한 이유는.. 파이썬으로 알고리즘 문제를 풀면 너무 느려서 시간 초과가 너무 자주 뜬다.. 편법으로는 PyPy3로 채점하는 방법이 있는데, 그래도 찝찝하긴 하다.. 나는 이 문제를 세그먼트 트리 알고리즘으로 풀었다. 간단하게 정리해보자 세그먼트 트리 이 문제를 단순하게 배열을 확인하는 알고리즘으로 구현한다면 O(N^2)의 시간 복잡도를 갖게 되어 시간 초과를 면하지.. Programming/Algorithm 2019. 9. 2.

• 

  [백준] 6603번 로또 -Python -조합, 백트래킹 카카오 온라인 코딩 테스트를 준비하기 위해 슬슬 알고리즘 문제들을 풀 때가 왔다. 간단하게 정리만 하고 다음 문제를 풀러 가자 백준 6603번 로또 문제는 여러 가지 알고리즘으로 문제를 풀 수 있다. 파이썬과 조합 함수 (itertools 모듈에 combinations 함수)를 사용하면 정말 쉽게 풀 수 있지만, 백트래킹으로도 풀어보고 싶어서 두 번 풀었다. 조합을 이용한 풀이법 combinations 함수를 호출하면 자동으로 사전 순으로 정렬해주기 때문에 정말 간단하게 풀 수 있는 문제이다. 정답 코드를 첨부하겠다. from itertools import combinations import sys input=sys.stdin.readline while 1: arr = input().split() if .. Programming/Algorithm 2019. 9. 2.