본문 바로가기

알고리즘 문제풀이202

[프로그래머스] 큰 수 만들기 (Swift) (스터디) 1. 적용 알고리즘과 문제 설명 그리디 문제 정수로 된 문자열이 주어지고, 자연수 k가 주어지면 정수 문자열에서 k개의 문자를 제거하여 얻을 수 있는 수 중 가장 큰 수를 구하는 문제 문자열에서 문자를 제거하는 것이기 때문에 문자열의 순서는 보존되어야 한다. 접근방법 큰 수를 얻는게 목적인 만큼, 앞자리 수가 커야한다. 스택 하나를 두고, k개의 카드(앞으로 문자를 제거하는 걸 카드라고 표현한다)가 남아있는 한 새로 들어갈 수가 현재 스택의 맨 위의 수보다 커야한다.는 로직이면 가장 큰 수를 얻을 수 있다. 2. 코드에 대한 설명 이걸 코드로 설명하면 k가 0보다 클 때까지는, 스택의 맨 위의 수 >= 새로 들어갈 수 를 만족할 때 까지 스택에서 원소를 뺀다. 그리고 뺄 때마다 k를 1감소 시킨다. im.. 2022. 3. 6.
[프로그래머스] 빛의 경로 사이클 (C++) https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr level 2 구현 (배열) 우선 사이클에 대해서 이해가 잘 안돼서 블로그를 찾아보고 이해했다. (역시 국어문제인가) 사이클은 같은 노드, 같은 방향을 다시 만났을 때 사이클이 이루어진다. 접근방법 모든 노드에서 갈 수 있는 모든 방향으로 경로가 뻗어나간다. 이를 위해 3중 for문을 돌려 각 노드의 각 방향으로 출발하는 (이름만)d.. 2022. 3. 5.
[프로그래머스] 소수찾기 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42839?language=swift 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr level 2 dfs(완전 탐색) 한자리 숫자 여러개로 이루어진 문자열이 주어지고, 종이 조각 하나에 한자리 숫자가 적혀서 흩어져있는 상황이다. 이들을 적절히 조합하여 만들 수 있는 소수의 개수를 반환하는 문제. 즉, 문자열 -> 한자리 숫자들의 배열. 로 만들고 숫자들의 가능한 순열을 구해야 한다. 그렇게 나온 수를 소.. 2022. 3. 5.
[프로그래머스] 멀쩡한 사각형 (Swift) https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr level 2 구현 (최대공약수 & 수학) 직사각형의 가로,세로 크기가 주어지고, 이 직사각형을 구성하는 넓이가 1(1*1) 사각형 중에 대각선이 지나가는 사각형을 제외한 작은 사각형들의 넓이의 합을 반환하는 문제이다. 접근방법 간단해 보였는데 어려웠다. 우선 대각선이 사각형들의 꼭짓점과 만나는 점을 기준으로 작은 사각형으로 분리해야 .. 2022. 3. 3.
[프로그래머스] 큰 수 만들기 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42883?language=swift 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr level 2 큰 수 만들기 (그리디) 정수로 된 문자열이 주어지고, 자연수 k가 주어지면 정수 문자열에서 k개의 문자를 제거하여 얻을 수 있는 수 중 가장 큰 수를 구하는 문제 문자열에서 문자를 제거하는 것이기 때문에 문자열의 순서는 보존되어야 한다. 접근방법 큰 수를 얻는게 목적인 만큼, 앞자리 수가 커야한다. 스택 하나를 두고, k개의 카드(앞으로 문자를 제거하는 걸 카드라고 표현한다)가 남아있는 한 새로 들어갈 수가 현재 스택의 맨 위의 수보다 커야한다.는 로직이면 가장 큰 수를 얻을 수 있다. 오답노트 .. 2022. 3. 2.
[프로그래머스] 행렬 테두리 회전하기 (Swift) https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr level2 구현 rows*columns 인 격자판이 있고, 순서대로 1부터 숫자가 채워져 있다. 사각형을 이루는 대각선의 점이 주어지고, 그 사각형의 테두리를 시계방향으로 한칸 회전한다. 여러개의 대각선 점이 주어지고, 각 테두리를 회전시키면서 만난 가장 최솟값을 반환하는 문제 접근방법 판이 커질 것 같아서 다른 방법을 고민해봤는데, 숫자의 .. 2022. 3. 2.
[프로그래머스] 기능개발 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr level2, 스택 진행 상황, 속도가 아래와 같이 주어진다. 이때 속도는 하루에 할 수 있는 작업의 양 [93, 30, 55] [1, 30, 5] 진행 상황 배열에서 앞쪽에 있는 작업부터 배포될 수 있고, 뒤에 있는 작업은 작업이 먼저 완료되어도 그 앞의 작업들이 배포되기 전까지는 배포될 수 없다. 접근방법 1. 각 작업 마다 필요한 작업일수를 구한다... 2022. 3. 2.
[프로그래머스] 조이스틱 (C++) https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr level2 알파벳으로 구성된 문자열이 주어지고, A로만 이루어진 동일한 길이의 문자열을 주어진 문자열과 동일하도록 바꾸려면 알파벳을 바꾸는 조이스틱 방향과, 커서를 이동하는 조이스틱 방향을 몇번 조작해야하는지 그 최솟값을 구하는 문제 어려웠다 ^_^ 접근방법 알파벳 변경을 위한 조이스틱 조작 횟수는 A부터 Z방향으로 이동하는 경우와, A에서.. 2022. 3. 2.
[프로그래머스] 위장 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42578?language=swift level 2 옷:종류로 된 딕셔너리가 주어지고, 입을 수 있는 옷의 조합의 수를 구하는 문제 한번에 종류당 1개의 옷을 입을 수 있으며, 아무것도 안입는건 불가능 접근방법* 처음에는 조합을 구하는 문제라고 생각해서 백트래킹이나 완전탐색 같은 알고리즘을 사용해서 조합을 구해야 되나 고민했었다. 안입는 경우를 종류별 옷에 개수에 추가하여 구한 블로그를 참고했다. 고등학생때 확통배울때 했었는데..까먹었었음.. 종류별 옷의 개수 + 1(안입는 경우) 를 구한 후에 모든 종류의 옷의 개수를 곱해주면 된다. 그리고 하루에 최소 하나의 옷은 입어야 하기 때문에 아무것도 안입는 경우를 빼준.. 2022. 3. 2.

티스토리툴바