본문 바로가기

🐍 Algorithm32

[알고리즘/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.

[알고리즘/Swift] 프로그래머스 - 위장 (해시) Python3 로 풀었던 문제를 Swift 로 다시 풀어봤어요. iOS 개발을 좀더 효율적으로 하기위해서 Swift 데이터구조, 알고리즘 공부의 필요성을 느꼈습니다. 🤔 '위장' 문제에 대한 접근 방법은 이전 포스팅을 참고해주세요~ [알고리즘/Python] 프로그래머스 - 위장 (해시) 서로 다른 옷의 조합의 수 구하는 법 👀 여러 의상끼리의 조합을 구하는 것이므로 곱집합을 생각했다. 곱집합 (데카르트 곱)은 각 집합의 원소를 각 성분으로 하는 튜플들의 집합으로 A x B 라고 jellysong.tistory.com ✔︎ Dictionary 를 이용한 풀이 방법 스파이가 가진 의상들이 담긴 2차원 배열 clothes 은 [의상의 이름, 의상의 종류] 형태로 되어있습니다. 여기서 의상의 이름은 중복되지 않.. 2021. 4. 16.

[알고리즘/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.

[Python] class, instance 속성, class 상속과 생성자 C++/Java에서의 Class와 차이점 클래스 instance 생성시 new 키워드가 없다. 함수호출과 같은 방식을 사용한다. 메소드 오버로딩이 없다. 메소드 오버로딩: 하나의 클래스에서 메소드 이름은 같고, 인자를 다르게 하는 형태 가변인자를 활용해 사용한다. 가변인자는 인자 앞에 *를 붙여서 사용 (함수참고) def add(self, *num) class 속성과 instance 속성을 구분해서 정의해줘야한다 C#, Java는 다중상속이 불가능하지만 python, c++은 다중상속이 가능하다. class 속성과 instance 속성 구분하기 class 속성은 class를 import한 후 사용할 수 있다. class 변수는 class 내부에서 정의해준다. class method 정의시 @classme.. 2020. 12. 7.

[Python] 데이터 타입 - List, Dictionary, JSON 데이터 타입 immutable과 mutable 은 변수가 담고 있는 object의 속성에 따라 달라지는 특성이다. 변수가 담고있는 object의 값을 변경 할 수 없는 데이터 타입은 immutable object 라고 부르며, 변수가 담고있는 object의 값을 변경 할 수 있으면 mutable object 라고 부른다. immutable object : int, float, bool, string, tuple mutable object : list, dictionary id(object) 함수는 object의 고유한 상수를 리턴한다. 리턴하는 값이 실제 메모리상의 주소는 아니지만, object마다 존재하는 고유값이다. 아래 예제는 immutable object, mutable object를 담고있는 변.. 2020. 12. 7.

이전 1 2 3 4 다음

티스토리툴바