티스토리

JooTopia's Blog

검색하기

블로그 홈

JooTopia's Blog

sungmin-joo.tistory.com/m

Develop with complexity for simple development.

구독자: 5

방명록 방문하기

주요 글 목록

[백준] 2252번 줄 세우기 파이썬 해설 출처 : https://www.acmicpc.net/problem/2252 입사 후 교육을 받는 기간이라 주말에 간간히 한 두 문제 정도 풀 수 있다..ㅜ 심지어 회사와 관련된 내용과 지식은 보안상 조심해야 한다고 하기 때문에 퇴사 전 까지는 알고리즘 문제 풀이 정도나 올릴 것 같다. 오늘은 동기들을 통해 추천받은 "위상 정렬" 알고리즘 문제를 풀어봤다. 정답률도 높고, 정답의 범위도 넓기 때문에 푸는데 조금 수월했던 것 같다. 풀이 위상정렬의 개념에 대해서 공부하기 좋은 기본 문제라고 생각한다. a, b를 입력받을 때 a가 b를 참조한다고 생각하고, 참조 횟수가 0인 정점부터 위상 정렬을 수행하면 쉽게 문제를 풀 수 있다. 다만 참조 횟수가 0인 정점에 대해 정렬을 수행하고 나서 해당 정점이 참조하던 .. 공감수 1 댓글수 0 2020. 1. 19.
[백준] 4949번 균형잡힌 세상 파이썬 해설 출처 : https://www.acmicpc.net/problem/4949 입사 후 교육을 받는 기간이라 주말에 간간히 한 두 문제 정도 풀 수 있다..ㅜ 심지어 회사와 관련된 내용과 지식은 보안상 조심해야 한다고 하기 때문에 퇴사 전 까지는 알고리즘 문제 풀이 정도나 올릴 것 같다. 오늘은 오랜만에 알고리즘 문제를 풀었기 때문에 다소 쉬운 문제를 선택했다. 문자열을 다루는 문제이며 괄호 찾기와 매우 유사한 문제이기 때문에 자료구조 stack을 이용하면 쉽게 풀 수 있다. 풀이 문제를 정독하고 간단하게 알고리즘을 설계한 뒤 그대로 코드로 구현하였다. 1. 입력을 받는다. 2. 좌측 괄호('(', '[')인지 검사한다. 만약 좌측 괄호라면 스택에 넣어준다. 3. 우측 괄호인지(')', ']') 검사한다. .. 공감수 0 댓글수 2 2020. 1. 5.
[백준] 1713번 후보 추천하기 파이썬 해설 출처 : https://www.acmicpc.net/problem/1713 코딩 테스트 문제에서 자주 출현하는 구현 알고리즘이다. 보통 1, 2번 문제에 출제되고 긴장하면 말리기 쉬운 문제 유형이니 많이 풀어서 익숙해지는 게 중요한 것 같다. 풀이 보통 구현 문제는 여러가지 조건을 그대로 구현하면 정답을 맞힐 수 있는 구조로 많이 출제된다. 성급하게 접근하기 보단 문제의 조건을 읽어보고 정리한 뒤에 알고리즘을 설계하는 것을 추천한다. 문제의 조건은 다음과 같다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 .. 공감수 0 댓글수 0 2019. 12. 18.
[백준] 7576번 토마토 파이썬 해설 (BFS) 출처 : https://www.acmicpc.net/problem/7576 BFS 알고리즘으로 분류된 문제이다. 코딩 테스트를 통과하기 위해 알고리즘 문제를 많이 풀던 시기에 가장 취약했던 알고리즘의 종류 중 하나이다. 한 번의 시도만에 취업을 성공해서 당분간 코딩 테스트는 치르지 않지만, 약점을 보완하기 위해 내가 약했던 알고리즘을 위주로 문제를 다시 풀어보고 있다. 풀이 처음 이 문제를 접근할 때는 하루가 지날 때 마다 배열의 모든 점을 탐색하는 알고리즘을 설계하고 그대로 구현하였다. 나름 예외처리를 했다고 생각했지만 M과 N이 증가 할 수록 시간 복잡도가 기하급수적으로 늘어났고 결국 시간 초과라는 결과를 받았다. ㅜㅜ 그 후에 파이썬의 dequeue 모듈을 사용해서 좀더 효율적인 알고리즘을 새로 설.. 공감수 0 댓글수 0 2019. 12. 15.
[백준] 1541번 잃어버린 괄호 Python 해설 (그리디 알고리즘) 출처 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 그리디 알고리즘으로 분류된 문제이다. 코딩 테스트나 알고리즘 경진대회에서 해당 알고리즘이 나온다면 확실하게 점수를 가져가야 한다!! 그리 어렵지 않은 알고리즘이니 쉽게 문제를 풀어보자 풀이 여기에 그리디 알고리즘에 대해서 언급한 적이 있다. 간단하게 가장 좋은 선택을 알고리즘이라고 생각한다. "잃어버린 괄호" 문제는 가장 최.. 공감수 5 댓글수 1 2019. 12. 8.
[백준] 2661번 좋은수열 Python 해설 (백트래킹 알고리즘) 출처 : https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 알고리즘으로 분류된 문제이다. 코딩 테스트를 몇 차례 보면서 탐색, 백트래킹 쪽 문제에 약하다는 걸 알고 관련 문제를 많이 풀어보려고 하는 중이다. 풀이 입력받은 자릿수만큼의 길이가 될 때까지 깊이 우선 탐색을 진행하게 된다. 깊이 우선 탐색만 예를 들면 n = 7일 경우 첫 결과는 1111111이 된다. (최솟값 우선 조건 적용) 하지만 백트래킹 알고리즘을 적용하여 깊이 우선 탐색에 조건을.. 공감수 3 댓글수 0 2019. 12. 7.
[백준] 1717번 집합의 표현 Python 해설 출처 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net Disjoint-set 알고리즘으로 분류된 문제이다. N사에 떨어졌다고 생각하고 K사 채용연계형 인턴 정형의 코딩 테스트를 .. 공감수 0 댓글수 0 2019. 11. 24.
[백준] 11003번 최솟값 찾기 Python 해설 출처 : https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우 알고리즘으로 분류된 문제이다. 열몇 번의 시도만에 풀었다.. 풀이 - Python 정답 코드 from collections import deque n, l = map(int, input().split()) arr = [*map(int, input().split())] m = deque() for i in range(n): tmp = arr[.. 공감수 2 댓글수 0 2019. 11. 18.
[백준] 10868번 최솟값 Python 해설 출처 : https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 www.acmicpc.net 세그먼트 트리에 입문하기 위해 딱 좋은 문제라고 생각한다. 풀이 - Python 정답 코드 import sys from mat.. 공감수 0 댓글수 0 2019. 11. 18.
[백준] 4673번 셀프 넘버 C, Python 해설 에라토스테네스의 체 알고리즘으로 분류된 문제이다. 하지만 C언어로 푼 다면 단순하게 자신만의 알고리즘으로도 풀이가 가능하다. 풀이 문제에서 정의한 셀프 넘버는 생성자가 없는 숫자를 뜻한다. 문제에서 제공된 함수 d(n)을 구현하고, 1부터 10000까지 반복하여 생성자가 존재하는 숫자에 대해서는 미리 체크한 뒤 체크되지 않은 수만 출력하는 알고리즘으로 문제에 접근하였다. - C 정답 코드 #include int self_num(int num) { int sum = num; while (num != 0) { sum += num % 10; num /= 10; } return sum; } int main() { int i = 1, tmp; char arr[10001] = { 0, }; for (; i < 10.. 공감수 0 댓글수 0 2019. 10. 29.
[백준] 17618번 신기한 수 파이썬 해설 (Python) 출처 : https://www.acmicpc.net/problem/17618 17618번: 신기한 수 평소에 수에 대한 관심이 많은 아이인 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나눠보면서 시간을 보내고 있다. 그러다가 18이라는 수는 신기한 성질을 가진다는 것을 알아냈다. 18을 이루는 각 자릿수인 1과 8을 합한 9는 18의 약수가 된다. 민철이는 18과 같이 모든 자릿수의 합으로 나누어지는 수를 여러 개 더 찾아냈는데, 12, 21도 그런 신기한 수였다. 민철이는 이렇게 모든 자릿수의 합으로 나누어지는 수를 “신기한 수”라고 부 www.acmicpc.net 따로 알고리즘이 분류되지 않은 문제이다. 수학으로 분류될 수 있을 것 같다. 풀이 파이썬이 아니면 아주 간단하게 풀 수 있.. 공감수 0 댓글수 0 2019. 10. 28.
[백준] 1652번 누울 자리를 찾아라 파이썬 해설 (Python) 출처 : https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 수학 알고리즘 문제로 분류된 문제이다. 문제를 잘못 이해해서 한 번에 맞추지 못했던 문제여서 억울함이 가득한 문제이다. 해설을 보기 전에 문제를 다시 한번 정독한 뒤 다시 풀어보는 것을 추천한다! 풀이 문제에 그림이 나오고 입력이 특이하다고 겁먹지 말고 문제를 천천히 읽어보면 그리 어렵지 않은 문제라는 것을 알 수 있다. 문제에서 원하는 출력인 "가로로 누울 수 있는 자리"와 ".. 공감수 0 댓글수 0 2019. 10. 26.
[백준] 11403번 경로 찾기 파이썬 해설 (Python) 출처 : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net BFS와 DFS 혹은 플로이드 와샬 알고리즘으로 분류된 문제이다. BFS : Breadth-first search DFS : Depth-first search 플로이드 와샬 알고리즘은 시간 복잡도가 O(n^3)이기 때문에 위 두 가지 방법으로 푸는 것을 추천한다. 풀이 이전에 BFS 혹은 DFS알고리즘 문제를 푼적이 있다면, 해당 문제에서 사요한 코드를 조금만 변형하면 풀 수 있는 문제이다. 문제를 풀기위해 알고리즘을 설계했던 순.. 공감수 0 댓글수 0 2019. 10. 25.
[백준] 1058번 친구 파이썬 해설 (Python) 출처 : https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다 www.acmicpc.net 그래프 이론 알고리즘으로 분류된 문제이다. 문제를 다 풀고 다른 사람들의 풀이를 참고하며 공부했는데 플로이드 와샬 알고리즘을 사용했.. 공감수 0 댓글수 0 2019. 10. 23.
[백준] 1182번 부분수열의 합 파이썬 해설 출처 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 브루트 포스 알고리즘으로 분류된 문제이다. 완전 탐색 알고리즘이라고도 불리는데, 가능한 모든 경우의 수를 다 따진다는 뜻이다. 문제를 두 가지 방법으로 풀어봤다. 첫 번째는 파이썬 모듈을 사용하여 풀었고, 두 번째는 직접 조합을 만들어서 풀었다. 1. 파이썬 itertools를 사용한 풀이 from itertools import combinations .. 공감수 0 댓글수 2 2019. 10. 21.
[백준] 9465번 스티커 파이썬 해설 출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net dp 알고리즘으로 분류된 문제이다. 점화식을 찾는데 다른 dp 문제보다 시간이 조금 더 걸렸지만, 어려움 없이 잘 풀었다. 풀이 .. 공감수 0 댓글수 0 2019. 10. 18.
[백준] 1507번 궁금한 민호 C 해설 (플로이드 와샬 - reverse) 출처 : https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다. www.acmicpc.net 그리디, 플로이드 와샬 알고리즘으로 분류된 문제이다. 플로이드 와샬 알고리즘으로 분류되어 있길래 당황했지만 신기한 접근으로 풀어나가는 문제여서 천천히 풀어보았다. 당황했던 이유는 이미 모든 노드로 가는 최단경로를 입력으로 주어졌기 때문이었다. 하지만 이 문제는 플로이드 와샬 알고리즘을 역으로 이용하는 문제였다... 공감수 0 댓글수 0 2019. 10. 8.
[백준] 9461번 파도반 수열 C 해설 (다이나믹 프로그래밍) 출처 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 다이나믹 프로그래밍(DP) 알고리즘으로 분류되어있는 문제이다. 이제 DP알고리즘은 정말 잘 푸는 것 같다. 물론 아직 갈 길.. 공감수 0 댓글수 0 2019. 10. 7.
[백준] 4195번 친구 네트워크 파이썬 해설 (디스조인트-셋) 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 여러 가지 알고리즘으로 분류되어있는 문제이다. 디스조인트-셋(Disjoint-set) 알고리즘을 공부하기 위해 해당 알고리.. 공감수 0 댓글수 0 2019. 10. 6.
[백준] 1753번 최단경로 파이썬 해설 (다익스트라 알고리즘) 출처 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 다익스트라 알고리즘으로 분류된 문제이다. 다익스트라 알고리즘은 하나의 정점에서 나머지 모든 정점까지의 최단 거리를 찾는 알고리즘이.. 공감수 8 댓글수 4 2019. 10. 4.
[백준] 3985번 롤 케이크 파이썬 해설 출처 : https://www.acmicpc.net/problem/3985 3985번: 롤 케이크 문제 인기 티비 프로그램 "나는 요리사 인가?"의 새 시즌이 시작한다. 이번 시즌은 기네스북에 등재될 만한 음식을 만드는 것을 목표로 진행한다. 첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 L미터의 롤 케이크를 만들 것이다. 상근은 몇 시간동안 집중해서 케이크를 만들었고, 이제 스튜디오의 방청객 N명에게 케이크를 나누어 주려고 한다. 상근이는 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다. 가장 왼쪽 조각이 1번, 오른쪽 조각이 www.acmicpc.net 시뮬레이션으로 알고리즘으로 분류된 문제이다. 개인적으로 시뮬레이션 문제가 익숙하지 않아서 많이 풀어보려고 하는 중이다. 그냥 한.. 공감수 0 댓글수 0 2019. 10. 3.
[백준] 14409번 주사위 굴리기 파이썬 해설 출처 : https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 시뮬레이션으로 알고리즘으로 분류된 문제이다. 코딩 테스트를 준비하는 데 있어서 주사위 문제는 필수라고 생각한다. 가장 .. 공감수 0 댓글수 0 2019. 10. 1.
[백준] 14501번 퇴사 파이썬 해설 출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 부루트 포스, 다이나믹 프로그래밍 알고리즘으로 분류된 문제이다. 부루트 포스 알고리즘은 모든 경우를 다 비교해보는 무식한 알고리즘이라고 하는데 사실 다이나믹 프로그래밍과의 차이를 모르겠다. 풀이 나름 부루트 포스 알고리즘의 방향으로 접근해보려 했으나, 정답을 맞히고 보니 다이나믹 프로그래밍 알고리즘을 이용해서 문제를 해결하였다. 정말 무슨 차이인지 모르겠다. 우선 문제를 잘 이해하고 문제 풀이의 흐름을 정했다. N이 주어지면 마지막 N일 부터 최대로 돈을 벌 수 있는 경우를 체크했다. 여기서 주의할 점은 N번째 날은 상담에 .. 공감수 0 댓글수 0 2019. 9. 30.
[백준] 2217번 로프 파이썬 해설 출처: https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net 그리디 알고리즘으로 분류된 문제이다. 그리디 알고리즘의 정의는 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘이.. 공감수 1 댓글수 0 2019. 9. 29.
[백준] 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)] 먼저 문제의 규칙을 적용할 수 있는 리스트를.. 공감수 0 댓글수 0 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 이분 탐색을 사용하면 쉽게 풀 수 있는 문제이다. 이분 탐색의 대표적인 예제인 "나무 자르기" 같은 문제를 풀었다면, 약간의 변화만 줘도 이 문제를 맞힐 수 있을 것이다. 풀이 이진 검색 알고리즘 이라고도 불리는 이분 탐색 .. 공감수 0 댓글수 0 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에 대한 정의는 나름 여기에 정리해두었다. 풀이 문제의 특징을 잘 정리.. 공감수 7 댓글수 1 2019. 9. 24.
[백준] 2579번 계단오르기 파이썬 해설 하루에 적어도 한 문제는 풀고 싶은데, 요즘 너무 바빠서 블로그에 풀이를 남기는 건 일주일에 한 번 꼴로 하게 될 것 같다.. 빨리 취업해서 역량을 펼치고 싶다. DP - Dynamic Programming 백준의 카테고리 중 "분류 별 풀어보기"를 들어가보면 가장 많은 문제를 차지하고 있는 문제 유형이다. 동적 프로그래밍이라는 알고리즘? 풀이방법? 나는 알고리즘이라는 말 보단 풀이 방법이라는 단어가 더 어울리는 것 같다. 정의는 위키백과에 찾아보면 되고, 내가 생각하는 동적 프로그래밍을 재 정의해보면 "재활용"이라고 생각한다. 구현하는 건 어려울게 하나도 없다. 정말 이전의 값을 재활용해서 불필요한 반복을 없애고, 그만큼 시간 복잡도를 줄이도록 구현하면 된다. 문제 풀이를 위한 조건 간단하게 정리 1... 공감수 9 댓글수 2 2019. 9. 13.
[백준] 1197번 최소 스패닝 트리 - Kruskal - union find 오픈 S/W 컨트리뷰톤과 카카오 코딩 테스트를 위해 열심히 알고리즘 공부를 하는 중이다. 한 문제를 풀기 위해 여러 개의 알고리즘을 공부하게 되니 시간이 오래 걸리는 것 같다. 간단하게 코드만 정리하고 다음 공부를 하러 가야겠다. Kruskal과 Union Find - Kruskal 알고리즘 최소 신장 트리(MST)를 만들 때 사용하는 알고리즘의 종류 중 하나다. 노드가 많고 산선이 적을 때 유리하다고 하는데, 최소 신장 트리를 만드는 알고리즘 중에서는 가장 쉽기 때문에 공부를 시작했다. 시간 복잡도는 O(E * logV) 모든 간선을 비용의 오름차순으로 정렬한 다음 간선을 차례대로 선택한다. - Union Find 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재.. 공감수 0 댓글수 0 2019. 9. 4.
[백준] 2042번 구간 합 구하기 파이썬 해설 -세그먼트 트리 알고리즘 공부 혼자 하는 게 생각보다 어렵..지만 꾸준히 해야지! 나는 원래 C언어로 알고리즘 문제를 풀었다. 임베디드 전공이다 보니 전공과목에서 프로그래밍 언어를 C/C++ 만 배웠기 때문이다. 하지만 임베디드를 넘어서 다양한 분야에 만능 프로그래머가 되고 싶어서 파이썬을 시작하게 되었고, 요즈음은 파이썬으로만 문제를 푼다. 쓸데없는 소리를 한 이유는.. 파이썬으로 알고리즘 문제를 풀면 너무 느려서 시간 초과가 너무 자주 뜬다.. 편법으로는 PyPy3로 채점하는 방법이 있는데, 그래도 찝찝하긴 하다.. 나는 이 문제를 세그먼트 트리 알고리즘으로 풀었다. 간단하게 정리해보자 세그먼트 트리 이 문제를 단순하게 배열을 확인하는 알고리즘으로 구현한다면 O(N^2)의 시간 복잡도를 갖게 되어 시간 초과를 면하지.. 공감수 0 댓글수 0 2019. 9. 2.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.