파이썬알고리즘(10)
-
[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘
예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 아이디어 생각하기 그래프를 만들고, 방문여부를 체크하는 배열 visited를 선언한다. 루트 v를 dfs() 인수로 넘겨 V와 연결된 다른 노드를 재귀적으로 방문한다. for문으로 그래프를 도는데, 만약 visited[v]가 비어있다면, visited했다는 의미의 True가 아닌, 탐색을 시작한 값 즉, 부모를 넣어준다. 그리고 다시 재귀한다. 결국, dfs를 기존 그대로구현하고, visited에는 방문여부대신, v를 넣어주면 된다! 기존의 로직을 헷갈릴 것 같아서 변수명은 그대로 visited로 냅두고 진행하겠다 원한다면 father, parents 등으로 바꿔보자.... 주의사항 graph = [[0] *..
2023.02.19 -
[ Python] 백준 10819번 차이를 최대로 / 브루트포스 그림 풀이
문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다. 예제 입력 1 6 20 1 15 8 4 10 예제 출력 1 62 아이디어 생각하기 대체 최대값이 왜 62나 나오지? 라고 생각했다... (최대값 - 최소값) + (2번째 최대값 + 2..
2023.02.14 -
[python] 계수정렬
카운트 할 배열을 선언하고, 정렬할 배열 요소가 몇개가 있는지 카운트 배열 각 인덱스에 담는다 데이터의 크기가 한정되어 빠르게 동작해야할 때 사용된다. 예제를 통해 [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 배열을 순서대로 정렬해보자 step 0 배열과 요소의 갯수를 셀 배열 선언 arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] cnt = [0] * (max(arr) + 1) # arr 변수에 요소가 몇개가 있는지 셀 배열 step 1 arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 1 0 0 step 2 arr = ..
2023.02.07 -
[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이
이진탐색: 배열 내부의 데이터가 정렬되어 있을 때 시작점, 끝점, 중간점을 이용하여 원하는 값을 찾는 탐색법 시작점을 start 중간점을 mid, 끝점을 end라고 부르겠다 이진탐색은 주어진 범위가 엄청 클 때 사용할 수 있고, 배열의 원소들은 오름차순으로 정리되어야 한다. 코드 작성 순서 (1) 이진탐색의 시작점과 끝점을 설정 start= 0 end = 배열에서 가장 큰 수, 혹은 주어진 최대값 (2) 이진탐색 수행 while(start
2023.02.07 -
[Python] 백준 11652번 풀이 / 카드 / sorted()에서의 key lambda 사용하기
문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 예제 입력 1 5 1 2 1 2 1 예제 출력 1 1 틀렸던 코드 import sys input = sys.stdin.readline n = int(inp..
2023.01.30 -
[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결
import sys input = sys.stdin.readline n = int(input()) arr = [] for i in range(n): arr.append(int(input())) arr.sort() for i in arr: print(i) 입력받은 값을 빈 배열 arr에 append 후, sort()함수로 오름차순하여 출력하는 형식을 생각했다 하지만 메모리 초과 발생...! 메모리 제한이 8MB로 굉장히 작은데, 많은 메모리를 소요하는 파이썬으로 실행하니 쉬운 문제임에도 불구하고 오래 걸렸다.... 메모리 초과 발생 이유 (1) sort,sorted를 사용 (2) sys.stdin.readline이 아닌 그냥 input()를 사용 (3) for 문 안에 append를 작성 따라서 이 문제는..
2023.01.30