전체 글

[프로그래머스] 소수 찾기 - 자바스크립트

문제 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 종이 조각이 있다. 종이 조각은 최소 1개, 최대 7개이며 0~9의 숫자로 이루어진다. "013" 은 0,1,3의 종이 조각이 있다는 의미이다. 풀이는 다음과 같다. 1. 종이 조각으로 만들 수 있는 모든 숫자를 만들고 2. 각 숫자들이 소수인지 판별하여 소수인 숫자 갯수를 출력한다. 종이 조각 "011"의 경우 "011" "11"을 같도록 취급해줘야 한다. 숫자를 만들 때 문자열이 아닌 숫자로 저장해주면 "011"은 11로 저장되므로,..

[프로그래머스] 괄호 변환 - 자바스크립트

문제 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이 문제가 상당히 길지만 당황하지 말고 천천히 읽어보면 의외로 쉽게 풀리기도 한다. 핵심 키워드는 다음과 같다. 균형잡힌 괄호 문자열 : 두 괄호 "(" ")"의 개수가 같다. 올바른 괄호 문자열 : 균형잡힌 괄호 문자열이면서, "(" ")" 의 순서 짝이 맞는 경우이다. 임의의 "균형잡힌 괄호 문자열" p를 입력받아 "올바른 괄호 문자열"로 바꿔서 출력하는 문제이다. 풀이 방향 문제를 보면, 임의의 p를 입력받으나 이는 이미 "균형잡힌 괄호 문자열"임이 ..

[프로그래머스] 게임 맵 최단거리 - 자바스크립트

문제 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 풀이 n x m 행렬에서 (1,1)에서 시작해서 (n,m)에 도달하는 최단경로를 출력한다. (n,m)에 도달할 수 없다면 -1을 출력한다. 풀이 방법 최단경로를 구해야 하므로 BFS 유형의 문제이다. 현재 위치에서, 상하좌우 이동 가능 여부를 판단한다. 상하좌우가 벽(0)이거나, 행렬의 범위를 벗어났다면 이동할 수 없다. 이동할 수 있다면 이동할 좌표와 이동한 횟수를 큐에 넣는다. FIFO를 따라 BF..

[프로그래머스] 땅따먹기 - 자바스크립트

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 처음에는 DFS로 접근했다. N회까지 재귀를 돌면서, X행에서는 X-1행에서 선택하지 않은 열을 선택하여 더했다. 각각의 경우의 수로부터 N행까지 도달했을 때, 최댓값일 경우 최댓값을 갱신하도록 했다. 물론 주어진 행 N이 최대 100,000이기 때문에 재귀 호출로 인한 시간초과 이슈가 발생했다. 모든 경우의 수를 조회할 수 없다면, DP(동적 계획법)를 생각해봐야 한다. 풀이방법 DP답게 생각해보자. land 행렬은 N x 4 크..

[백준] 15990번 1, 2, 3 더하기 5 - JavaScript(NodeJS)

문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 숫자 n을 1,2,3의 합으로 표현하는 경우의 수를 구한다. 1,2,3을 여러 번 사용할 수 있으나, 연속되게 사용하면 안된다. 숫자 4를 표현할 때 1+1+2, 2+2 와 같이 연속되게 같은 숫자를 사용할 수 없다. 이 문제는 dp 유형으로 점화식을 구해야 한다. 우선 1부터 시작해보자. n=1 일 때, 1 n=2 일 때, 2 n=3 일 때, 1+2, 2+1, 3 n=4 일 때, 1+2+1, 1+3, 3+1 n=5 일 때, 1+3+1, 2+1+2, 3+2, 2+3 사실 이렇게만 보면 점화식을 파악하기 ..

[백준] 1157번 단어 공부 - JavaScript(NodeJS)

문제 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 풀이 생각보다 엄청 간단하면서 생각보다 까다로울 수 있는 문제다. 문제의 키포인트는 아스키 코드를 활용해서 문자를 숫자로 바꿀 수 있느냐 일 듯 하다. 풀이 방향 조건이 생각보다 많다. 알파벳 대소문자를 구별하지 않으며, 알파벳 개수를 카운트 해야 하고 가장 많이 사용된 알파벳을 출력하는데, 2개 이상이라면 ?를 출력해줘야 한다. 내가 풀이한 방향은 다음과 같다. 1. 단어를 대문자로 바꾸고 A-Z순으로 정렬한다. 2. 단어의 각 알파벳들을 아스키코드를 이용해 A=0, Z=25의 인덱스 취..