분류 전체보기
-
알고리즘: 백준 1697번 숨바꼭질 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 14:40
백준 1697번 링크입니다. 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net bfs를 이용하면 문제가 생각보다 쉽게 풀린다. 최대 가능 인풋이 100000이기 때문에 시간복잡도가 최대 n^2 까지 가능하다고 생각하였다. 최단거리 문제이기도 해서 bfs를 선택하였다. #include #include using namespace std; int visit[100001]; bool check(int x) { //check 함수가 중요한듯! if (x 100001) ret..
-
알고리즘: 백준 2667번 단지번호붙이기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 22. 11:38
백준 2667번 링크입니다. 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net bfs 너비 우선 탐색을 이용하여 단지수를 찾는다. 방문한 집은 방문처리를 함으로써 반복문을 이용해 모든 집을 방문하면서 방문처리가 되어있는 주택은 패스, 방문하지 않은 집은 bfs를 시행한다. 총 단지수를 받을 house와 방문한 곳을 표시하는 visit을 만들었다. 방문했으면 visit의 해당하는 인덱스에 1을 집어 넣고, 아니면 0을 넣는다. bfs하기 전, 초기 visit[y][x] 값은 house[y][x]가 0 일때 1, ..
-
메모: 파이썬 알고리즘 1차 강의 메모메모 및 기타 2020. 8. 20. 21:09
1. 문자열 역으로 출력하기 s = input() print(s[::-1]) 2. 시간복잡도 O(root(n)) 으로 소수판별하기 import math x = int(input()) answer = False if x % 2 == 0 and x != 2: answer = False else: for i in range(2, int(math.sqrt(x)) + 2): if x % i == 0: answer = False break else: answer = True print(answer) 3. 최대값구하기 3 4 1 7 9 2 2 7 9 6 1 9 5 7 3 9 # -*- coding: utf-8 -*- # UTF-8 encoding when using korean n = int(input()) numb..
-
알고리즘: 백준 1010번 다리놓기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 19:00
백준 1010번 링크입니다. 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net n개 중에 r개를 고르면 되므로 nCr을 사용하면 간단하다...고 생각했지만 아니였다. 팩토리얼을 다이나믹 프로그래밍으로 구해서 콤비네이션하려 했지만 long long 자료형을 써도 넘어가버려서 다이나믹 프로그래밍과 재귀함수를 이용하였다. nCr = n-1Cr-1 + n-1Cr 을 이용해서 recursive form을 만들어 해결하였다. #include using namespace std; int cache[30][30]; // 다이..
-
알고리즘: 백준 1018번 체스판 다시칠하기(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 16:28
백준 1018번 링크입니다. 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net B로 시작하는 8 x 8 완성된 체스판을 chess1 W로 시작하는 8 x 8 완성된 체스판을 chess2 내가 입력받을 잘못된 체스판을 wrong_chess라고 하자 wrong_chess의 행과 열을 변화시켜 가면서 chess1과 chess2와 비교한다. chess1과 비교했을 때 잘못된 값의 갯수 = wrong_count1 chess2과 비교했을 때 잘못된 값의 갯수 = wrong_count2일때 두 값중에 더 작은 값을 ..
-
알고리즘: 백준 1037번 약수(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 14:35
백준 1037번 링크입니다. 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 방법 1 #include using namespace std; int main() { int n; int x; int max = -1; int min = 1000000; cin >> n; for (int i = 0; i > x; if (max x) { min = x; } } int answer = min * max; cout n; for (int..
-
Python: 견고한 객체지향 프로그래밍 SOLID 설계원칙 공부하기!Python 2020. 8. 16. 21:26
SOLID 원칙이란? Solid 원칙이란 로버트 마틴이 개발한 객체 지향 프로그래밍 및 설계의 다섯가지 원칙을 말합니다. 프로그래머가 시간이 지나도 유지보수와 확장이 쉬운 시스템을 만들고자할 때 이 원칙들을 함께 적용할 수 있습니다. Solid 원칙은 각 원칙들의 첫 글자를 따서 만들어졌는데 다음과 같이 나뉩니다. Single responsibility principle 단일 책임 원칙 Open/closed principle 개방-폐쇄 원칙 Liskov substitution principle 리스코프 치환 원칙 Interface segregation principle 인터페이스 분리 원칙 Dependency inversion principle 의존관계 역전 원칙 순서대로 알아봅시다. 1. 단일 책임 원..
-
Python: 객체 지향 프로그래밍을 위한 4가지 기본개념 (상속, 추상화, 캡슐화, 다형성)2Python 2020. 8. 16. 16:09
이번 포스팅은 전 포스팅에서 못 다룬 캡슐화와 다형성에 대해서 공부해봅시다. 상속과 추상화에 관한 내용은 아래에 있습니다. Python: 객체 지향 프로그래밍을 위한 4가지 기본개념 (상속, 추상화, 캡슐화, 다형성)1 객체 지향 프로그램을 다루기 위해서는 알아야 할 4가지 기본개념에 대해 알아봅시다. 크게 4가지로 나뉩니다. 상속 추상화 캡슐화 다형성 하나씩 차례로 알아봅시다. 재산상속할때 그 � seungjuitmemo.tistory.com 캡슐화란 인스턴스를 생성했을 때 일부 구현 내용에 대한 외부로부터의 직접적인 엑세스를 차단하는것입니다. 쉽게 말해서 캡슐처럼 객체 내부를 숨겨 외부로부터의 엑세스를 차단하는 것입니다. 객체 내부를 숨기는 법은 크게 두가지가 있습니다. 첫번째는 언더바 ..