백준20 1012 유기농 배추 💡문제 분석 요약이 문제와 거의 유사했다. 그리고 저 문제에다가 이차원 배열을 탐색하는 nx, ny 요소만 추가하면 됐다. 이 부분은 여기 문제와 유사했다. 저 두 문제의 방법을 합치면 될 것이다 !결국, 지렁이가 몇마리냐 구하는 것은 DFS/BFS가 몇번 실행되느냐를 구하면 되는 것과 같은 맥락이었다. DFS가 아직은 더 편해서 DFS로 접근해보았다. 결국 모든 노드를 방문하는 맥락에서는 두 방법 모두 사용 가능하다.💡알고리즘 설계인접행렬, 인접리스트 2가지 방법으로 풀 수 있지만 인접행렬로 풀어보았다. 💡코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(5000)# 순서대로 상, 하, 좌, 우로 이동하는 것을 의미dx = [0, 0, 1,.. 2024. 7. 18. 백준 1158 💡문제 분석 요약N명의 사람이 있고, K번째 사람을 제거한다. 제거되면 그 다음 K번째 사람을 다시 제거한다.제거된 사람은 list에서 빠지게 된다.최종 1명이 남을 때 까지 제거한다.💡알고리즘 설계원형큐를 사용해야될 것 처럼 보였는데, 일단은 list를 사용한 큐로 풀었다.나머지 계산이 들어갈 것으로 보이고, len(list)를 나누는 것을 pop하고 나서 할지, 이전에 할지 생각해보면 될 것 같다.💡코드n, k = map(int, input().split())lst = [x+1 for x in range(n)]removed_people = [] # 제거된 사람 모임remv = 0 # 제거될 사람for i in range(1, n+1): remv += (k-1) if remv >= le.. 2024. 7. 9. 백준 10828 💡문제 분석 요약(시간/공간복잡도 제약도 추가하기)5개의 명령에 대하여 각 명령에 대해 다른 작업이 수행된다.명령은 5개 이외에는 주어지지 않는다.입력 개수는 10만개까지 가능하다.💡알고리즘 설계입력값을 담는 stack은 파이썬의 list를 사용하였다.5개의 명령에 대해 switch처럼 처리하는데, 파이썬은 switch가 없으므로 if-elif 형식으로 작성해본다.stack이 비어있는 경우처럼 특별한 케이스가 있는 명령어에 대해선 if-else를 안쪽에 하나 더 추가해준다.💡코드"""1. 처음에는 시간초과 났는데, sys.stdin.readline 으로 입력받으니까 바로 해결2. 한줄에 몇개를 입력받는지 모르는 상황에선 a, b = input().split()처럼 하지 말고 a = input().s.. 2024. 7. 8. 구) 브론즈~실버 백준 다시 볼법한 문제 예전에 실버 5 안팎의 문제들 중에 틀렸던 문제들인데, 근데 이제는 안볼듯... 그래도 정리는 해본다. 1929 - 소수 빠르게 구하기 힌트 : 소수라는 건 결국 약수를 다루는 거고, 약수들은 대칭이다. 2941 - 크로아티아 알파벳 힌트 : 변경된 알파벳들로만 이루어진 리스트를 만든다. 1157 - 단어 공부 힌트 : set을 이용. 1152 - 단어의 개수 힌트 : 공백으로 나누고, 덩어리 개수 참고 : 왜 ord == 32나 == ' ' 로는 안되는가?? -> 공백하나만 입력값으로 줄 수도 있으니 2839 - 설탕 배달 힌트 : 5의 배수가 될때까지 설탕 3kg씩 빼기 // 또는 5kg을 0봉지 1봉지 2봉지 ... list로 경우의 수 다 만들어놓기 2108 - 통계학 中 최빈값 모르겠다 ... .. 2023. 2. 2. 12/27 스터디 1300 K번째 수 n=10 , k=20이면 숫자가 크다보니 규칙을 찾아야함 A 행렬 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20 3 6 9 12 15 18 21 24 27 30 4 8 12 16 20 24 28 32 36 40 ... 10 20 30 40 50 60 70 80 90 100 B[20] 이중에서 20보다 작거나 같은 값이 몇개인지 세면 됨 => 각 행이 구구단임 ? k=20 i*j가 20 안에 몇개인지 세면 되는데 1행은 10개 10까지 2행은 10개 20까지 3행은 6개 18까지 4행은 5개 20까지 5행은 4개 20까지 6행은 3개 18까지 7행은 2개 14까지 8행은 2개 16까지 9행은 2개 18까지 10행은 2개 20까지 k // i => 2.. 2022. 12. 28. 12/23 스터디 어떤 블로그에서 봤는데, 이분탐색은 숫자 맞추는 up down 게임이라고 하더라... 좋은 예시인 것 같다.. 2110 공유기 설치 ㅇ 9663 N-Queen python으로는 실패하고... 동일 코드로 pypy로는 통과하는 문제인데 간혹 이런 문제가 나오는데 로직이 문제인지 잘 모르겠다... pypy로만 통과되는 문제면 그만큼 시간관리가 엄격하다는 건데, 그래서 그런지 검색해서 나오는 코드마다 모두 일차원 배열로 풀었다. 이차원 배열은 시간이 더 많이 걸려서 그런가보다 ... 일차원 배열 board를 선언했는데 이것의 의미는 board[ i ] = j 일 때 [ i, j ]에 퀸을 놓겠다는 의미이다. 이것을 잘 기억해두어야 한다. 우리가 문제를 풀 때 사용하는 함수는 2가지이다. 퀸을 놓을 수 있는지 .. 2022. 12. 23. 12/20 스터디 15651 N과 M(3) N과 M(1) 문제와 매우 비슷한 문제였다. 애당초 N과 M 문제들 자체가 순열 조합 문제라서, 순열 조합 중복순열 중복조합으로 이해하고 접근하면 바로 풀 수 있었다. 이 문제는 순열과 똑같은 맥락에, 중복을 추가한 문제였기 때문에 순열 코드에서 중복을 제거하는 부분만 없애주면 중복을 추가해줄 수 있게 되고 그러면 중복순열을 구현할 수 있었다. 따라서 for문 안에 if i not in s부분을 지워주면 된다. 나머지 코드는 15649 N과 M(1) 문제의 코드와 동일하다. n, m = list(map(int, input().split())) s = [] def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i i.. 2022. 12. 20. 12/14 스터디 15650 N과 M(2) 앞서 풀었던 15649 문제 N과 M(1)이 순열 문제였다면, 이 문제는 조합 문제였다. 마찬가지로 combination을 쓰면 금방 풀 수 있지만 이것도 백트래킹을 활용해 풀어야한다. 순열과 조합 자체가 유사한데 한가지 다른 점은 순열은 [1,2]와 [2,1]이 다르지만 조합은 서로 같다. 이 점을 이용해서 15649 코드를 조금 변형하면 된다. n, m = list(map(int, input().split())) s = [] def dfs(start): if len(s) == m: print(' '.join(map(str, s))) return for i in range(start, n + 1): if i not in s: s.append(i) dfs(i + 1) s.pop(.. 2022. 12. 15. 12/7 스터디 1920 수 찾기 전형적인 binary search 문제였고, 이분탐색을 위해 먼저 정렬을 해주었다. 정렬 후 각 숫자들에 대해 모두 binary search 알고리즘을 적용해주었다. 이때, 한가지 다른 점은 flag를 각 숫자마다 0으로 설정해놓고 숫자를 찾으면 flag = 1, 없으면 그대로 0으로 설정을 해서 마지막에 flag 값에 따라 숫자 유무를 검사해서 1 혹은 0을 출력해주는 형식으로 진행해주었다. binary search에 대해 간단히 설명하면, 반씩 쪼개서 탐색을 하는 알고리즘인데 탈출 조건은 start와 end가 서로 엇갈리는 순간이다. 즉, start 2022. 12. 9. 이전 1 2 3 다음 반응형
