본문 바로가기
반응형

전체 글181

[백준] N과 M (1) 15649 (파이썬) 문제 접근 n 개중에서 m개를 뽑는데 순서를 고려해서 뽑는다 = 순열 문제 파이썬 라이브러리를 사용해서 쉽게 풀었다. 2021.03.15 - [Algorithm & Data structure] - [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutati seongbindb.tistory.com 코드 # N과 M from itertools import permutations n,m = map(int,i.. 2021. 3. 19.
[백준] 수 찻기 1920 (파이썬) 문제접근 어떤 수열에서 특정 값이 있는지 없는지를 찾는데 수가 크다면 이진탐색을 고려해 봐야했다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 이진탐색 (이분탐색) # 수 찾기 import sys input = sys.stdin.readline def binary_search(start, end, target, arr): while start 2021. 3. 19.
[항해99] 알고리즘 복습 2021. 3. 19.
[파이썬] print() 원하는 양식으로 출력하기 (백준 11866 요세푸스 문제) 출력 원하는 방식으로 출력해야 할 때 필요한 코드들이다. 백준 11866 요세푸스 문제를 풀 때 막힌 부분이 출력이어서 정리한다. 2021.03.16 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 요세푸스 문제0 11866 (파이썬) [백준] 요세푸스 문제0 11866 (파이썬) 스케치 코드 기본적으로 큐를 활용해서 문제를 풀면 되지만 K번째 값을 뽑는 도중 Q가 K보다 작아지게 될 때를 유의하여 처리하여야 한다. Q < K 작은 구간은 나눗셈으로 인덱스를 뽑아서 구현하 seongbindb.tistory.com # Python 3.6 이상 # 로 출력하고 싶을 때 arr = [1,3,5,7,9] print(f"'{arr}를 양식에 맞게 출력합니다'") # '[1, 3,.. 2021. 3. 18.
[백준] 곱셈 2588 (파이썬) 문제접근 1안: 방식은 음 뭔가 복잡하다 2안: 문제 조건이 3자리 자연수를 입력값으로 준다고 명시돼 있으므로 쉽게 풀 수 있다 # 곱셈 a = int(input()) b = input() b = list(b) b.reverse() zero = '' arr = [] for i in b: c = str(a*int(i)) arr.append(c+zero) zero = zero + '0' print(a*int(i)) total = 0 for j in arr: total = total + int(j) print(total) # 2안 # 문제 조건이 3자리 자연수를 준다고 명시돼 있으므로 조금더 쉽게 풀 수 있다. n = int(input()) m = int(input()) m = str(m) print(n * .. 2021. 3. 18.
[항해99] 알고리즘 문제 유형 정리 (03-19 최신화) 수학 사칙연산 10869 (브론즈5) 52.622% 곱셈 2588 (브론즈4) 51.513% 알람시계 2884 (브론즈3) 39.168% 더하기 사이클 1110 (브론즈1) 48.102% 평균은 넘겠지 4344 (브론즈1) 37.371% 셀프 넘버 4673 (브론즈1) 50.276% 달팽이는 올라가고 싶다 2869 (브론즈1) 26.831% ACM 호텔 10250 (브론즈3) 34.605% 소수 구하기 1929 (실버2) 27.372% 암호 만들기 1759 (골드5) 44.837% 설탕 배달 2839 (브론즈1) 32.830% Fly me to the Alpha Centauri 1011 (실버1) 29.486% 베르트랑 공준 4948 (실버2) 29.486% 약수 1037 (실버5) 49.806% 최대공.. 2021. 3. 18.
[백준] [백트래킹] N-Queen 9663 (파이썬) 문제 접근 처음 보는 유형이 었고 공부를 해도 잘 몰라서 유투브 '코드랩' 님의 백트래킹 강의를 참조하였다 백트래킹 기본 개념 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 백트래킹 [알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대 seongbindb.tistory.com 코드 # N - Queen # 참조 코딩랩 import sys input = sys.stdin.readline def queen(row, col): for i in range(row): #.. 2021. 3. 17.
[백준] [다익스트라 알고리즘] 최단경로 1753 (파이썬) 문제접근 주어진 V E의 범위가 큰 편이기 때문에 시간 복잡도를 고려했을 때 다익스트라 알고리즘을 적용해서 풀어야 한다고 파악했다. 또한 특정지점 (주어진 시작점)에서 다른 지점으로 까지 가는 최단 경로를 구하기 때문에 모든 정점에 대해 최단 경로를 알 수 있는 플루이드 워셜 알고리즘 시간복잡도와 문제를 보았을 때 적합하지 않았다. 최단 경로 알고리즘에 대해 정리한 글을 참조하면 도움이 될 것 같다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘.. 2021. 3. 17.
[Blog] 구글 애드센스 (애드고사) 합격 구글 에드센스 합격 2월 말 부터 꾸준히 블로그에 포스팅을 하고 있고 방문자 수도 늘고 있어서 다시 한 번 애드고사를 신청했었다. 유투브를 비롯해서 무언가 내 사이트를 이렇게 꾸준히 한 적은 처음이었다. 수익을 바라고 블로그를 하는 것은 아니지만 나의 블로그가 광고를 할 정도로 가치 있는 게시물이 있는지를 판단 할 수 있는 좋은 지표, 글을 계속 쓰게 되는 원동력이 될 것 같아서 신청을 했다. 일주일 정도 시간이 지난 뒤에 애드센스 광고를 게시할 수 있다는 메일이 도착했다 ^ ^ 에드핏 보다는 애드센스가 수익이 좋다고 한다. 수익이라 하기 부끄럽지만 지난 3개월 간 쓰레기 봉투값 정도 번 나의 애드핏 수익을 공개한다. 방문자수가 얼마전에 1000명을 돌파했는데 앞으로도 꾸준히 올려서 많은 사람들에게 도움.. 2021. 3. 17.
[알고리즘] 정렬 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬) 정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 이진 탐색을 하기위한 전처리과정 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 다뤄보자 선택 정렬 O(N^2) 가장 작은것을 선택하여 맨 앞과 바꾼다 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택정렬 소스코드에 익숙해지자 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스, i번째 인덱스와 바꿀 가장 작은 인덱스를 찾는다. for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index =j array[i], array[min_inde.. 2021. 3. 17.
[알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대표적인 문제는 N-Queen이 있다. 2021. 3. 17.
[알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘 O(ElogV), O(V^2) 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 0 보다 작은 간선이 없을 때 이용된다 매 상황마다 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘에 속한다. 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3번과 4번을 반복한다. 특징 각 노드에 대한 현재까지의 최단 거리 정보를.. 2021. 3. 17.
[백준] [다익스트라] 최단경로 1753 (파이썬) 문제접근 특정한 지점(start) 값이 주어지고 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 적용하여 문제를 푼다. 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘 $O(ElogV), O(V^2)$ 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출 seongbindb.tistory.com 스케치 코드 # 최단 경로 , 다익스트라 알고리즘 사용 import heapq import sys input = sys.stdin.readline .. 2021. 3. 17.
[백준] 단지번호붙이기 2667 (파이썬) 문제설명 기본적인 아래와 같은 DFS 문제와 거의 유사하지만 추가해야 하는 조건이 있다. 2021.03.14 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] [우선탐색] DFS와 BFS 1260 (파이썬) [백준] [우선탐색] DFS와 BFS 1260 (파이썬) 개념 2021.03.07 - [Algorithm & Data structure] - [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을.. seongbindb.tistory.com 스케치 코드 # 단지 번호 붙이기 def dfs(x,y): global temp if x = n or y = n:.. 2021. 3. 16.
[백준] [분할정복] 쿼드트리 1992 (파이썬) 문제설명 아래 색종이 만들기 문제와 아주 유사한 문제였다. 부분적인 조건만 추가해서 DFS 방식으로 풀어주면 된다. 2021.03.15 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 색종이 만들기 2630 (파이썬) [백준] 색종이 만들기 2630 (파이썬) 코드 # 색종이 만들기 # 쿼드 트리 문제 # 처음 리스트를 쪼개서 작은 리스트를 만드려고 했는데 이방식은 어리석은 방식이었다. 전체에서 범위만 제한해서 원하는 부분에 접근할 수 있다. import s seongbindb.tistory.com 코드 # 쿼드트리 import sys def quadTree(x,y,size): # 전체 갯수를 센다. color = matrix[x][y] if (size == 1): pr.. 2021. 3. 16.
반응형

티스토리툴바