2JINISHAPPY 2JINISHAPPY

programmers.co.kr/learn/courses/30/lessons/42883?language=cpp 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이에 따라 시간이 확연하게 차이나는 큰 수 만들기 문제 주어진 숫자에서 k개의 숫자를 제거했을 때 가장 큰 수를 반환해야 한다 하지만 정석적으로 N자리의 숫자 중 K개를 제거하는 경우를 모두 구하면 아래 사진의 오른쪽 위와 같은 공식이 나온다 그렇기에 최대 백만자리에서는 시간초과가 날 수 밖에 그렇기 때문에 다음과 같이 풀어줬다 len = number의 length - k (목표 문자열 길이)라고 했을 때, ① number내의 모든 문자를 탐색하면서 현재 인덱스부터 뒤에서 len개만큼 확인하면서 최댓값을 구한다 ② 구한 최댓값을..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 한 번 꼬이면 답없는 구슬탈출 문제 ‼⁉❓💯⁉‼ 항상 중요한 것은 문제에 언급한 조건과 순서를 정확히 지켰는지 !! 확인하는 것 !!! 나는 백트래킹, dfs를 이용해서 풀어줬당 ① 현재 좌표를 미리 저장해둔다 ② 이동하려고 하는 방향에 어떤 구슬이 앞서는지 체크 !! (ex. 오른쪽으로 이동하려고 할 때 파란색의 x좌표가 더 크다면 파란색부터 이동시켜준다) ③..

www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 스타트 택시와 함께 반례 찾기에 까다로운 문제!! 이런 구현 문제는 문제를 잘 읽고 수행해야 할 과정들을 순서대로 했는지 점검하는게 가장 중요한 듯 하다 😢 상어의 이동에 관한 것은 홈페이지에 잘 설명되어 있으니 생략하고.... 주의해야 할 것은 한 턴에 무슨 순서로? 진행되느냐!!이다 1. 냄새가 없는 칸 탐색 후 그런 칸이 없다면 냄새가 있는 칸 중 내가 있던 칸..

www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 � www.acmicpc.net 나를 아주아주 괴롭혔던 주사위 윷놀이 문제이다..... 처음에 봤을 때는 저 ㄱㅓ지같은 문제는 어떻게 풀어야 하지.....?? 맵을 링크드리스트로 구현해야 하나...?? 라는 생각을 했었는데 잘 보면 윷놀이의 코스는 4가지로 나뉜다는걸 알 수 있다 그리고 각 코스의 공통점은, 10/20/30을 밟을 경우 해당 번호의 코스로 이동한다는 것!! 또한 코스의 이동은 0번에서 1,2,3번으로의 이동밖에 없다 예를 ..

www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net BFS응용문제인 스타트 택시 문제이당 택시는 지정된 위치에서 출발하고, 현재 가장 가까운 위지에 있는 승객에게로 가서 태운 뒤 해당 승객의 목적지로 간다 위의 과정을 모든 승객에 대해 전부 반복하면서, 남아있는 연료의 양을 계산하는 문제 위와 같은 그림에서는 2번 승객(거리: 6)를 태우면, 연료는 15-6=9가 된다 2번 승객의 목적지인 (1,6)으로 가면 연료를 6소모..

https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 수식을 입력받아서, 연산자의 우선순위를 정하고 계산하는 문제이다 !! 수식 연산자는 더하기 빼기 곱하기의 세 가지만 있기 때문에 next_permutation 함수를 이용해서 우선순위를 이용했다 계산 과정은 N, N+1번째 피연산자를 N번째 연산자로 계산해서 N번째 피연산자로 교체하면 된다 후위연산식의 계산 과정은 생각이 났는데, 중위연산식이 생각이 잘 안..

https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 아래와 같이 진열된 보석 진열대에서 각 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 찾아내는 것 문제의 설명을 보고 DP인가? 라고 생각했는데 DP의 접근방식과 유사하지만 다르게 풀이했다 이러한 경우에서는 번호 3~7번까지의 구간이 R, D, D, E, S의 모든 종류를 포함하면서 가장 짧은 구간이다😉 1. 보석 이름은 string 형식으로 되어있기 때문에 stl map을 만들어 각각의 보석을 번호에 매..

https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 2020 카카오 공채 문제 중 1개인 외벽 점검 문제이다(정답률 0.6%) 원형으로 이루어진 취약 지점들과, 임의 숫자의 사람들이 이동 가능한 거리를 주어주고 벽을 수리할 수 있는 최소 인원을 구해야 한다 대부분의 문제들과 같이 범위는 작아서 완전탐색으로 코딩 가능하다 ❗ 물론 나는 완탐인건 알았지만 효율을 망쳐버려서 시간초과때문에 애를 먹엇ㄷㅏ.. 처음에는 모든..