투투

programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 접근 처음에 접근했던 방식은 주어진 숫자 중 최댓값을 생성하여 2부터 최댓값까지 탐색하여 소수일 때 입력된 숫자 안에 포함되는지 확인하려고 했다. 하지만 몇몇 케이스에서 시간초과가 발생하였다. 그래서 주어진 숫자에서 만들 수 있는 수를 만들어 소수를 판별하고자 하였다. 구현 permutations를 통해 1부터 입력된 숫자의 길이만큼의 순열을 만들어준다. 생성된..

programmers.co.kr/learn/courses/30/lessons/42747?language=python3# 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 접근 문제를 이해하는데 어려움을 겪었고 많은 테스트 케이스를 놓쳤다. 먼저 인용횟수가 입력되는데 해당 인용횟수 중에서 h편 이상 인용된 논문이 h 이상일 때를 찾는 줄 알았다. 하지만 인용횟수가 담긴 리스트가 아닌 0회에서 10,000회 이하의 수 중에서 조건에 부합하는 h를 찾는 것이다. 또한 h편 이상인 논문..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 접근 처음에 위에서 주어진 조건대로 구현을 하려고 했지만 실패했다. 최소 연산을 해야하는 최적화문제이기 때문에 그리디 or 동적프로그래밍으로 풀 수 있겠다는 생각을 하였다. 하지만 여기서 그리디로 구현하면 최적해가 나올 수 없었고 동적프로그래밍을 사용하였다. 여기서 할 수..

programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 접근 DFS로 ICN을 출발하여 깊게 탐색해 나간다. 탐색하다가 더이상 방문할 공항이 없을 때 경로에 하나씩 추가해온다. DFS를 재귀로 구현을 하면 도착점에서부터 경로에 추가되어 오기 때문에 마지막에 뒤집어서 반환하도록 한다. 구현 defaultdict는 딕셔너리를 생성하는 것인데 인자로 주어진 값으로 초기화를 한다. 여기서 리스트로 초기화..

programmers.co.kr/learn/courses/30/lessons/43165# 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 접근 타겟넘버를 만들기 위한 연산은 덧셈과 뺄셈 뿐이다. 그래서 각 상황에서 덧셈을 할 때와 뺄셈을 할 때로 나눠서 계산을 해나가고 numbers의 수를 모두 사용했을 때 target과 비교해본다. 이문제를 dfs와 bfs로 모두 풀어보자 구현 ▶ DFS 각 상황에서 numbers에 있는 수를 더하거나 빼는 것을 dfs함..

문제 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다. 따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다. 숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 N번째 영화제목을 출력한다. 접근 1탄은 666이고 2탄은 1666이다. 영화제목에는 666이 포함되어 있어야 한다. 처음에 입력된 N에 따라 출력을 만들어보려고 했지만 실..

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 접근 처음에 DFS로 각 노드를 방문하려고 했다. 하지만 현재 노드에서 깊이있게 탐색하기 때문에 1, 2, 3 노드가 모두 연결되어있다고하면 1->2->3으로 방문하여 모순이 발생하는 경우가 있을 수 있다. 따라서 현재 노드에서 주변 노드를 먼저 방문하는 BFS로 탐색하였다. 또한 2차원 리스트로 그래프를 표현하면 시간초과가 발생하였고 인접 리스트로 구현하였다. 구현 먼저 입력받은 간선의 정보를 통해 무방향 그래프를 표현하였다. def solut..

programmers.co.kr/learn/courses/30/lessons/12906?language=javascript 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr 나의 코드 입려된 배열의 마지막에서 두 번째 원소까지 탐색을 진행한다. 현재 인덱스의 숫자의 다음 인덱스의 숫자가 다르다면 answer에 push를 하며 탐색이 모두 종료되었을 때 마지막 인덱스의 숫자도 push하여 반환한다. function solution(arr) { var answer = []; for (va..

programmers.co.kr/learn/courses/30/lessons/42883?language=python3 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 접근 프로그래밍적으로 어떻게 풀 수 있을까가 아닌 그냥 어떻게 풀지만 생각하여 적당한 방법이 떠오르지 않았다. 그래서 다른 사람들의 풀이를 참고하였다. 그리디 알고리즘으로 분류가 되어있었고 어떠한 기준으로 최적을 선택할지 고민을 했었다. 이럴때 앞에서부터 탐색하면서 어떻게 최적의 해를 구할지 손으로 풀어가면서 생각을 발전시킬 필요가 있다. 스택을 활용하여 스택에 첫 숫자를 넣어주고 시작한다 두 번째 숫자부터 탐색을 진행한다. 이때 스택의 top과 계속 비교하여 top이 더작고 제거할 수인 k가 남아있다면 계속해서 pop을 ..

programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 접근 문자열로 들어오는 것이 리스트의 형태로 들어온다면 굉장히 쉬운문제라고 생각했다. 그래서 입력된 문자열을 리스트로 변환하는 과정을 거쳤으며 이후에 2차원 리스트가 생성이 되었고 2차원 안의 리스트들의 길이에 따라 오름차순으로 정렬하여 문제에서 원하는 답을 구하였다. 구현 입력된 문자열을 탐색한다. 숫자가 들어온다면 wor..