목록Problem Solving (54)
이것저것
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/EHGP0/btq2SMTYecX/t6wm1fdiGcY7nnJrhpCEHk/img.png)
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr [풀이과정] 구해야하는 것 : 보석을 모두 포함하는 가장 짧은 구간의 시작점과 종료점 1) 먼저 보석의 종류들을 set에 모두 담아둔다. (vector아닌 set에 담아두는 이유 : set은 중복 원소를 포함하지 않으므로, 보석이 종류들만 얻을 수 있다. 2) 투 포인터를 사용하여 가장 짧은 구간의 시작점을 찾아준다. start와 end를 각각 0으로 초기화하고, 다음과 같은 두 가지의 경우로 나뉘어진다. - ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Floyd-Warshall 알고리즘 사용 문제 Point : 경유지를 무엇으로 설정할까? -> 결국 경유지를 다 탐색해봐야하는 완전 탐색 문제! 프로이드-와샬 알고리즘을 사용해서 해결할 수 있는 문제다. 이 문제의 핵심은 경유지를 무엇으로 정하는가 이다. 아래 그림에서 1,2,3,4,5,6 에 경유지를 둘 수 있다. (여기서 경유지를 둔 다는 것은 출발점에서 경유지 지점까지 (S -> K)는 "무지"와 "프로도"가 함께 택시를 타고 경유지에서 각각의 도착지점까지 (K->A or K->B) 까지는 따로 택시를 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/csLj9o/btq2MzG8cjp/HvXEKKoNTY4bC5VmkIkH01/img.png)
https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 과정 문제를 보자마자 해시를 떠올렸다! 여러 장르들이 존재하는데 조건1) 에 의해 속한 노래가 많이 재생된 장르의 순서를 구해야한다. 그러기 위해 우선 장르를 키값으로 가지는 map을 만들었다. 그리고 이 map의 value값은 총 몇 번 재생되었는지를 나타내야하므로 plays 배열의 값을 더해주었다. for(int i=0;ifirst,it->second..
문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 1..
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력 1 5 17 예제 출력 1 2 풀이 과정 1) BFS로 쉽..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/MRWtJ/btqX82UB9ie/aU87HGX5kSRjVCm8R860m0/img.png)
문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ZuaQq/btq2TbEtovE/RxerbJnxq37kzkeAzqydK0/img.png)
https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 풀이과정 이번 문제도 일반적인 풀이와는 조금 다르게 푼 거 같다(?) 만약 스킬트리 중에 스킬이 존재하면 그 스킬트리에서 나타나는 스킬에 인덱스를 미리 메모해두었다. 예를 들어 CBD 일 경우 ⇒ 스킬의 인덱스는 순서대로 0,1,2이다. 스킬트리 BACDE ⇒ 1 0 2 (A랑 E는 신경 쓸 필요가 없음 , B 스킬 인덱스는 1, C스킬 인덱스는 0, D 스킬 인덱스는 2) 이런식으로 미리 메모를 해두었다. 이 메모는 무조건 0부터 시작해야한다. 그리고 0→1→2 순서대로 건너뛰지 않고 진행되는 경우만 카운트해주면 답을 구할 수 있었다. #in..
문제 설명 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{&#..