문제 풀이/프로그래머스 알고리즘, SQL

[프로그래머스 LV1] 비밀 지도 (이진수, 비트연산, 문자열) / 2018 KAKAO BLIND RECRUITMENT) [C++]

https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로..

[프로그래머스 LV3] 보석 쇼핑 (투 포인터, map / 2020 카카오 인턴쉽) [C++]

programmers.co.kr/learn/courses/30/lessons/67258# 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아..

[프로그래머스 LV2] 괄호 변환 (문자열, 2020 카카오 블라인드 문제) [C++]

programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 용어의 정의 '('와')' 로만 이루어진 문자열이 있을 경우, '('의 개수와 ')'의 개수가 같다면 이를 균형 잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 "균형 잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다. 반면에 "((..

[프로그래머스 LV3] 섬 연결하기 (그리디, 유니온파인드) [C++]

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 주어진 노드와 cost 정보로 최소의 비용으로 섬들 간 연결을 하면 된다. 1 - 2 - 3이 연결되려면 모든 노드가 연결되어 있을 필요가 없이 1 - 2, 2 - 3만 되어있어도 1, 2, 3이 모두 연결되었다고 한다. 처음에 어떻게 풀지 고민을 하다가, 그래프 관련 알고리즘으로 풀어보려고 했다. BFS를 사용하면 방문하는 순서에 따라서 최솟값을 못 찾을 수도 있다는 결론이 나와서 pass (모든 점에서 BFS를 통해 최단 경로를 찾은 뒤, 최저 값을 출력하려고 했지만 c..

[프로그래머스 LV3] 가장 먼 노드 (BFS) [C++]

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1번 노드로부터 최단 거리 중 가장 먼 노드들의 개수를 찾는 것이다. 즉, 1번으로부터 4번 5번 6번 노드의 최단 거리가 3이고 그 거리가 그래프에서 1번과 가장 먼 거리면 정답은 3이다. 따라서 나는 input을 인접 리스트에 저장하고, BFS를 수행해서 최단거리를 찾으면 되겠다고 생각했다. #include #include #include using namespace std; vector v[20001]; int check[20001], re..

[프로그래머스 LV4] 3 x n 타일링 (DP) [C++]

programmers.co.kr/learn/courses/30/lessons/12902#qna 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 백준의 이 문제와 똑같다. 밑의 설명을 참고하면 좋을 것 같다. bbeomgeun.tistory.com/30 [baekjoon 2133] 타일 채우기- DP(동적 프로그래밍) (C++) www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 일반적인 타일 문제라 생각했지만 추가적인 아이디어가 필요한 문.. bbeomgeun.tistory.com 차이점은 백준 문제는 30까지 구하지만 프로그래머스는 n이 5000까지..