일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 카카오 면접
- Python
- 기술면접
- 2629
- 정상회담2
- 카카오 인턴
- 백준
- 개발자 면접
- 여름인턴십
- DP
- 인턴십 면접
- 2228
- 파이썬
- 구간나누기
- 알고리즘
- 카카오 자기소개서
- Longest Increasing Subsequence
- 최장증가수열
- 백준12015
- 단어수학
- 1670
- 백준12738
- LIS 알고리즘
- 2482
- 카카오
- 카카오 인턴십
- 백준11053
- 카카오 서류전형
- 가장긴증가하는 부분수열
- LIS
- Today
- Total
목록알고리즘 (31)
프로그래밍에 대한 고찰 및 생각

올해로 20살이된 민수는 코로나 여파로 겨울방학임에도 불구하고 집에서 나갈 수 없어 옛 추억을 떠올리며 오랜만에 스타크래프트 게임을 시작했다. 평소에 프로토스 종족을 좋아하던 민수는 부푼마음으로 게임을 시작했지만 너무 오랜만에 하는 탓에 지어야 할 건물들의 순서를 몰라 난관에 부딪혔다. 스타크래프트 라는 게임에서는 각 종족마다 많은 건물들이 존재한다. 그러나 이러한 건물들을 게임을 처음 시작하면 바로 건설할수 없는 건물들이 있으며 이 건물들은 지정된 다른 건물들을 먼저 선행으로 건설해야 건설할 수 있다. 예를 들어 0번 건물을 짓기위해서는 1번건물을 지어야한다. 그런데 1번 건물을 지으려면 2번 건물을 지어야한다. 즉 2->1->0 의 순서로 건물을 지을 수 있다. 위와같은 건물의 순서도를 참고해서 10..

너비 우선 탐색 BFS (Breadth-First Search) 너비 우선 탐색 (이하 BFS) 는 시작 정점에서 방문할 수 있는 정점들을 우선 방문한후, 이후에 그 정점들에서 방문 할수 있는 정점들을 방문 하는 탐색 방법이다. 예를 들어 위와같은 그래프에서 0번 정점으로 부터 BFS를 시행한다고 하면 ( 방문할수 있는 정점이 여러개라면 번호가 낮은 정점을 우선 방문한다고 가정 ) 이전의 DFS에서는 1번 정점을 방문한뒤, 1번 정점에서 방문할 수 있는 2번 정점을 방문하였지만 BFS에서는 1번 정점을 방문한뒤, 바로 9번 정점을 방문한다. 이후 1번 정점에서 방문할 수 있는 2,5,7번 정점을 방문한 후, 9번 정점에서 방문할 수 있는 정점을 방문한다. ( 위 그래프 상황에서는 이미 9번과 연결된 7번..

깊이 우선 탐색 DFS (Depth-First Search) 깊이 우선 탐색(이하 DFS)은 하나의 정점에서 시작해서 그래프를 탐색 하는 방법중 하나로 한 정점에서 갈수있는 정점을 방문하고 해당 정점에서 갈수 있는곳을 계속해서 방문하여 더이상 방문할 정점이 없을때까지 방문하는 방법이다. 쉽게생각해서 미로탈출 게임을 할때 만약 세가지 갈림길이 나왔을 때, 셋중 하나를 골라서 끝까지 진행해본후 막혀있다면 다시 원점으로 돌아와 다른 길로 가는 것과 같이 생각하면 될것이다. 다음과 같은 방향이 없는 그래프로 생각해보자. 0번 정점에서 시작해서 DFS를 수행하는 과정은 다음과 같다. 이번 DFS에서는 현재 정점에서 갈 수 있는 정점들 중 가장 번호가 낮은 정점부터 방문한다고 가정하자. 0번 정점에서 처음에 갈수 ..

그래프(Graph) 란? 그래프는 어떤 자료나 개념을 각각의 정점들(vertex)의 집합 V와 그 정점들을 이어주는 간선들(edge)의 집합 E로 구성된 자료 구조이다. 이러한 그래프는 크게 두가지로 표현이 가능하다. 1. 인접 리스트 표현 2. 인접 행렬 표현 1. 인접 리스트 표현 첫번째로 그래프를 표현할 수 있는 방법은 인접 리스트 이다. #include #include using namespace std; int main(){ vector v; for(int i=0;i

문제 이해 토마토 문제에서는 각 박스내에 3가지 상태가 존재한다. 익은 토마토(1), 안익은 토마토(0), 비어있는 칸(-1). 주의할 점은 익은 토마토는 자신의 상하좌우에 위치한 토마토만을 익힐 수 있고, 비어있는칸이 존재할 수 있기때문에, 문제의 예제2 처럼 모든 토마토를 전부 익힐 수 없는 상황이 주어질 수도 있다는 점을 고려해야한다. 알고리즘 설계 문제에서 주어진 예제3의 경우를 시각화했을 때의 모습이다. 간단하게 생각해보면, 1. 현재 익은토마토(1)의 상하좌우의 토마토들의 상태를 1로 바꾼다. 2. 현재 익은토마토들 주변에 익힐수 있는 토마토가 없을 경우 종료 / 아닐 경우 1 반복 로 표현할수 있다. 그런데 현재 익은 토마토의 개수는 매번 달라지므로 일반적인 재귀함수로 표현하기는 힘들것 같다..

알고리즘 설계 문제에서 주어지는 n명의 그림 소유상태를 비트마스킹으로 표현하고 DP를 이용해서 해결할수 있는문제이다. 만약 비트연산을 처음 들어봤다면 비트연산을 먼저 공부하고 오는 것을 추천한다. 전체 코드는 다음과 같다. #include int n; int pp[16][16]; int dp[15][32768] = {0}; int ddp(int state, int before, int price); int max(int x, int y); int main(){ int i,j; scanf("%d",&n); for(i=0;i

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 0/1 배낭 문제 (0/1 knapsack problem) 에 대해 알아보자. 0/1 배낭 문제 ( 0/1 Knapsack Problem) 0/1배낭 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수 없고 담거나 담지 않거나 둘중 한가지를 택해야한..

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 배낭을 빈틈없이 채우는 문제에 대해 알아보자. Fraction Knapsack Problem 배낭 빈틈없이 채우기 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수도 있다. 예를 들어 무게가 10이고 가치가 20인 물건 A를 절반만 담으면 무게가 ..