JooTopia's Blog

출처 : https://www.acmicpc.net/problem/1713 코딩 테스트 문제에서 자주 출현하는 구현 알고리즘이다. 보통 1, 2번 문제에 출제되고 긴장하면 말리기 쉬운 문제 유형이니 많이 풀어서 익숙해지는 게 중요한 것 같다. 풀이 보통 구현 문제는 여러가지 조건을 그대로 구현하면 정답을 맞힐 수 있는 구조로 많이 출제된다. 성급하게 접근하기 보단 문제의 조건을 읽어보고 정리한 뒤에 알고리즘을 설계하는 것을 추천한다. 문제의 조건은 다음과 같다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 ..

출처 : https://www.acmicpc.net/problem/7576 BFS 알고리즘으로 분류된 문제이다. 코딩 테스트를 통과하기 위해 알고리즘 문제를 많이 풀던 시기에 가장 취약했던 알고리즘의 종류 중 하나이다. 한 번의 시도만에 취업을 성공해서 당분간 코딩 테스트는 치르지 않지만, 약점을 보완하기 위해 내가 약했던 알고리즘을 위주로 문제를 다시 풀어보고 있다. 풀이 처음 이 문제를 접근할 때는 하루가 지날 때 마다 배열의 모든 점을 탐색하는 알고리즘을 설계하고 그대로 구현하였다. 나름 예외처리를 했다고 생각했지만 M과 N이 증가 할 수록 시간 복잡도가 기하급수적으로 늘어났고 결국 시간 초과라는 결과를 받았다. ㅜㅜ 그 후에 파이썬의 dequeue 모듈을 사용해서 좀더 효율적인 알고리즘을 새로 설..

출처 : 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 그래프 이론 알고리즘으로 분류된 문제이다. 문제를 다 풀고 다른 사람들의 풀이를 참고하며 공부했는데 플로이드 와샬 알고리즘을 사용했..

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

요즘은 신경치료를 받으면서 네이버 테스트를 준비 중이라 공부를 많이 못한다. 변명이 아니라 진짜 너무 스트레스받는다 치통... 나중에 이 글을 읽는 나는 명심해라! 이가 조금이라도 깨지면 바로 치과로 가라! 문제 출처 : https://www.acmicpc.net/problem/11726 이 문제를 포스팅 한 이유는 파이썬의 재귀 깊이의 한계치 때문이다. 아마 파이썬으로 이 문제를 채점하면 "런타임 에러"가 발생할 수도 있다. 문제 풀이 이 문제는 동적 프로그래밍의 가장 기본적인 문제이기 때문에 풀이는 쉽지만 그래도 정리는 해보겠다. import sys input = sys.stdin.readline n= int(input()) dp = [0]*n def f_dp(n): if n == 1: return ..

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

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

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

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