본문 바로가기

🐍 Algorithm/알고리즘-Python18

[알고리즘/Python] BOJ 1543 문서 검색 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 💡 완전탐색(exhaustive search) 문제에 쓰여진 대로 구현하는 문제이다. 실수 없이 빠른 시간안에 잘 짜야 쉬운 문제들을 풀어나갈 수 있다. ✔︎ 첫 번째 풀이 문서에서 특정 단어를 중복되지 않고 검색해서 총 몇 번 나타나는지 구하기 입력 : 문서(document), 단어(word) 출력 : 문서에 중복되지 않고 나타나는 단어의 개수 문서의 전체를 반복하며 단어가 나타는지 확인했다. 단어가 나타나는 경우, 그 구간에서는 단어를 찾을 수 없으므로 인덱스(i.. 2021. 4. 22.

[알고리즘/Python] BOJ 1182 부분수열의 합 👉 1182 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 👀 접근 :: N개의 정수로 이루어진 수열의 부분 수열 중에서 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다. 백트래킹 문제임을 알고 접근했기에 DFS 로 깊이 탐색을 하면서 조건을 체크했다. 백트래킹? 트리 구조를 기반으로, DFS 로 깊이 탐색하면서 각 루트에 대해 조건을 체크한다. 만약, 해당 트리에 조건이 맞지 않으면 해당 트리 탐색을 종료한다. ✔︎ 문제 풀이 방법 부분 수열은.. 2021. 4. 21.

[알고리즘/Python] 프로그래머스 - 위장 (해시) 서로 다른 옷의 조합의 수 구하는 법 👀 여러 의상끼리의 조합을 구하는 것이므로 곱집합을 생각했다. 곱집합 (데카르트 곱)은 각 집합의 원소를 각 성분으로 하는 튜플들의 집합으로 A x B 라고 한다. 곱집합의 개수는 간단하게 A x B 로 계산할 수 있다. 해당 문제에서는 자기 자신만을 갖는 경우도 포함되어야 하기 때문에 (A+1) x (B+1) - 1 로 계산했다. 1 을 빼주는 이유는 (A+1) x (B+1) 의 경우에는 비어있는 경우도 포함되기 때문이다. 기존 리스트 = [a], [b], [c] 최종 결과 = [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c] 풀이1 (시간초과) solution 함수 clothes : 스파이가 가진 의상들이 담긴 2차원 배열 r.. 2021. 3. 11.

[알고리즘/Python] 프로그래머스 - 네트워크 (DFS) 풀이1 solution 함수 n : 컴퓨터의 개수 computers : 연결에 대한 정보가 담긴 2차원 배열 return : 네트워크의 개수 dfs 함수 graph : computers v : 현재 index visited : 방문처리를 위한 1차원 배열 자세한 풀이 연결되지 않은 네트워크가 있을수도 있으므로 index 를 n 만큼 반복하며 dfs 함수를 호출한다. 처음 방문하는 경우에는 새로운 네트워크가 시작되는 것과 같다. count 를 증가시킴 현재 index 를 방문처리 시킴 이미 방문처리 되어있다면 네트워크가 연결되어 있으므로, count하지 않음 graph 를 반복하며 방문하지 않은 노드에 대해 방문처리, dfs 재귀호출 count = 0 def dfs(graph, v, visited): gl.. 2021. 3. 6.

[알고리즘/Python] 프로그래머스 - 타겟 넘버 (DFS) 풀이1 DFS 를 어떻게 이용할지 감이 안와서 비효율적으로 풀어버렸다. 가능한 케이스를 전부 고려해서 구현 itertools.product 이용해서 곱집합 구하기 solution 함수의 파라미터와 리턴값은 다음과 같다. numbers : 사용할 수 있는 숫자가 담긴 배열 target : 타겟 넘버 return : 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 자세한 풀이는 다음과 같다. product 함수를 통해 가능한 case 구하기 (cases 예시는 그림 참고) 덧셈과 뺄셈 연산을 할 수 있으므로 [-1, 1] 을 곱하는 값이라고 생각했다. length 만큼 반복하며 case[i] * numbers[i] 를 더한 값이 target 과 같으면 count 를 증가시켰다. from iterto.. 2021. 3. 6.

[알고리즘/Python] BOJ 1158 - 요세푸스 문제 (기초 자료구조) 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. 풀이1 단순히 리스트를 사용해서 풀었다. index와 target 변수를 지정해 리스트에서 target 을 제거하고, 다시 현재위치에서 k번째 사람이 제거될수 있도록 index 를 변경시켰다. # BOJ-1158.py from sys import stdin input = stdin.readline n, k = map(int, input().split()) nums = list(range(1, n+1)) result = [] target = k while(True): index = nums.index(target) nums.remove(target) result.append(target) .. 2021. 3. 6.

[알고리즘] Day3 - 1967번 트리의 지름 00 문제 01 트리의 지름?트리는 사이클이 없는 무방향 그래프이며, 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재한다.트리에서 어떤 두 노드를 선택해서 양쪽으로 당기면, 가장 길게 늘어나는 경우가 있다.이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히는 트리에 존재하는 모든 경로들 중 가장 긴 경로의 길이를 말한다.가장 먼 두 정점 사이의 거리 or 가장 먼 두 정점을 연결하는 경로를 의미한다. 02 트리의 지름을 구하는 방법트리에서 임의의 정점 x를 잡는다.정점 x에서 가장 깊은 노드 중 가중치가 가장 큰 정점 y를 찾는다. -> DFS 이용정점 y에서 가장 깊은 노드 중 가중치가.. 2018. 8. 8.

[알고리즘] Day3 - 2309번 일곱 난쟁이 00 문제 01 아이디어9개 중에 순서대로 7개를 뽑아서 100이 되는지 확인하고 result 배열에 저장한다.insert sort를 이용해 정렬해 오름차순으로 출력한다.1234567 1234568 1234569 1234578 1234579 요런 순서 02 코드 #define scanf scanf_s#include "stdafx.h"#include #include #define N 9void find_seven_dewarf(int *height, int *result);void insertion_sort(int N_, int *num);int main(){ int i; int height[9] = { 0, }; int result[7] = { 0, }; for (i = 0; i < 9; i++) scan.. 2018. 8. 8.

[알고리즘] Day3 - 1260번 DFS와 BFS 00 문제 01 DFS 알고리즘?Depth First Search, 깊이 우선 탐색이라는 뜻.하나의 노드에서 시작하여 마지막 지점까지 계속 탐색하는 행동을 하는 알고리즘즉, 시작점을 기준으로 가장 아래까지 이동하면서 탐색하는 방식 -> 스택을 이용하여 푸는 방식스택에 값을 넣어주고, 그 값을 통해 확인하며 종료 조건은 스택이 비어있을 때이다.DFS의 장점은 깊은 곳에 있을수록 빨리 찾아낼 수 있다는 점단점은 자칫하면 overflow가 날 수도 있고, 얻어진 해가 최단 거리라는 보장이 없다. 02 DFS 알고리즘 구현 방식인접한 노드들을 표현하기 위해 NxN 크기의 adj_mat 배열과 방문한 노드를 표현하기 위해 Nx1 크기의 visited 배열을 사용한다. add_matrix 함수에서 연결된 노드를 입.. 2018. 8. 8.

이전 1 2 다음

티스토리툴바