링크: https://www.acmicpc.net/problem/1759아이디어 비밀번호의 모든 가능한 조합을 탐색해야 하므로 백트래킹을 사용알파벳은 사전 순으로 정렬되어야 하므로 입력받은 알파벳 리스트를 정렬한 후 탐색을 시작백트래킹 함수는 매개변수로 현재 인덱스를 받아 해당 인덱스 이후의 문자들만 탐색패스워드의 길이가 L이면 해당 문자열이 유효한 비밀번호인지 check 함수를 통해 확인모음이 최소 1개자음이 최소 2개조건을 만족하면 해당 비밀번호를 출력하고 만족하지 않으면 그대로 return 구현import sysinput = sys.stdin.readlinedef check(password): mo = sum (1 for x in password if x in 'aeiou') ja = l..
링크: https://www.acmicpc.net/problem/1182 아이디어모든 경우의 수를 탐색하는 문제이므로 백트래킹을 활용한다.back 함수는 인자로 idx와 li_sum을 받는다.idx는 현재 탐색할 수열의 인덱스를 의미하며, 이를 통해 a + b 와 b + a 같이 중복되는 조합을 방지할 수 있다.li_sum은 지금까지 선택한 수들의 합이며, 이 값을 s와 비교해 조건을 만족하는지 판단한다.현재 합이 s와 같으면 cnt를 1 증가시킨다.하지만 여기서 탐색을 멈추는 것이 아니라 이후 값을 더한 경우도 여전히 조건을 만족할 수 있으므로 재귀를 이어간다.다만 s == 0인 경우 아무 값도 선택하지 않은상태에서 li_sum == s가 성립하므로 마지막에 cnt에서 1을 빼준다.구현import ..
링크: https://www.acmicpc.net/problem/15651 아이디어이전글 N과 M (1) 을 보고오면 더 쉽다.N과 M (1)과 유사하지만 조건 하나만 빼주면 위 문제가 풀린다.N과 M (1)에선 check 배열에 존재하면 추가하지 않았지만 이는 중복을 허용해야 하기 때문에 그 조건을 제거해준다.구현import sysinput = sys.stdin.readlinedef back(): if len(check) == m: print(*check) return for i in range(1, n+1): check.append(i) back() check.pop()n, m = list(map(int, input().spli..
링크: https://www.acmicpc.net/problem/15649 아이디어모든 가능한 경우의 수를 탐색해야 하므로 DFS를 활용한다.길이 제한 조건(M)이 있으므로 백트래킹이 적합하다.현재까지 선택한 숫자들을 check 리스트에 저장한다.리스트의 길이가 m이 되면 해당 수열을 출력한다.아직 길이가 m이 안 되었다면 1부터 n까지의 수 중 아직 선택되지 않은 수를 하나씩 추가하면서 재귀적으로 탐색을 이어간다.구현import sysinput = sys.stdin.readlinedef back(): if len(check) == m: print(*check) return for i in range(1, n+1): if i not in check: ..
링크: 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이면 맨 뒤에 붙여줘..
