dfs
-
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
[Python] 프로그래머스 소수 찾기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
2023.03.06 -
14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 나의 풀이 +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다. 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다. 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다. def get_perm(arr, n): perm_list = [] # ..
[파이썬] 백준 연산자 끼워넣기14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 나의 풀이 +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다. 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다. 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다. def get_perm(arr, n): perm_list = [] # ..
2022.11.11 -
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다. 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다. 백트래킹 활용 현재 위치 정보를 전달해서 중복된 방문을 제한했다. [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. from collections import defaultdict def solution(tickets): # 방문 여부 visited = defaultdic..
[파이썬] 프로그래머스 여행경로프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다. 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다. 백트래킹 활용 현재 위치 정보를 전달해서 중복된 방문을 제한했다. [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. from collections import defaultdict def solution(tickets): # 방문 여부 visited = defaultdic..
2022.10.31 -
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 기존에 DFS, BFS를 시뮬레이션에서만 활용했어서 간단한 문제임에도 못 풀었다. DFS를 활용할 때, 어떤 값을 넘겨줄 지가 정확히 설계하는 것이 중요함을 깨달았다. DFS를 재귀, stack 방식 모두를 활용해 구현해봤다. from collections import deque def dfs(num_sum: int, idx: int, max_idx: int, numbers: list, target: int): global answer # DFS 진행 동안 answer 값 증가 if idx == m..
[파이썬] 프로그래머스 타겟 넘버프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 기존에 DFS, BFS를 시뮬레이션에서만 활용했어서 간단한 문제임에도 못 풀었다. DFS를 활용할 때, 어떤 값을 넘겨줄 지가 정확히 설계하는 것이 중요함을 깨달았다. DFS를 재귀, stack 방식 모두를 활용해 구현해봤다. from collections import deque def dfs(num_sum: int, idx: int, max_idx: int, numbers: list, target: int): global answer # DFS 진행 동안 answer 값 증가 if idx == m..
2022.10.03 -
1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 시간 제한 2초 메모리 제한 256MB 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 ..
[파이썬] 백준 1707번 이분 그래프1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 시간 제한 2초 메모리 제한 256MB 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 ..
2022.05.12 -
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 ..
[파이썬] 백준 2667번 단지번호붙이기2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 ..
2022.05.03