코딩테스트(10)
-
[Python] 🥇 백준 7576- 토마토 / BFS 알고리즘 이용하기
예제 입력 1 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 예제 출력 1 8 예제 입력 2 6 4 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 예제 출력 2 -1 아이디어 생각하기 이 문제는 익은 토마토들의 주위를 확인하며 나아가야하므로 bfs 알고리즘을 사용해야한다 또한 미로 문제와 다르게 시작점이 여러개이므로, 1인 토마토의 위치값을 모두 큐에 넣어준다 로직 순서 (1) 토마토 박스에 토마토 넣어주기 (2) 익은 토마토들의 위치를 q에 넣어주기 🌟🌟🌟출발점이 여러개인 경우 출발점을 모~두 Queue에 미리 넣어야 한다.🌟🌟🌟 (3) bfs 함수 실행 -1 큐에서 익은 토마토들의 위치를 popleft -2 fo..
2023.02.21 -
[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] 백준 파이썬 풀이 11724/연결 요소의 개수
문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력 1 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 2 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) #재귀 최대깊이, dfs 사용 시 오류 방지 n, m = map(int, inp..
2023.02.02