링크: https://www.acmicpc.net/problem/1743 아이디어전염되어있는 크기를 구하는거니 bfs를 쓰자N, M 최대값이 각 100 밖에 안돼서 NxM 전체 탐색해도 시간복잡도 그리 안클거 같음NxM 크기의 배열을 각 요소를 0으로 선언해주고 r,c 위치를 다 1로 표시해준다. -> li방문 확인용 배열도 NxM 크기의 각 요소 0인 배열 선언li 리스트를 돌며 1인 (쓰레기위치)를 찾으면 방문했던 위치인지 판단.방문하지 않은 위치라면 bfs 함수 호출size를 1부터 시작해서(자기자신) 주변 탐색을 진행쓰래기 발견시 size+1하는 형식으로 진행bfs 함수는 size 값을 반환result는 초기값 0 을 가지고 bfs 함수 호출 시마다 큰 값을 result에 대입해줌li 탐색이 모두..
링크: https://www.acmicpc.net/problem/2606 아이디어nodes리스트를 통해 카운트한 노드인지 아닌지 판단.bfs를 통해 연결된 노드들 탐색 -> deque() 사용간선을 모두 돌며 탐색하고자 한 값이 간선의 양 끝값중 같은게 있는지 판단같은게 있다면 그와 연결된 노드가 이미 탐색이 완료된 친구인지 판단탐색 전인 노드라면 q에 넣고 nodes 리스트에 탐색 표시 0->1모두 완료 후 nodes리스트의 총 합 -1 출력 ( 1번 노드는 빼야함)구현import sysfrom collections import dequeinput = sys.stdin.readlinenode_cnt = int(input())line_cnt = int(input())lines = [list(map(int..
링크: https://www.acmicpc.net/problem/17086 아이디어상어의 위치를 기준으로 bfs를 하자1번상어와 2번상어의 거리와 2번 상어와 1번 상어의 거리는 같으니 반복해서 탐색 할 필요가 없음li값이 0이 아닌 부분만 탐색한번 탐색한 li[y][x] 값을 이전 값의 +1 한 값을 넣어 거리와 탐색 했다 안했다를 동시에 지정bfs 탐색이 모두 끝난 후 li의 최대 값의 -1 한값 출력첫 시작을 1부터 했으니 -1을 해줘야 함 구현import sysfrom collections import deque input = sys.stdin.readlineN, M = map(int, input().split())li = [list(map(int, input().strip().split())) ..
링크: https://www.acmicpc.net/problem/21610아이디어N의 값이 그렇게 크지 않아서 반복문을 많이 써도 괜찮을 것 같다.구름의 좌표가 리스트 인덱스 표기보다 1 커서 -1을 미리 해주고 사용하면 편할듯구름이동과 대각선 확인은 따로 리스트를 만들어서 관리하면 좋겠다.구름 생성시 이전의 구름 위치는 생성하면 안된다. -> 튜플을 사용해서 시간 복잡도를 낮추면 좋겠다.구현# (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.# d 방향으로 s칸 이동# 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙import sysinput = sys.stdin.readlineN, M = map(int, input().split())li = [list(map..
링크: https://www.acmicpc.net/problem/1966 아이디어전체 테스트 케이스와 테스트 케이스 별 처리 과정 2중 반복문으로 O(N^2) 시간 복잡도를 가진다.deque 라이브러리를 활용해 큐 자료구조 다루자반복마다 pop 이벤트가 나오면 cnt 값을 증가시키자반복마다 M값을 변경하여 원하는 값의 위치를 최신화 하자반복마다 맨 앞의 값이 큐의 최대값인지 아닌지로 분기를 나눈다.맨 앞의 값이 최대값인 경우 (우선순위가 가장 높은 경우)M이 0 이면 cnt 값을 출력하고 반복문을 끝내 다음 테스트 케이스로 넘어간다아니면 M의 값을 1 감소, 맨 앞의 값 popleft()로 뺌, cnt 1증가맨 앞의 값이 최대값이 아닌 경우 (우선순위가 가장 높지 않은 경우)M이 0이면 맨 뒤에 붙여줘..
링크: https://www.acmicpc.net/problem/9375 아이디어규칙을 찾아 식으로 표현해보자하나라도 입고있으면 되고 같은 종류의 옷은 2개이상 못입는다.옷 종류별로 개수를 구한 후 + 1 하고 서로 곱하면 조합할 수 있는 모든 경우의 수가 된다.모자가 3개있으면 각 모자를 모두 쓰는 경우 + 안쓰는 경우 이렇게 존재입력받는 옷을 종류를 기준으로 갯수를 저장한다.갯수는 딕셔너리 형태로 {hat: 3} 과같이 저장한다.이후 위에서 구한 식을 통해 조합 할 수 있는 전체 경우의 수를 구한다.알몸인 경우 1을 빼면 알몸이 아닌 모든 경우의 수를 구할 수 있다. 구현test_case = int(input())for i in range(test_case): n = int(input()) ..
링크: https://www.acmicpc.net/problem/3568 아이디어입력받은 문자열을 " "(공백) 단위로 잘라 리스트로첫 요소는 무조건 맨 앞에 고정으로 사용하기 때문에 따로 저장.2번때 요소부터 for 문을 돌리며 판별 진행요소의 뒤에서 부터 확인하는데 맨 뒤는 , 아니면 ; 이기 때문에 그 다음 부터 확인 *이거나 &이면 따로 저장한 첫번째 요소의 뒤에 붙인다.]이 나오면 []를 붙이고 for문을 한번 건너 뛰어 다음으로 간다.알파벳 소문자가 나올 때까지 반복한다.알파벳 소문자가 나오면 그 지점을 가지고 변수명을 추출한다. -> 요소[:그지점 +1] = 변수명! 구현li = input().split()fix = li.pop(0)for i in li: result = fix f..
링크: https://www.acmicpc.net/problem/1929 생각M, N을 입력받음M부터 N까지 반복문을 돌며 소수 판별소수는 무엇인가 -> 약수를 1과 자기 자신만을 가지는 수하나의 수를 num이라 할 때 2부터 num -1 까지의 수를 눴을 때 나머지가 0이 되는 경우가 있으면 소수가 아님2중 for문을 써야겠다구현 1 - 시간초과M, N = map(int, input().split(" "))result = []for num in range(M, N+1): if num > 2: for i in range(2, num): if num % i == 0: break if i == num-1: ..
링크: https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 아이디어 물이 새는 곳 리스트를 돌며 처음것과 다음것의 차를 구하여 저장 -> tmp 그 값이 L보다 작으면 L-tmp를 하여 저장 -> L1 계속 돌며 L1-tmp를 하다가 tmp가 L1보다 더 커지는 경우 테이프를 하나 더 가져와야 함 cnt += 1 반복문이 끝날 때까지 계 구현 import sys input = sys.stdin.readline N, L = map(i..
