분류 전체보기 (61) 썸네일형 리스트형 [백준 13305번 / 실버4] 주유소 - (그리디) https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 처음에 풀때 시간초과가 떠서 input()을 sys.stdin.readline()으로 바꿨는데 마찬가지로 시간초과가 떴다. 한마디로 코드에 문제가 있었다는 뜻. 아래 코드는 다시 짠 코드임. 이 문제의 풀이법!!! 현재상황에서 가장 최선의 선택을 하면 되는 그리디 알고리즘 문제이다. 현재 도시를 기준으로 현재 도시보다 기름값이 더 싼 곳에 이동할때까지 현재 도시에서 주유한 기름으로 .. [알고리즘/Python] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 이란?? 병합 정렬(Merge Sort)와 더불어 대표적인 분할 정복 알고리즘 중 하나이다. 리스트 값중 랜덤한 값을 pivot으로 설정한 뒤 pivot보다 작으면 왼쪽에, pivot보다 크면 오른쪽에 위치시킨다. pivot을 기준으로 나눠진 왼쪽과 오른쪽 리스트에 대해 또 다시 위의 과정을 재귀적으로 시행한다. 평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2)이다. def quick_sort(arr): #리스트가 하나 이하의 원소를 가지고 있다면 종료 if len(arr) [이코테 with Python] 음료수 얼려먹기 - (Graph Traversal) 문제 N * M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 00110 00011 11111 00000 입력 첫 번째 줄에 얼음 틀의 새로 길이 N과 가로 길이 M이 주어진다.( 1 [백준 2178번 / 실버1] 미로 탐색 - (Graph Traversal) 문제링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 최소경로를 찾는 문제이고 각각 간선(edge)의 가중치가 동일하므로 BFS를 이용해도 무방하다. 핵심은 dx,dy라는 방향벡터를 사용하는 것과, 미로의 정보를 나타내는 data라는 2차원 리스트랑은 별개로 특정 칸을 방문하기 위해 지나야 하는 최소 칸의 정보를 담고있는 visited라는 2차원 리스트를 추가로 만드는것이다. from collections import deque def BFS(data): v.. [백준 1260번 / 실버2] DFS와 BFS - (Graph Traversal) 문제링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS 코드에서 굳이 visited라는 리스트를 return해 주지 않고도 코드를 작성할 수 있다. 사실 visited를 return하는 방법과 하지않는 방법 중에서 어떤것이 더 좋은 코드인지 잘 모르겠다..ㅎ from collections import deque def DFS(graph,v,visited=None): visited.app.. [알고리즘/Python] DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 구현 DFS (Depth-First-Search) 그래프에서 가장 깊은 부분을 우선으로 탐색하는 알고리즘이다. 진행 가능한 노드가 없을 때까지 깊게 파고드는 방식이며, 더이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고든다. 주로 모든 노드를 방문하고자 하거나, 이동할때 마다 가중치가 붙어서 이동하는 경우, 그리고 이동 과정에서 여러 제약이 있는 경우에 이 방식을 사용한다. 또한 검색 대상 그래프가 정말 크다면 DFS를 사용한다. DFS 알고리즘을 구현할때는 재귀로 구현할 수도 있고, 스택을 이용해서 구현할 수도 있다. 코딩테스트에서 구현할때는 재귀로 구현하는것이 더 선호되는 편이다. 장점 BFS에 비해 저장공간의 필요성이 적다(적은 메모리 사용). 백트랙킹을 해야하는 노드들만 저.. [알고리즘/Python] 그래프 구현 - 인접 행렬과 인접 리스트 알고리즘 문제를 보다가 보면 Graph와 관련된 문제들을 매우 많이 접할 수 있다. 보통 이런 그래프와 관련된 문제를 풀때는 현재 그래프의 모습을 모델링하고 난 뒤에 문제를 푼다. 이때, 모델링한 그래프의 연결관계를 나타내는 방법에는 크게 두가지가 있다. 1. 인접 행렬 2. 인접 리스트 1. 인접 행렬 그래프에서 두 노드(vertex) 사이의 연결 관계를 이차원 배열로 나타내는 방식이다. 보통 adj[][]형태로 많이 사용한다. adj[i][j] : 노드 i에서 j로 가는 edge가 존재할 경우 1, 아니면 0 만약 구현하고자 하는 그래프가 Undirected Graph 일때는 adj[i][j] == adj[j][i] 일것이다. 이 경우에서 인접 행렬을 구현하면 대각선을 기준으로 대칭인 성질을 가질 것.. [알고리즘/Python] 알고리즘 설계 Tip!! 코딩 테스트 문제에서 시간제한은 보통 1~5초가량이라고 생각해야함. Python의 경우 연산 횟수가 5억을 넘어간다면 통상 5~15초 가량의 시간이 소요된다. 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)이다. 만약 시간제한이 1초인 문제를 만났다면, 일반적인 기준은 다음과 같다. N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하기 N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하기 N의 범위가 100,000인 경우 : 시간 복잡도가 O(N*logN)인 알고리즘을 설계하기 N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하기 일반적으로 알고리즘 문제를 만났을때의 사고과정!! 지문 읽기 및 컴.. 이전 1 ··· 4 5 6 7 8 다음