Python 4

[BOJ] 9466. 텀 프로젝트 / DFS / Python 풀이

몇 달 전부터 친구랑 같이 문제를 정해서 함께 풀고 있다. 이번에는 친구가 먼저 풀어봤는데 꽤 어려웠다는 문제를 풀어보기로 했다. 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 백준 9466번 문제로 레벨 골드3에 걸맞는 정답률을 자랑하고 있다. 정답 비율이 23퍼센트밖에 되지 않아서 겁을 먹었지만 풀고 나니 처참한 비율의 이유를 알게 되었다.. 알고 싶지 않았다 문제 이해 문제 설명이 말로 되어 있어서 처음에 이해하기가 어려웠다. 설명을 여러 번 읽어본 후에야 이해할 수 있었는데, 결국은 싸이클이 성립될 때 팀..

알고리즘 2023.06.11

[BOJ] 2636. 치즈 / BFS / Python 풀이

2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 오랜만에 포스팅, 최근 풀고 있는 BFS 문제다. 백준 2636번 문제로 골드4인데 정답률은 50퍼센트를 넘는다.. 친구와 함께 풀다가 몇 가지 힌트를 얻고 한 번에 통과했다 ㅎㅎ 문제 이해 공기와 접촉된 칸은 한 시간이 되면 녹아 없어진다. 이때 치즈로 둘러싸인 구멍은 공기와 접촉된 것으로 치지 않는다. 이 부분의 설명이 이해하기 쉽지 않아서 주춤했다. 접근 문제를 보자마자 너비 우선 탐색으로 접근했고, 처음에는 공기와 닿은 치즈를 어떻게 알아낼지가 고민이었다. 문제 ..

알고리즘 2023.06.02

선택 알고리즘 파이썬 구현

선택 알고리즘 이전 게시물 퀵 정렬 분할 알고리즘을 기본으로 함. 2021.07.29 - [알고리즘] - 퀵 정렬, 분할 알고리즘 퀵 정렬의 수행시간 분할 후 자기호출 -> 최악의 경우 O(N^2) 시간 소요 평균 선형 시간 선택 알고리즘 - 분할을 이용 - 평균 O(N), 최악의 경우 O(N^2) 시간 소요 분할 알고리즘이 리턴하는 값으로 기준원소가 전체에서 몇 번째 작은 원소인지 알 수 있다. 퀵 정렬을 필요한 부분만 해나가는 느낌 #평균 선형 시간 선택 알고리즘 select def select(a, p, r, i): if p==r: return a[p] q = partition(a, p, r) k = q-p+1 if i

알고리즘 2021.07.31

퀵 정렬, 분할 알고리즘 파이썬 구현

퀵 정렬 - 평균적으로 가장 좋은 성능을 가짐 - 현장에서 가장 많이 쓰이는 정렬 알고리즘 1. 정렬할 배열에서 기준 원소를 고른다 2. 기준 원소보다 작은 수는 왼쪽에, 큰 수는 오른쪽에 3. 기준 원소의 왼쪽과 오른쪽 부분 배열을 다시 정렬 (퀵 정렬 재귀) 파이썬 코드 구현 타입 에러 - return값이 없어서 - X - range 설정이 잘못됨 #Quik sort 퀵정렬 def quickSort(a, p, r): if p

알고리즘 2021.07.29