탄탄한 기본기!

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 제한 사항 (3 ≤ L ≤ C ≤ 15) 문제 풀이 이 문제는 dfs를 활용해서 백트래킹을 할 수 있는지 없는지 물어보는 문제인 것 같다(조합). 문제를 풀 때 자음과 모음 개수에 대해서 제약이 있는데, 모음은 최소 1개 이상, 그리고 자음은 최소 2개 이상으로 구성되어 있다는 것이다. 이 때문에 본인은 다음과 같이 dfs 함수의 매개변수로 모음의 개수를 넘겨주어 이를 계산할 수 있도록 하였다. const dfs = (cnt, st, key, aeiouCnt) ..

Programmers - 가장 먼 노드 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,0..

Programmers - 네트워크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 comp..

Programmers - 짝지어 제거하기 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 문제 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면..

BOJ 1079 - 마피아 1079번: 마피아 첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 www.acmicpc.net 문제 문제 풀이 일단 이 문제는 백트래킹 문제라는 것을 바로 알 수 있었다. 재귀를 구현할 때 낮과 밤을 잘 구분한 다음 조건에 맞도록 낮에는 투표로 살아있는 사람들 중 유죄 지수 배열에서 숫자가 제일 높은 사람을 죽이고 밤이라면 마피아가 무작위로 한 명 골라서 죽인다. 라는 로직에 충실히 구현을 하고자했다. 근데 1시간이 넘도록 계속 "틀렸습니다"가 떠서 테스트 케이스들도 많이 만들어보고 로직도 계속 확인했는데... 문제를 잘못 이해..

leetcode Monthly Challenge - N-Queens II N-Queens II - 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 문제 문제 풀이 해당 문제 역시 leetcode의 5월 Daily Challenge 문제였다. 문제를 풀이한 후에 난이도가 Hard인 것을 확인했는데, 사실 N-Queen 문제는 워낙 유명하기도 하고 예전에 백준에서 비슷한 문제를 한 번 풀어본 적 있었기 때문에 어렵지 않게 풀이할 수 있었던 것 같다. 사실 이 문제는 ..

leetcode May Challenge 28 - Maximum Erasure Value 결과적으로, 이 문제는 시간 복잡도가 O(N)만에 풀이할 수 있는 풀이법으로 풀이해주었다. 문제는 위와 같이 배열이 주어졌을 경우, 중복 값을 가지지 않는 연속된 부분 배열 중 그 배열의 요소의 합이 가장 큰 경우의 합을 출력하는 것이었다. 그리고 문제 조건을 보면 nums의 길이가 최대 10,000 이기 때문에 완전 탐색은 당연하게도 절대 불가능했다. 그리고 처음엔 투포인터로 접근해 left와 right을 증가시켜주며 합을 기억하고, 중복 값이 발견되는 경우를 set을 통해서 검출해주는 방식으로 접근했지만, 중복값을 검출했을 경우 left를 어떻게 갱신해주어야 최적화가 되는지 찾아내지 못하여 시간이 조금 걸린 문제..