본문 바로가기

알고리즘

프로그래머스 - 단어 변환 문제풀이에 백트래킹을 적용하였고, 자바스크립트로 작성했습니다. 문제 두 개의 단어 begin, target과 단어 집합 words가 매개변수로 주어질 때, 최소 몇 단계를 거쳐 begin이 target으로 변환 될 수 있는지를 반환하라. 제한사항 한 번에 한 개의 알파벳만 바꿀 수 있다. words에 있는 단어로만 변환할 수 있다. 각 단어는 알파벳 소문자로만 이루어져 있다. 3 dot->dog->cog와 같이 4단계를 거쳐 변환 가능. 문제풀이 이 문제의 가장 작은 하위문제는 words 순회할 때 이전 문자열을 현재 문자열으로 수정할 수 있는가 없는가 이다. 수정이 가능할 경우 이전문자열을 현재 문자열로 수정한 경우와 수정하지 않은 경우 둘 다 탐색해야한다. 수정이 불가능한 경우 수정하지 않은 경우만 .. 더보기
프로그래머스 - 네트워크 문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 말한다. 예를들어 컴퓨터A가 컴퓨터B와 직접적으로 연결되어있고, 컴퓨터B가 컴퓨터C와 직접적으로 연결되어있다면, 컴퓨터A와 컴퓨터C는 간접적으로 연결되어 정보를 주고 받을 수 있다. 따라서 컴퓨터A,B,C는 모두 같은 네트워크 상에 있다고 말할 수 있다. 컴퓨터의 갯수 n과 연결에 대한 정보가 주어질 때, 네트워크의 갯수를 반환하라. 입력값 n(int): 컴퓨터의 갯수 computers(int[][]): 컴퓨터들이 연결되어있는지 아닌지를 표현한 2차원배열. 컴퓨터i와 컴퓨터j가 연결되어있다면 computers[i][j]는 1이고 연결되어있지 않으면 0이다. 제한사항 1 더보기
프로그래머스 - 등굣길 문제 물 웅덩이가 없는 칸만으로 학교에 갈 수 있는 경로의 수를 구하라 입력값 m: 가로 길이 n: 세로 길이 puddles: 물에 젖은 지역들 좌표 제한사항 1 더보기
프로그래머스 - 정수 삼각형 문제 삼각형 꼭대기에서부터 바닥까지 이동할 때, 숫자의 합이 가장 큰 경우를 찾아라. 아래칸으로 이동할 때는 대각선 방향으로 왼쪽 한 칸 또는 오른쪽 한 칸으로만 이동이 가능하다. 제한사항 1 더보기
프로그래머스 - 카펫 level 2 문제 갈색으로 테두리가 1줄 둘러져있고 중앙에는 노란색이 칠해져 있는 카펫이 있다. 갈색 격자의 수와 노란색 격자의 수가 주어질 때, 카펫의 가로 세로 규격을 반환하라. 문제풀이 1. 주어진 노란색 격자로 만들 수 있는 모든 [가로, 세로]를 순회한다. 2. 그렇게 사각형 중 둘레의 길이가 갈색 격자의 수와 같은 것이 있으면 정답을 찾은 것. 3. 노란색 사각형의 가로 세로를 반환하는게 아니라, 거기에 갈색 격자까지 합했을때의 가로 세로 크기를 반환해야하므로 노란 사간형의 가로 세로 길이에 2씩 더해준다. function solution(brown, yellow) { let y = 0 while (++y) { const x = yellow / y if (y > x) { break } const perim.. 더보기
프로그래머스 - 숫자 야구 level 2 문제 숫자 야구 게임은 1~9까지 3자리 임의의 숫자를 정한 뒤 서로가 생각한 숫자를 맞추는 게임이다. 숫자는 맞지만, 위치가 틀렸을 때는 볼 숫자와 위치가 모두 맞을 때는 스트라이크 숫자와 위치가 모두 틀렸을 때는 아웃 입력값 baseball: 질문한 세자리 수, 스트라이크의수, 볼의 수를 담은 2차원 배열 출력값 정답일 수 있는 숫자의 수 문제풀이 1. 정답 후보가 될 수 있는 가장 작은값 123 부터 가장 큰 값 987까지 순회하며 정답인지 확인한다. 2. 100처럼 0이 포함되어있거나 112 와 같이 같은 수가 중복된 경우는 답이 될 수 없는 숫자이므로 제외한다. 3. 정답후보와 질문한 세자리 수를 비교해봤을떄 스트라이크나 볼의 갯수가 딱 맞아 떨어지지 않는 경우 정답이 아니므로 제외한다. fun.. 더보기
프로그래머스 코딩테스트 Kit 스택/큐 문제풀이 프로그래머스 코딩테스트 kit 스택/큐로 분류되어 있는 탑, 다리를 지나는 트럭, 기능개발, 프린터, 쇠막대기, 주식가격 문제풀이. 1.탑 function solution(heights) { const answer = [0]; for (let i = 1; i < heights.length; i++) { for (let j = i - 1; 0 heights[i]) { answer.push(j + 1) break } } if (answer.length === i) { answer.push(0) } } return answer; } 2.다리를 지나는 트럭 function solution(bridgeLength, weight, truckWeights) { truckWeights.reverse() const on.. 더보기
2018 카카오 코딩테스트 1차 비밀지도 JS 문제풀이 🔗직접 문제 풀러가기 문제 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ") 또는벽("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도1과 지도2라고 하자. 지도1 또는 지도2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다. 문제풀이 1. 각 배열의 i번째 정수를 이진수로 바꾸었을 떄 01 과 11라면 해독된 숫자는 이진수 11이다. 즉, OR 연산을 활용하면 된다. 2. .. 더보기