PYTHON (17) 썸네일형 리스트형 [DFS/BFS] 타겟넘버 문제링크https://school.programmers.co.kr/learn/courses/30/lessons/43165 해설내 풀이간단하게 내가 이 문제를 직접 풀면 어떻게 풀까 고민하다가 생각난 풀이이다.숫자가 여러개 들어있을 때 값을 빼줄지 더해줄지에 대한 모든 경우의 수를 미리 짜두고이에 대한 계산을 진행하는 코드이다나는 이를 구현하기 위해서 생각 났던 방식이 어짜피 더하기 빼기는 결국 -1, 1을 곱해서 더하는 과정이라고 생각했고, 이를 구현하기 위해 이진법으로 2의 숫자의 갯수 제곱만큼 늘려주고 이렇게 부여된 값을 각각 숫자에 더해주는 과정으로 진행했다 예를 들어서 문제에 나온 것 처럼 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다.-1+1+1+1+.. [DFS/BFS] 연구소 문제링크https://www.acmicpc.net/problem/14502문제 이해하는 데도 상당히 오랜 시간이 걸린 문제이다0 갯수를 최대화 할 수 있도록 1을 3개 세워야하는 문제이다2가 탐색 방식으로 확장해나가는 구조라 생각하면 좀 더 쉽게 생각이 가능하다1이 나올때 까지 0을 2로 바꿔버린다 해설이 문제야 말로 컴퓨터가 인간보다 잘 푸는 유형의 대표적인 예라고 생각한다전체 조합을 모두 고려해야하는 상황에서는 dfs를 먼저 생각할 줄 알아야 한다 풀이과정3개의 벽을 골라 벽을 설치한다각 바이러스가 사방으로 퍼지는 것을 DFS/BFS로 계산하여 안전 영역을 구한다 전체 코드 dx = (-1, 0, 1, 0)dy = (0, 1, 0, -1)result = 0def is_valid_coord(x, y).. [DFS/BFS] 특정 거리의 도시 찾기 문제링크https://www.acmicpc.net/problem/18352 해설최단거리니까 bfs로 풀자최단 거리가 정확히 K인걸 찾아야 하므로 최단거리가 K 미만인 도시는 지워줘야 함from collections import deque# N, M을 공백으로 구분하여 입력받기n, m, k, x = map(int, input().split())graph = [[] for _ in range(n+1)]for i in range(m): start, end = map(int, input().split()) graph[start].append(end)distance = [-1] * (n+1)distance[x] = 0 # 출발 도시의 거리는 0으로 설정q = deque([x])cnt = 0while q.. [DFS/BFS] 미로 탈출 문제링크이것이 코딩테스트다 연습문제 해설from collections import dequedx = (-1, 0, 1, 0)dy = (0, 1, 0, -1)def is_valid_coord(x, y):return 0 총평/느낀점항상 같은 flow로 DFS/BFS 문제를 푸는 연습을 해봐야 겠다 출처이것이 코딩테스트다 연습문제 [DFS/BFS] 음료수 얼려 먹기 문제링크- 이것이 코딩 테스트다 에서의 예제 문제이다 해설# 한 덩어리 찾고 다음 덩어리 찾고 ...# DFS 로 생각하는게 맞을 듯?dy = (0, 1, 0, -1)dx = (-1, 0, 1, 0)def is_valid_coord(x, y): return 0 총평/느낀점생각하는 과정이 아직도 어렵게 느껴진다.모두 다 이 과정에서 크게 달라지지 않는다는 것을 기억하자 출처이것이 코딩 테스트다 [DFS] 재귀 완벽히 이해하기 학습 내용코딩테스트에서 자주 등장하는 DFS/BFS를 이해하기 전 재귀에 대해 알아보고자 한다내가 이해할 수 있을 만큼 쉽게 설명해보고자 한다 재귀자기 자신을 다시 호출하는 함수 재귀함수 예제팩토리얼 예제# 반복적으로 구현한 n!def factorial_iterative(n): result = 1 # 1부터 n까지의 수를 차례대로 곱하기 for i in range(1, n+1): result *= i return result# 재귀적으로 구현한 n!def factorial_recursive(n): if n 최대 공약수 계산 (유클리드 호제법) 예제유클리드 호제법두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 하자이때 A와 B의 최대공약.. 정렬 학습내용정렬에 대한 내용을 전체적으로 정리해보고자 한다정렬 관련해서 코드 필요할 때 들어와서 확인하는 용도 다중 정렬def multisort(xs, specs): for key, reverse in reversed(specs): xs.sort(key=attrgetter(key), reverse=reverse) return xsmultisort(list(student_objects), (('grade', True), ('age', False))) 다중 정렬 문제 예시문제를 통해 이해하는 것이 더 쉬울 것 같아 문제를 추가한다 [백준] 국영수https://yeonco.tistory.com/31 파이썬 정렬 관련 참고 링크https://docs.python.org/ko/3/howt.. [Greedy] 그리디 가장 좋은 것만 선택하는 그리디‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 제시정렬 알고리즘과 짝을 이뤄 출제 그리디 알고리즘의 정당성대부분의 문제는 그리디 알고리즘을 통해 최적의 해를 찾을 수 없다문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 출처이것이 코딩테스트다 이전 1 2 3 다음 목록 더보기