본문 바로가기

전체 글204

[백준] 7576번 토마토 상자 - 시간초과.. BFS 활용하자 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 예시 코드 모두 다 돌아가지만 시간 초과가 나온 코드 ㅠㅜㅠㅜ 속상하다. # BOJ_7576 # 모든 토마토가 익는 최소 날짜 구하고 싶어. 결과는 0, -1, 자연수 # 토마토는 상하좌우에 익은 토마토가 있을 때 익어. # 그렇다면 익은 토마토를 중심으로 인접한 토마토로 이동해야하니까 # DFS보다는 BFS가 적합하겠네. # 아니다 굳이 BFS를 쓸 필요 없이 # 인접한 익지 않.. 2023. 2. 20.
list, dict, set은 mutable 하다. Shallow Copy & Deep Copy 문제 출처: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net # 입력 받은 모든 토마토 상태 그래프 graph = [list(map(int, input().split())) for _ in range(n)] # 모든 토마토가 익었을 때의 그래프 finish_graph = graph print(graph) for i in range(n): for j in range(m): if finish_graph[i][j] == 0: fini.. 2023. 2. 20.
BFS DFS 정복하기 각 문제 유형별 풀 방법 정리 1) 그래프의 모든 정점을 방문해야하는 문제 DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다. 2) 경로의 특징을 저장하는 문제 예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다. 3) 최단거리를 구하는 문제 미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다. 4) 검색대상그래프가 많이 클때DFS가 좋다고한다. 5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별.. 2023. 2. 20.
리눅스 기본 Linux는 CUI인가 GUI 인가? CUI(Character User Interface) - 키보드 이용한 명령에 의해 조작하는 환경 - Linux - 리소스가 작고 보안이 비교적 견고하며 자동화 처리가 쉽다 GUI(Graphical User Interface) - 마우스를 이용하여 파일이나 폴더를 조작하는 환경 - Window, Mac 리눅스의 배포 형태, Distribution 리눅스 자체는 오픈소스이지만 실제로 기업이나 단체가 독자적인 규칙이나 지원 등 서비스를 덧붙여 패키지를 만들고 있다. 이것을 디스트리뷰션, 즉 배포 형태라고 한다. 유명한 디스트리뷰션 계열 Debian - Ubuntu slackware RedHat - CentOS > 무상에서 유상으로 변경됨(Red Hat Enterprise.. 2023. 2. 17.
약점보완: Dynamic Programming " 계속 쓰일 값은 저장해놓고 가져다 쓰자" 메모리를 조금 더 쓰지만, 수행 시간을 단축시킬 수 있다. 큰 문제를 작은 문제들로 분할하여 작은 문제들을 푼 결과를 이용해서 큰 문제를 해결하는 방법 DP를 사용하려면? 1. 큰 문제를 작은 부분 문제로 나눌 수 있을 때 2. 작은 문제에서 구한 정답을 큰 문제에서 사용할 때에도 동일할 때 DP으로 문제를 어떻게 해결할까? 1. 메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다 같은 정보를 다시 호출하면 메모했던 결과를 그대로 가져옵니다 값을 기억해둔다는 점에서 캐싱(caching)라고 합니다 '한 번 계산한 결과를 메모리 공간에 기록했다가 필요할 때 .. 2023. 2. 9.
[백준] 2164번 카드2 - 시간초과, 짝수 홀수 인덱스만 추출하기 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 처음에는 문제 그대로 구현하였다. num = n square = 0 while num >= 1: square += 1 num /= 2 square = square - 1 print(2 ** square) 그리고 짝수 홀수로 나뉘네 # 카드 구성 설정 cards = [] if n >= 8: n // 8 for i in range(1, n + 1): cards.append(i) # 규칙 그대로 구현해.. 2023. 2. 2.
[백준] 10816번 숫자카드2, 시간초과 - 이분탐색만으로도 안됨, bisect 모듈! https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색으로 아래 풀이 처럼 풀었는데도 시간초과가 뜬다. # BOJ_10816 # 입력 n = int(input()) cards = list(map(int, input().split())) m = int(input()) show_cards = list(map(int, input().split())) # 두 카드 목록 모두 오름차순으로 정렬한다. cards.sor.. 2023. 1. 25.
[백준] 1654번 랜선 자르기, 시간초과 - 이분탐색(풀이 암기) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 시간 초과 나온 풀이 # BOJ_1654 import sys # 입력 k, n = map(int, input().split()) lines = [] for _ in range(k): lines.append(int(sys.stdin.readline())) # 전체 합을 k로 나눈 값에서 내림차순으로 시작한다. sum = 0 for line in lines: sum += .. 2023. 1. 25.
[백준] 10816번 숫자 카드2, 시간 초과 - 이진탐색 + 알파 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 처음엔 count()를 이용하여 몇 개가 들어갔는지 구하였다. 그렇게 하니 시간복잡도가 O(n^2)으로 2% 대에서 시간 초과가 나왔다. 그래서 이진탐색 사용 # BOJ_10816 import sys # 입력 n = int(input()) cards = list(map(int, sys.stdin.readline().split())) m = int(input()) .. 2023. 1. 21.

티스토리툴바