kakasoo

// 백준 1260번 DFS와 BFS를 풀었습니다. const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const input = []; let n = 0; let m = 0; let start = 0; rl.on("line", (line) => { if (!n) { [n, m, start] = line.split(" ").map(Number); } else { input.push(line); if (input.length === m) { main(); process.exit(); } } }); const dfs = (start) =>..

C언어를 다룰 때 가장 힘든 것이 동적할당이었다. 동적할당을 처음 배울 당시, 나는 프로그래밍을 마치고 동적할당을 해제하지 않으면, 컴퓨터의 자원을 영영 잃어버리는 것이 아닐지, 그 부분에 대해서 두려움을 가졌다. 당연히 지금은 운영체제가 그런 부분을 자동적으로 처리해준다는 것을 알고 있다. 하지만 그 사실을 몰랐던 나는, 동적할당을 의사가 환자 다루듯 신중하게 해야 했다. 도달 가능성 Mark-and-Sweep 알고리즘이 있다. 이는 말하자면 DFS, BFS와 유사하게, 도달가능한 모든 영역을 탐색하는 알고리즘이다. 나중에 다른 포스팅에서 말하겠지만, JavaScript는 다양한 Enviorment를 Context로 가진다. Mark-and-Sweep 알고리즘은 이 환경 중 맨 처음에 위치할 전역 환경..

발상 자체가 조금 까다로운 문제이다. (그런 줄 알았는데, 내가 문제를 잘못 읽었다.) 상근이 ( 또 상근이야? )는 여러 나라를 여행할 건데, 최소한의 비행기만을 타고자 한다. 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..

숫자가 예쁜 문제다, 14500번. 일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다. 간단히 문제를 요약하건대, 아무 숫자가 적혀져 있는 2차원 배열이 주어질 때, 그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서 테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다. 고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상, dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데, bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다. 그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다. 다만 dfs의 경우에..

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..

오랜만에 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) 중간에 틀린 걸 판별했다면? -> ..