Algorithm

백준 1697번: 숨바꼭질 (javascript, bfs)

쉬운 문제이나 또 어려운 문제였다. 시간제한도 넉넉하고 문제도 쉬우나 그 시간제한을 맞추게 알고리즘을 짜는게 쉽지 않았다. 가장 빠른 시간, 즉 최소를 묻는 경우는 보통 풀이 알고리즘이 그리디, DP, BFS가 있다. 그 중에 BFS를 이용해 풀었는데 왜냐하면 수빈이가 이동할 수 있는 경우의 수가 3가지로 정해져 있기 때문이다. 처음 푼 풀이는 visited 집합과 queue를 동시에 사용해서 그 점에 방문한 적이 없으면 queue에 넣는 식으로 풀이를 짰다. BFS이므로 queue에 현재 위치와 움직인 시간을 동시에 넣어서 움직인 시간을 계산하고자 했다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().tri..

백준 16234번: 인구이동(javascript, BFS, 완전탐색)

완전탐색이며 BFS로 풀 수 있는 문제이다. 물론 DFS로도 풀어도 되지만 문제 조건에 인접한 국가만 국경을 열 수 있다는 점에서 넓이 우선 탐색이 좀 더 직관적으로 풀 수 있다고 생각해 BFS로 접근하여 풀었다. 예제에서 N이 3이상인, 즉 인구이동이 다른 구역에서 동시에 일어날 때 인구가 어떻게 합쳐지는 지에 대한 설명이 없어 디버깅에 조금 어려움을 겪었던 문제였다. 물론 예제 4,5를 통해 알수는 있지만 그 과정을 일일히 찾기에 어려움이 있었다. 예제 4,5에서 인구이동이 일어나는 과정을 적은 글이 있어 이 문제를 푸는데 어려움을 겪는 사람이 있다면 참고하면 디버깅에 도움이 될 것 같다. const fs = require('fs'); const input = fs.readFileSync("/dev/..

백준 2589번: 보물섬(javscript, BFS, 완전탐색)

전형적인 BFS이며 브루탈 포스(완전탐색) 문제이다. 문제에서 보물이 묻혀있는 곳 두 거리간의 최단거리를 요구하고 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 최단거리로 이동할 수 있는 방법은 BFS 알고리즘이다. 왜 BFS알고리즘이 최단거리인지는 트리를 어떻게 탐색하는 지를 생각해보면 쉽게 이해할 수 있다. 따라서 이 문제는 완전탐색을 통해 BFS로 육지마다 다른 육지들로 이동할 때의 거리들 중 최대거리를 구하면 그 값이 답이 된다. 또한 BFS는 DFS와 다르게 한번의 이동에 주변을 다 탐색하므로 이동할 때마다 이동거리를 증가시키면 안되고 이전 이동거리에 1을 더해서 이동거리를 계산해야 한다. 위 생각을 토대로 짠 코드는 다음과 같다. 주의할 ..

백준 1325번: 효율적인 해킹(javascript, DFS)

문제는 쉬웠지만 시간관리를 잘해야 하는 문제였다. 문제는 기본적인 문제인데 트리 구조를 만든 후 부모노드를 통해 자식 노드의 개수들을 세는 문제였다. 최대값을 찾아야 하므로 완전탐색을 이용해야 함을 알 수 있었고 N이 10^4로 좀 컸지만 시간제한이 5초로 매우 넉넉하여 쉽게 풀 수 있을것 같았다. 그러나 시간초과가 여러번 났는데 트리를 탐색하는 방법에 문제가 아닌 트리를 배열로 표현하기 위해 배열을 선언하는 과정에서 문제가 있음을 알 수 있었다. 먼저 원래의 배열 선언 코드는 다음과 같다. let tree = new Array(N+1) for(let i=0; i Number(a)) const tree = Array.from({ length: N + 1 }, () => []); for (let i=1; i

백준 14502번: 연구소 (javascript, DFS)

간단하고 전형적인 DFS문제이다. 0은 빈칸이고 1이 벽, 2는 바이러스가 있는 곳이다. 최대 개수를 세야하므로 조합 혹은 완전탐색을 이용한 방법과 DP를 이용한 방법중에 선택해야 하는데 제한시간이 2초로 매우 넉넉하여 조합을 통한 모든 경우의 수를 비교 후 최대값을 찾는 알고리즘으로 풀었다. 이때 각각의 배열들(연구소)은 참조형 변수이기에 깊은 복사를 이용해서 불러와야 하는데 나는 배열의 각 행마다 전개구문을 사용함으로써 깊은 복사를 행하였다. const fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); const [ROW, COLUMN] = input[0].split(' ').map(a..

백준 2870번: 수학숙제 (javascript, 구현)

문제 자체는 쉬운 문제였지만 자바스크립트를 공부한 지 얼마 안되다 보니 새롭게 배운 점이 있어 기록을 위해 글을 남겨본다. 먼저 알고리즘은 간단하다. 한 문자열씩 for of문으로 돌면서 숫자인지 아닌지 판별하고 숫자형일 경우 문자가 나올때까지 합쳐서 배열에 넣고, 배열을 마지막에 정렬하여 출력하며 된다. 문제는 문제의 조건에서 각 줄은 최대 100글자라는 조건이 문제다. 엣지케이스를 생각해보면 가장 큰 수는 999...(100자리)일 것이다. 통상적으로 사용하는 javascript의 정수형 자료형은 Number인데 8바이트(64비트)를 사용한다. 이 중 1비트는 부호, 11비트는 지수부이고 52비트가 가수부이므로 Number자료형으로 표현할 수 있는 최대 정수는 2^53-1이다. 이는 당연하게도 문제의..

프로그래머스: 주차 요금 계산 (파이썬, 구현)

문제 자체는 어렵지 않았는데 구현에 시간이 좀 걸리는 문제였다.. 푸는데 40분정도 걸린 것 같다. 시간과 번호판의 자리수가 정해져 있기에 파이썬의 list indexing과 sort함수를 이용하면 쉽게 풀 수 있는 문제였다. 먼저 문제에서 봐야할 조건은 크게 두가지 였던것 같다. 첫째로 누적 주차시간을 계산하여 요금을 일괄로 정산한다는 점, 둘째로 입차 후 당일에 출차를 안할 시 23:59분에 출차로 계산한다는 점이다. 셋째로 차량 번호가 작은 자동차부터 주차요금을 배열에 담아 return해야 한다는 점이다. 이 세가지 조건을 토대로 차량번호별로 주차시간을 계산해야하고, 미리 번호판, 시간순으로 정렬이 필요하겠다는 생각을 하였다. 번호판, 시, 분 순으로 정렬한다면 in, out조건을 신경쓸 필요 없어..

프로그래머스: [3차] 압축 (파이썬, 구현)

간단한 구현 문제이나 푸는데는 30분정도 걸린 것 같다.. 대기업 코딩 테스트에는 구현 문제가 한 두문제씩 나오는 경우가 많아 여러가지 케이스들을 미리 해보는게 빠른 구현에 도움이 될 것 같다. 문제를 살펴보면 주어진 문자열을 LZW라는 알고리즘으로 압축을 해야 하는데 이 알고리즘은 사전의 인덱스를 이용하여 해당하는 문자의 인덱스를 출력하는 방식이다. 따라서 문제를 풀기 위해서는 우선 대문자들로 dictionary를 미리 초기화 시켜야함을 알 수 있다. 그 후 반복문을 이중중첩하여 문자열을 탐색하는데 내부의 반복문은 dictionary가 계속 늘어나기에 그에 맞춰 문자열을 dictionary의 key에 없을때까지 더하는 용도이다. from string import ascii_uppercase def so..