분류 전체보기

백준 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..

프로그래머스: k진수에서 소수 개수 구하기 (파이썬, 구현)

간단한 구현 문제인데 구현할게 조금 있어서 30분보단 조금 더 걸렸던 문제였다. 문제를 풀기 위해서는 세가지를 구현해야 하는데 첫째로 10진수를 n진수로 변환해주는 함수, 두번째로 소수인지 아닌지 판단하는 함수, 마지막으로 n진수에서 0을 기준으로 숫자들을 나누는 함수이다. 함수는 순서대로 보겠다. 우선 소수인지 아닌지를 판단하는 함수이다. 프로그래머스를 좀 풀어본 사람이라면 알텐데 소수구하는 문제가 은근 많아 소수 구하는 방법은 외울 정도이다. 제곱근보다 작은 구간에서 약수를 가진다면 수를 그 약수로 나눈 수는 제곱근보다 큰 구간에서 약수가 되므로 제곱근까지만 약수가 있는지 없는지를 보면 된다. 다음으로 진법 변환 함수이다. 아마 컴퓨터공학이나 전자전기공학을 전공한 사람들은 다 알텐데 10진수를 n진수..

프로그래머스: n^2 배열 자르기 (파이썬, 구현)

규칙만 알면 금방 풀 수 있는 문제라 생각한다. 먼저 제한사항부터 보면 n의 최댓값이 10^7이다. 만약 2차원 배열을 2중 반복문으로 일일히 초기화하여 푼다면 시간복잡도가 10^14이상으로 시간초과가 날 것이다. (일반적으로 시간복잡도는 10^9를 넘기지 않아야 한다.) 따라서 2차원 배열을 직접 만들어서 풀수는 없고 다른 풀이를 생각해야 한다. 테스트케이스 설명을 애니메이션으로 아주 현란하게 설명하는 문제였는데 나는 그런건 할줄 몰라서 파워포인트로 간단하게 그림을 그려 설명해보겠다. 테스트 케이스2의 n=4인 2차원 배열이다. 왼쪽에 숫자는 배열에 채워지는 수들이고 괄호안의 숫자는 배열의 몇번째에 있는지를 나타낸 것이다. 문제에서 주어지는 left와 right가 괄호안의 숫자에 해당함을 알 수 있다...

프로그래머스: [1차] 뉴스 클러스터링 (파이썬, 구현)

우선 문제가 꽤나 길다. 코딩테스트는 수학, 공학문제 풀이와 다르게 풀이를 구현하는데 시간이 꽤나 걸려 문제 조건을 꼼꼼히 읽는 것이 특히 더 중요한 것 같다. 문제에선 자카드 유사도라는 새로운 개념을 소개하고 이를 응용하여 두 문자열의 유사도를 출력할 것을 요구한다. 문제를 읽으면서 집중했던 부분은 크게 네가지이다. 첫째로 원소의 중복을 허용하는 다중집합에 대해서도 자카드 유사도를 적용할 수 있다는 것이다. 이는 두 집합간의 교집합을 구할때 중요하다. 왜냐하면 중복을 허용하지 않는다면 리스트를 집합으로 변환 후 뺼셈을 통해 교집합의 원소의 갯수를 쉽게 구할 수 있지만 중복이 있다면 반복문을 통해 교집합을 구해야하므로 교집합을 구하는 구현 방법이 달라진다. 둘째로 두 집합이 모두 공집합일 경우 자카드 유..

프로그래머스: 점프와 순간이동 (파이썬, 구현)

간단한 구현문제이다. 최소값을 구하는 문제이기에 완전탐색, DP, 구현 세가지 방법이 떠올랐으나 제한 사항을 보고 바로 구현문제임을 알 수 있었다. 왜냐하면 N이 10억 이하의 자연수로 일반적으로 효율성 테스트를 통과하기 위해서는 1초안에 통과해야 하는데 1초안에 통과하기 위해선 시간복잡도가 1억 이하여야 하기 때문이다. 문제의 조건을 우선 보면 지나온 거리에 2를 곱하여 이동하는 순간이동은 count를 올리지 않고 1씩 이동하는 것만 count를 올리므로 N이 짝수라면 2로 나누고 N이 홀수라면 1을 빼주어 짝수로 만들어 다시 2로 나누는 작업을 N이 1이 될 때까지 반복하면 됨을 알 수 있다. def solution(n): answer = 1 while n != 1: if n % 2 == 1: n -..