코딩 일기장

⭕️ 문제 ⭕️ 문제 접근 이 문제는 다른 레벨3 문제에 비해 많이 쉬운것 같다. 리스트에서 주어진 구간 내의 합을 구하고, 평균을 구해주면 되는 문제이다. 이 문제에서는 소수점 자리에 맞게 포맷팅 하는 부분을 주의깊게 봐 두면 될 것 같다. print("{0:.2f}".format(숫자))) round 함수를 사용하게 되면 45 같이 정수의 형태는 자릿수에 맞게 표현이 불가능하다. 따라서 format 함수를 사용하여 소수점 둘째 자리까지 평균을 표현해준다. 코딩테스트에서는 포맷에 맞게 표현하는게 중요하니 기억해두자! ⭕️ 문제 풀이 import sys N, K = map(int, sys.stdin.readline().split()) scores = list(map(int, sys.stdin.readli..

🫠 문제 🫠 풀이 방법 전형적인 dp 문제입니다. 하지만 dp에 익숙하지 않은 저는 처음에 dp 문제인지 파악이 힘들었습니다ㅎㅎ dp문제도 열심히 연습해야겠습니다 😭 사실 답안을 봤음에도 처음에는 이해하기 어려웠습니다. 아래는 제가 이해한 내용입니다. 바깥 for문: 우선 돌다리를 처음부터 끝까지 한번 탐색합니다. 안쪽 for문: 탐색할 때, 현재 탐색하는 돌(stones[i])와 지나온 돌(stones[j])값을 비교합니다. 현재 탐색하는 돌(stones[i])이 지나온 돌(stones[j])보다 높다면 건널 수 있다는 뜻입니다! 그래서 지나온 돌을 건널 때(dp[j]+1)와 건너지 않을 때(dp[i])의 값을 비교하여 큰 값을 현재 돌의 dp값으로 업데이트 합니다. 이렇게 해 주면 dp array의 ..

진짜 이 문제 풀다가 화가 많이 났어요... 요즘 제가 이상한 걸수도 있는데 소프티어 문제들은 뭐랄까... 엄청 성질을 박박 긁는달까요...?^^// 제가 더 분발할게요.... 소프티어 레벨3을 한번에 풀어버리는 멋진 알고리즘 왕이 되는 그날까지...⭐️ 🫠 풀이 접근 모든 얼음이 녹을 떄까지 bfs 탐색을 반복합니다. 이 때, visited 변수를 초기화 시키는거 잊지 말기! 상하좌우를 탐색할 때, 앞으로 탐색할 칸이 얼음인지 혹은 얼음이 아닌데 방문한 적이 없는 곳인지 파악해야 합니다. 이렇게 하면 얼음 내부는 탐색하지 않고 얼음 밖의 영역만 탐색을 하게 됩니다! 두 면이 닿은 얼음 (visited >= 2)인 얼음은 녹여줍니다 🫠 풀이 과정 import sys from collections impo..

🐶 문제 주어진 수열 중에서 그 값이 인덱스와 동일한 원소 찾기 ex) 수열 a = {-15, -4, 2, 8, 13}이면 a[2] = 2 이므로 고정점은 2가 됨. 수열은 오름차순으로 정렬되어 있음 고정점이 없다면 -1을 출력함 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 남 🐶 생각 이 문제 또한 O(logN)의 시간 복잡도를 넘게 되면 시간 초과가 나기 때문에, O(N)의 시간 복잡도를 가진 선형 탐색으로는 풀 수 없다. 따라서 이진 탐색을 구현해야 함! 단순히 이진 탐색 알고리즘을 알기만 하면 쉽게 풀 수 있는 문제이다. 🐶 문제 풀이 import sys N = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readl..

이 문제는 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 나오는 문제이다. 따라서 일반적인 for문을 활용하여 리스트를 탐색하면 시간 초과가 난다! 그렇기에 O(logN)의 시간 복잡도를 가지는 이진 탐색을 활용해야 한다. 직접 이진 탐색을 구현할 수도 있지만 파이썬의 라이브러리와 친숙해지기 위해 bisect 라이브러리를 사용했다. bisect는 특정 숫자 사이에 있는 원소의 개수를 구할 때 유용하게 사용된다. 여기서 주의할 점은 array가 오름차순으로 sorting되어 있어야 한다는 점이다! 해당 문제의 경우 이미 오름차순으로 정렬된 수열이 input값으로 들어온다. bisect_right(array, N) 배열에서 N이 마지막으로 등장하는 인덱스+1을 리턴함 bisect_left(arra..

파이썬으로 알고리즘을 풀 때, input을 입력받는 과정에서 input()을 사용하면 시간 초과가 나올 수 있음! sys.stdin.readline 을 사용하여 입력값을 받자 거리 정보를 받을 때 아래와 같이 리스트의 형식으로 저장하면 특정 노드로부터 시작하는 거리가 있는지 파악하기 수월하다! queue를 사용하여 탐색할 노드를 파악한다 for _ in range(M): a, b = map(int, input().split()) dist[a].append(b) ✅ 문제 풀이 코드 import sys from collections import deque input = sys.stdin.readline N, M, K, X = map(int, input().split()) dist = [[] for _ in ..