본문 바로가기

Algorithm🐰96

[프로그래머스] 거리두기 확인하기 2021 카카오 인턴십 DFS 문제 : https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 분석 : 크기는 5X5 배열 예를 들어 입력이 2차원 배열로 주어질 때 P는 사람.. 2021. 9. 5.

[백준] 1463 1로 만들기 DP 문제 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 분석 : 재귀와 메모제이션을 이용해 풀었다. 처음에 if (d[n] > 0) return d[n]; 부분을 넣어주지 않아 시간 초과가 났었고 d[1]일때 n == 1일때 처리를 return 0으로 처리 해주지 않아 100퍼에서 에러로 헤맸다 c++ 코드 : // // 1463_makeOne.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/08/23. // #include #include #include using namespace std; int d[10000.. 2021. 8. 23.

[리트코드] 98. Validate Binary Search Tree - BT 문제 : https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 예시 : Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. 주어진 input이 .. 2021. 8. 17.

[프로그래머스] 보석 쇼핑 2020 카카오 인턴쉽 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 분석 : leetcode에 minimun window subString 문제를 풀고 나서 다시 풀었다! 투포인터로 접근했지만 방법을 모르겠으니 하드 코딩화 되어 가는 것만 같아서 .. TC도 통과도 못하고 있었던 찰나 슬라이딩 윈도우 알고리즘과 관련된 문제를 풀고나서 다시 적용해보았다. c++ 코드 : // // [KAKAO] 2020_jewerly_re.cpp // SOMA👩🏻‍💻 // // Crea.. 2021. 8. 5.

[리트코드] 76. Minimum Window Substring (슬라이딩 윈도우) 문제 : https://leetcode.com/problems/minimum-window-substring/ Minimum Window Substring - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 : hard 풀이 알고리즘 : sliding window(슬라이딩 윈도우) ⭐️ 슬라이딩 윈도우란 ? 일정 범위 만큼의 윈도우(w)를 가지고 슬라이딩 ~ 하며 찾는 기법을 말합니다. 주로 구간 문제에 많이 사용되며 투포인터와 방법론이 비슷하여 같이 얘기 .. 2021. 8. 5.

[리트코드] 3. Longest Substring Without Repeating Characters 문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/ Longest Substring Without Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 : Medium 풀이 방법 : 브루트 포스 O(n^2) 문자열 s에서 중복되는 문자 없이 가장 긴 서브 스트링을 찾는 문제였다. 슬라이딩 윈도우 방식을 사용하면 O(n) 만큼으.. 2021. 7. 16.

[리트코드] 1. Two Sum (두수의 합) 문제 : https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 : easy 풀이 방법 : 부르트포스 O(n^2) c++ 코드 : class Solution { public: vector twoSum(vector& nums, int target) { vector answer; for(int i = 0; i < nums.size(); i++){ for(int j = i + 1; .. 2021. 7. 12.

[백준] 5567 결혼식 구현 문제 : https://www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 분석 : 결혼식에 올 동기들 중 내 친구, 내 친구의 친구만 초대 하려면 몇명 초대 해야 묻는 문제였다. 친구 관계를 friends vector에 넣어 friends[친구] = ["친구의 친구들 리스트"] 를 찾으면 되는 문제지만 * 주의 해야 할 점이 있다. 친구의 친구가 내 친구일 수도 있기 때문이다. 따라서 우선 내 친구들만 queue에 넣어 result 값을 증가시켜준 다음 que.. 2021. 6. 13.

[백준] 2579 계단 오르기 DP 문제 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 분석 : 계단이 있을 시 계단을 오르는데 규칙이 있다 --> 점화식이군 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. stairArr [i] = i번째 계단의 값 d [i] = .. 2021. 6. 13.

[프로그래머스] Summer/Winter Coding 스킬트리 level2 문제 : programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 분석 : 분명 나보다 더 효율적인 코드가 있을 것이라 생각한다! 하지만 이 문제는 다행히(?) 효율성 체크하는 문제가 아니여서 맞출 수 있었다. (soma 첫 게임 문제와 비슷한 유형의 문제라(근데 그 친구는 위상 정렬이었다) 꼭 풀고 싶었다) 이 문제는 전에 최장 공통 부분 수열 공부했을때 언뜻 봤었던 최장 공통 부분 문자열과 비슷해 보이지만 skill의 모든 문자열을 스킬 트리가 가지고 있지 않아도 된다는 점에서 조금 다르다. 만약에 제시된 skill 순서가 CBD 이고 순서에 맞는지 검사하고 싶은 대상들 {"CBADF", " AECB", "OP.. 2021. 5. 8.

[백준] 1149 RGB 거리 DP ㅇ문제 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 분석 : rgb 색깔을 양 옆 집마다 겹치지 않게 색칠하는데 그 최소 비용을 구하는 문제다. dp 배열은 2차원 배열로 이루어져 있으며 dp[i][0], dp[i][1], dp[i][2]는 각각 i번째 집까지 색칠할때 0-빨간색 최소 비용,1-노란색 최소 비용,2-파란색 최소 비용을 저장하고 있는 배열이다. 예를 들어 dp[1][1]은 이전 0번째 집을 색칠할때 드는 최소 비용에.. 2021. 5. 8.

[프로그래머스] 경주로 건설 2020 카카오 인턴쉽 level3 문제 : programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 분석 : 이 문제는 백준에서 풀었던 내리막길 문제와 비슷하게 dp + dfs의 조합문제였다... 2021. 5. 7.

[프로그래머스] Summer/Winder Coding 기지국 설치 level3 문제 : programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 분석 : 시간초과 + 에러난 c++ 코드 : // // [SW] 2018_BaseStation.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/05/06. // #include #include #include #include #include using namespace std; //vector statio.. 2021. 5. 6.

[백준] 16236 아기 상어 DFS, Priority-Queue 문제 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 설명 : -> 아기 상어가 몇초 동안 물고기 잡아먹을 수 있는지 출력하시오 공간 n = 4 0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어가 움직일 수 있는 조건 1. 자기 주변에 인접한 물고기 && 먹을 수 있다면 가장 인접한 물고기를 먹으러 간다. 2. 인접한 물고기가 여러 마리라면 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기.. 2021. 5. 6.

[백준] 9095 1,2,3 더하기 DP 문제 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 분석 : 점화식을 세우면 간단히 해결할 수 있는 문제였다! 큰 문제가 작은 문제로 나누어지는 전형적인 dp 문제였고 1, 2, 3의 합으로 나타낸다는 것은 1일때 1 2일때 1 + 1 2 3일때 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 1 + 2 1 + 3 과 같이 나타내어지는 것을 의미한다. n = 4일 경우 나타내어지는 경우의 수를 memo[4]라고 하자 그럴때 경우의 수는 1 + memo[3] 2 + memo[2] 3 + memo[1] 일 것이다. 따라서 점화식은 memo[n.. 2021. 5. 4.

[프로그래머스] Summer/Winter Coding 지형 이동 level 4 MST 문제 : programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 분석 : 문제를 구현하면 되는 식이었다. 크루스칼 알고리즘, spanning tree 처음 공부해보는데 백준에서 유제 문제를 더 풀어봐야겠다. c++ 코드 : // // [SW] 2019_terrainMove.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 202.. 2021. 5. 2.

[백준] 1937 욕심쟁이 판다 🐼 DP 문제 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 분석 : n x n 판다 집이 있으면 판다는 상하 좌우로 움직일 수 있고 현 위치에서 다음 날이 될때 이동하는데 이동하는 칸에 먹이가 더 많아야 움직일 수 있는 욕심쟁이 친구다. 그래서 최대로 살 수 (?) 있게 하는 날을 구하는 문제였다. arr배열에 밥을 넣어주고 dp를 동시에 0으로 초기화 시켜준 뒤 dp 함수를 돌면서 최대로 살 수 있는 maxRice (maxLife 변수가 더 적절할듯.. 2021. 5. 2.

[프로그래머스] 합승 택시 요금 2021 카카오 블라인드 테스트 level3 문제 : programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 분석 : 첫번째 접근 문제를 보아하니 a와 b가 따로 갔을때와 중간 지점 걸쳐서 도착한 .. 2021. 5. 2.

[프로그래머스] Summer/Winder coding 방문 길이 level2 문제 : programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 분석 : 처음에 dfs문제인줄 알고 마침 오늘 dfs 스터디 해서 dfs 짜다가 stack에 push 해줄 필요가 없음을 느끼고 단순 문자열 길이만큼 for문을 돌아 answer 값을 증가 해주는 식으로 간소화 하였다. 1. 첫 접근 방식 갔던 간선은 또 갈 수 없으니 2차원 visit 배열 생성 후 false인 좌표에 대해서만 answer 값 증가시키기 하지만 이 방식은 1번시, 도착 노드로 방문했던 (5,6)번지를 7번 작업 수행시 (5,6)번이 이미 방문한 노드가 되었으므로 7번 간선을 만들수 없게 된다. 그래서 정점 방식으로 접근하면 안된다.. 2021. 4. 30.

[프로그래머스] 순위 검색 2021 카카오 블라인드 테스트 level2 문제 : programmers.co.kr/learn/courses/30/lessons/72412 >str){ j++; if(j == 5){ memberScore.push_back(stoi(str)); continue; } memberSet[i].insert(str); } } for(int i = 0; i >str){ j++; if(str == "and"){ continue; } if(j == 8){ searchScore.push_back(stoi(str)); continue; } searchQuery[i].push_back(str); }.. 2021. 4. 28.

이전 1 2 3 4 5 다음

티스토리툴바