일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- BFS
- 프로그래머스
- nlp
- 구글 킥스타트
- DFS
- 코딩
- OS
- 코딩테스트
- CSS
- dp
- 운영체제
- 브루트포스
- google coding competition
- 그래프
- 동적프로그래밍
- 백준
- PYTHON
- 코딩 테스트
- 파이썬
- linux
- 리눅스
- AI
- 킥스타트
- 프로그래밍
- 딥러닝
- kick start
- 알고리즘
- 동적 프로그래밍
- 순열
- 네트워크
- Today
- Total
목록알고리즘 (81)
오뚝이개발자
문제 https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b3771 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 간단한 구현 문제이다. NO를 출력하는 경우는 다음의 두 가지이다. S[i]=='C' and C==0 and i
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 DP를 사용해 쉽게 풀 수 있는 문제이다. input으로 주어진 각 수는 아래의 연산 중 한 가지를 할 수 있다. 2로 나누어 떨어지면 2로 나눈다. 3으로 나누어 떨어지면 3으로 나눈다. 1을 뺀다. 이를 반복해서 결과적으로 1이란 수를 만들어야 하는데, 이를 DP의 점화식과 연관지어 생각해보면 쉽다. 만약 내가 10이란 수를 input으로 받는다고 가정해보자. 10->5->4->2->1 10->9->3->1 10->9->8->7->...->1 위의 경우 말고도 10을 1로 만들기 위해선 굉장..
Greedy algorithm이란? 매 의사결정마다 정해둔 조건에 따라 가장 좋아보이는 답을 선택하는 것 Greedy algorithm(탐욕알고리즘)은 어디에 쓰이나? 주로 특정 제한조건(Constraints)을 만족해야 하는 상황에서의 최적화 문제에 사용 예) machine scheduling, bin packing, minimum spanning tree(MST) MST란? Spanning tree란 그래프의 모든 노드를 포함하는 트리이다. 이 때, MST란 edge의 가중치 합의 최소인 spannig tree이다. Shortest path problem(추후 자세히 포스팅) 다익스트라 알고리즘(Single source all destination) MST(각 방법별로 추후 자세히 포스팅) Krusc..
Divide and conquer(분할정복)이란? 다음의 세 단계를 거치는 알고리즘이다. Divide : large problem을 small subproblem으로 분할 Conquer : recursive하게 각 subproblem을 푼다 Combine : subproblem의 답을 조합해 large problem의 답을 구한다. D&C 사용 예시 [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다. 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할) ..
Sorting Bubble sort Selection sort Insertion sort Shell sort Quick sort Merge sort(분할->병합정렬) Heap sort 각 sorting 알고리즘의 시간복잡도는? Bubble - O(n^2) Selection - O(n^2) Insertion - O(n^2) Shell sort Quick sort worst : O(n^2) best : O(nlogn) avg : O(nlogn) Merge sort Heap sort Searching Linear search는 언제 쓰면 좋은가? item이 sorted 되어있지 않거나 unsortable할 때 Linear search의 단점? 찾는 아이템이 없거나 뒤쪽에 있는 경우 비효율적 Binary sea..
알고리즘의 효율성 측정 방법 basic operation(dominant operation)을 기준으로 하여 input size n에 따른 함수 T(n)으로 실행시간을 나타낸다.(Asymptotic algorithm analysis) Growth rate란? input size가 증가함에 따라 algorithm의 cost가 증가하는 비율 Linear Growth T(n) = n, Quadratic Growth T(n) = n^2 Big-O란? lowest upper bound
문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 � www.acmicpc.net 생각의 흐름 사실 혼자 힘으로 풀지 못해 블로그를 많이 참고해서 구현하였다. 참고한 블로그는 https://rebas.kr/770이다. 위 블로그에 드러나지 않은 부분을 설명하겠다. bfs함수의 for문 안에서 '.'인 경우 appendleft를 해주고 '#'인 경우 그냥 append를 해주는데 이유는 '.'인 경우를 우선적으로 처리하도록 하기 위함이다. 왜냐하면 '.'와 연결된 경우는 문을 부수지 ..
문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 생각의 흐름 수빈이가 X에 있을 때 이동가능한 경우의 수는 X-1, X+1, 2X의 세가지이다. 가능한 경우는 이 세가지이므로 수빈이의 위치를 q에 넣고 이들을 pop하면서 BFS로 탐색을 해주면 된다. 이 때, pop을 했을 때 원소가 K와 같은 값이면 탐색을 종료한다. 방문을 체크하기 위해서는 visit이라는 1차원 리스트를 사용하였다. 리스트에는 ..