Redddy's Devlog

정렬 (Sorting) 정렬은 데이터를 특정한 기준에 따라서 순차적으로 나열하는 것이다. 흔히 사용하는 내림차순이나 오름차순 역시 이 정렬을 통해 이루어진다. 이진탐색이라는 탐색기법은 정렬과정을 거친 후에만 사용이 가능하다. 정렬알고리즘은 Comparison Sorting Algorithm(비교방식 알고리즘)과 non - Comparison Sorting Algorithm 이렇게 크게 두가지로 나눌 수 있다. 비교방식 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등이 있고, non-비교방식 알고리즘에는 계수 정렬이 있다. 선택 정렬 (Seletion Sort) 선택 정렬은 배열에서 가장 작은 데이터를 선택하여 다른 데이터와 자리를 바꾸는 알고리즘이다. 일반적으로 쉽게 떠올릴 수 있다. 정렬되지 않은 배열에서..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..

그래프 : Graph DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자. 우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 그래프를 표현하는 방법은 크게 두가지가 있다. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하..

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 아래와 같은 함수가 재귀 함수이다. def recursive_function(): print("재귀 함수를 호출합니다.") recursive_function() recursive_function() 그러나 이 코드를 실행시킨다면 "재귀 함수를 호출합니다." 라는 문장을 출력하다가 어느 순간 에러를 내며 멈출 것이다. RecursionError: maximum recursion depth exceeded while calling a Python object 이 오류 메세지는 재귀의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 그 한계를 벗어났기에 다음과 같은 메세지를 출력한 ..

구현이란? 구현(Implementation)이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. 물론 어떤 문제를 풀던 간에 소스코드를 작성하는 과정은 필수이다. 그러나 구현이라고 따로 분류하는 문제들은 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 완전 탐색과 시뮬레이션은 모두 구현이 핵심이 되는 경우가 많다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 이것이 코딩테스트다를 읽고 정리한 내용입니다.

그리디 알고리즘이란? 한국어로 탐욕이라는 뜻의 그리디 알고리즘(Greedy Algorithm)은 단순하만 강력한 문제 해결 방법이다. 탐욕적으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이 바로 탐욕법, 그리디 알고리즘이다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 다른 알고리즘과는 달리 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 유형의 문제이다. 다음번에 다룰 최단 경로, 정렬 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 ..

📎문제링크: https://www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 💼서론 취킨먹고싶다🍗 🧩문제 해석 치킨을 주문하는데에는 쿠폰이 필요하다. 그리고 치킨 한마리 시킬때마다 도장을 하나찍어주는데 k개의 도장을 찍으면 한개의 쿠폰과 교환할 수 있다. 또 이렇게 구매한 치킨에도 도장을 찍어준다! 또한 문제의 테스트케이스가 주어지지 않기 떄문에 무한 루프를 돌리고 시스템 종료 처리도 잘 해줘야한다. 📘풀이 1. 우선 가지고 있는 쿠폰 n개와 쿠폰 n개로 구매..

📎문제링크: https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 💼서론 예~~전에 한번 봤다가 어케 푸는지 잘 모르겠어서 패스했던 문제다. 요즘 그리디 알고리즘을 배우고 있어서 다시 한번 도전해보았다. 구글링 없이 푸니까 나 자신 스스로도 성장했다고 느꼈다. 🧩문제 해석 다솜이는 국회의원이 되고 싶고 누가 누구를 뽑을지 알고 있다. 즉 다솜이 말고 다른 후보에게 투표하는 사람을 매수하여 자신을 투표하도록 만들어야 하는데 몇명을 매수해야 ..

월과 일이 주어졌을때 무슨요일인지 알아내는 프로그램이다. 처음부터 2007년이라는 연도가 주어졌기 때문에 조금은 쉽게 갔다. 만약 연도까지 입력값에 따랐다면 훨씬 더 복잡한 알고리즘으로 작성됐을 것이다. 📚 풀이 1. 입력받은 월(month)을 일로 변경하여 입력받은 일(date)과 더한다. 2. 더해진 일을 7로 나누어 나머지로 요일을 확인한다. 💻 코드 # PYTHON month, date = map(int, input().split()) # 매월의 마지막 일수 month_list = [31,28,31,30,31,30,31,31,30,31,30,31] day_list = ["MON","TUE","WED","THU","FRI","SAT","SUN"] days = 0 # 주어진 달의 이전달까지 모든 일을..

프로그램 내에서 바로 시간 복잡도를 측정할 수 있는 외장함수가 있다. time 을 import 해서 시작 부분에 시간을 start_time에 넣고 코드 마지막에 end_time을 넣어 그때의 시간을 측정한다음 뺄셈을 해준다. 그러면 그 사이 코드가 수행된 시간을 알 수 있다.