일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 자바스크립트
- socket
- ip
- TCP
- HTTP 완벽 가이드
- 프로그래머스 레벨 2
- 타입스크립트
- Node.js
- 그래프
- 알고리즘
- Nestjs
- 가천대
- 문자열
- javascript
- 소켓
- 쉬운 문제
- Crawling
- dfs
- HTTP
- Algorithm
- 타입 챌린지
- 크롤링
- type challenge
- 레벨 1
- dp
- typescript
- 수학
- 프로그래머스
- BFS
- 백준
- Today
- Total
목록알고리즘 (82)
kakasoo
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 #include #include using namespace std; int a[100]; int b[100]; int main(void) { int n; cin >> n; for (int i = 0; i > a[i]; } for (int i = 0; i > b[i]; } sort(a, a + n); sort(b, b + n); int sum = 0; for (int i = 0; i
문제 이름은 쉬운 계단 수인데, 사실 쉽지 않다, 저기 정답 비율만 봐도 28.216%지 않은가. 물론 DP에 능숙해졌다면 몇 번의 시행 착오만 겪어도 풀 수 있는 문제긴 하겠지만. 자세한 설명은 코드를 먼저 보여준 다음에 이어 나가는 게 좋을 거 같다, 주석을 달아 놨으니. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include using namespace std; long long int dp[101][10..
발상 자체가 조금 까다로운 문제이다. (그런 줄 알았는데, 내가 문제를 잘못 읽었다.) 상근이 ( 또 상근이야? )는 여러 나라를 여행할 건데, 최소한의 비행기만을 타고자 한다. A에서 B로 가는 비행기가 있다고 할 때, B에서 A로 가는 비행기는 한 종류로 취급한다. 상근이가 모든 나라로 여행을 가면서도 최소한의 비행기를 타려면 몇 번의 비행기를 타야 하는가? 여담이지만, 모든 나라를 돌면서도, 실패할 경우에 무엇을 출력하라는 말이 없는 것을 보니 test case로, 모두 성립할 수 있는 경우의 수만을 주는 것으로 보인다. 그럼 당연히 국가의 수 - 1이 정답이겠지 (...) 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 2..
상근이는 1번을 학번으로 가지고 있다. 또한 상근이를 포함해 n번까지의 학생이 있고, 우리는 그 인간관계 m개를 받아서 서로의 친구 관계에 대해서 파악해볼 것이다. 만약 1번과 2번이 친구고, 2번과 3번이 친구라면 1번과 3번 역시 자동으로 친구다. 한 마디로 같이 노는 그룹 전체를 친구라고 한다는 것이다. (가운데 한 명 빠지면 어색해지는 사이라고 해도.) 나는 이것을 bfs 방식으로 풀었다. bfs의 매개변수에 상근이의 학번을 전달한 다음에, 방문 여부를 모두 체크해서, 방문할 수 있었던 모든 학번에 대하여 친구라고 가정하여 출력한다. 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 32 33 34..
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; int n, s, sum, counted; int arr[21]; bool visited[21]; void dfs (int start) { visited[start] = true; int cur = start; sum += arr[start]; if (sum == s) { counted++; } for (int i = start + 1; i > n >> s; for (int i = 0; i > arr[i]; for (i..
어려웠다. 어떻게 접근해야 할지 고민하다가 알아낸 것이, 전깃줄이 교차되는 경우의 수였다. 예제의 1부터 10까지의 전봇대를 생각해볼 때, 1부터 10까지를 배열의 index처럼 취급할 수 있을 것이다. 만약 이 index가 더 후위에 있다면, 이 인덱스에 해당하는 배열의 값도 더 후위에 있어야 한다. 즉 1이 3으로 연결되어 있다면 2부터 10까지는 적어도 4 이상과 연결되어 있어야 1과 교차하지 않는다. 그러나 문제가 생기는 것이 바로 0이었다. 만약 1이 0이라고 한다면 2 ~ 10까지는 1이상과 연결되어도 되는 것이니 아무런 문제가 없다. 그러나 만약 index 2가 0이라고 한다면, 사실 index 2는 값과 무관하게 항상 앞전과 교차할 일이 없어야 하겠지만, 컴퓨터는 이 0을 0이라는 전봇대와..
그리디 알고리즘 (탐욕 알고리즘)이라고 하는데, 비슷한 종류의 문제들 중에 이게 가장 수준이 높았던 거 같다. 그리디 알고리즘은, 솔직히 나는 이런 거에 알고리즘이라는 말을 붙일 필요가 있나 싶을 정도로 간단했다. 그 순간 순간의 최적해를 쫓아 가서, 근사값을 구하는 방식의 알고리즘이라는 건데, 당연 그 순간의 최적해를 쫓을 때 최종적인 답안이 최적해가 아닐 수도 있다. 말하자면, 지금 알고리즘 조건에 따라서, 이렇게 설명할 수 있겠다. 2일 간격으로만 음식을 먹을 수 있고, 더 적은 음식을 먹어야할 때, 첫날 음식을 먹느냐 둘째날 음식을 먹느냐, 첫날과 둘째날을 비교해서 작은 쪽을 먹는다는 게 그리디의 방식이지만, 만약 셋째날이 무한대에 수렴한다면 다시 처음으로 돌아가 두번째를 먹는 것을 고르는 것이 ..
오랜만에 bfs 문제를 풀었다. 하도 안 보던 알고리즘을 푸니까 머리가 돌아버릴 거 같아서 일부러 bfs 문제를 풀었다. 역시 완벽하게 이해가 된 알고리즘은, 손이 알아서 치고, 이게 또 너무 재밌다. 음악을 즐긴 적은 없지만 무작정 피아노를 두들기는 사람들이 이런 기분이었을까. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 8..
알고리즘 구분 알고리즘을 공부하며 가장 헷갈린 것이, 알고리즘의 이름이 무얼 의미하는지 몰랐던 부분이었다. n-Queen 문제를 풀 때도, 풀이를 보고 신기했던 경험이 있었지만 백트래킹에 대한 이해는 얕았다. 그러나 그것이 스도쿠 문제를 풀면서 완전한 이해로 갖춰지게 된 거 같다. 일단 기본적으로, 브루트 포스가 있다. 브루트 포스는 for문이든 중첩된 for문이든 간에 모든 경우의 수를 다 찾아보는 방식이다. 이 브루트 포스에서 방문한 칸을 체크하는 것으로 효율을 꾀하는 것이 dfs와 bfs로 나타난다. 그러나 dfs는 갈래의 마지막까지 방문한 다음에 옳고 그름을 판단하는데, 다음의 문제가 있다 1) 만약 재귀가 끝나지 않는다면? -> 런 타임 에러가 발생한다. 2) 중간에 틀린 걸 판별했다면? -> ..
일단 첫번째로 올린 코드는 잘못된 코드다. 46%에서 시간초과로 끝나는 것을 확인할 수 있다, 이전 이분 탐색 문제에서는 내가 제시한 방법으로 시간초과를 해결했지만 이 문제에서는 같은 방법으로 해도 46%까지 밖에 안 되는 거로 보아 더 획기적인 해결 방법이 필요한 듯 하다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 ..