본문 바로가기

프로그래머스39

[프로그래머스 Lv3] : N으로 표현 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 숫자 N으로 특정한 수 number을 만드는데 필요한 N의 최소 개수 리턴 풀이 먼저 주어진 예제를 보자. 5를 이용해서 12를 만드는 방법에는 3가지가 있다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 첫번째, 두번째, 세번째 방법은 각각 5를 6번, 5번, 4번 이용해서 만들었다. 우리가 5를 이용해서 숫자를 만드는 방법은 5가지가 있다. 1. 5를 이어붙인다. ex) 55, 555, 5555, ... 2. +연산 사용. ex) 5 + 5, 55 .. 2022. 6. 28.

[프로그래머스 Lv3] : 섬 연결하기 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 최소비용으로 n개의 섬이 모두 연결될 수 있도록 하는 문제. 풀이 다리를 통해서 통행이 가능하다면 두 섬은 연결되어있다고 본다. 문제를 보면 최소스패닝 트리 문제인 것을 알 수 있다. 최소 스패닝 트리를 이용해서 모든 섬이 공통 조상을 가지도록 연결시켜주면 된다. 코드 작성 #include #include #include using namespace std; const int MAX_N = 100 + 5; int Parent[MAX_N]; int F.. 2022. 6. 23.

[프로그래머스 Lv2] : 구명보트 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 무인도에 갇힌 사람들을 모두 구하기 위해 필요한 최소 구명보트 수를 리턴하는 문제. 풀이 보트에는 최대 2명의 사람이 탈 수 있으며, 무게 제한이 있다. 풀이 알고리즘 무게가 가벼운 사람은 최대한 무게가 무거운 사람이랑 같이 타야 최대한 많은 사람들이 짝을 이뤄서 보트에 탈 수 있다. 일단 탈출해야할 사람들을 무게순으로 정렬.. 2022. 6. 23.

[프로그래머스 Lv2] : 조이스틱 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 원하는 이름을 완성하기 위해서 조이스틱을 최소한 몇 번 조작해야하는 지 리턴하는 문제. 풀이 이번 문제가 여태까지 풀어본 2단계 문제중에 제일 어려운 것 같다. 내 방식대로 몇 번을 시도해봤지만 몇 개의 케이스에서 계속 실패해서, 결국 구글 선생님들께 가르침을 받았다. 초기에 이름은 'A' 로만 이루어져있으며 조이스틱을 상하좌우로 .. 2022. 6. 22.

[프로그래머스 Lv1] : 체육복 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42862# 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 체육복을 도난당한 학생들이 최대한 체육복을 빌려서 체육수업을 들을 수 있도록 해주자. 풀이 나의 알고리즘 1. 잃어버린 학생들 중에 여벌옷을 가지고 있는 학생들은 빌려주지 못하고 자기가 입어야 하므로 본인 여벌옷을 입는다. 2. 체육복을 빌려줄 수 있는 학생들 중에 2명을 빌려줄 수 있는 학생이 아닌, 1명만 빌려줄 수 있는 학생들 먼저 도난 당한 학.. 2022. 6. 21.

[프로그래머스 Lv4] : 징검다리 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 바위를 n개 제거했을 때, 각 지점 사이의 거리의 최솟값이 최대가 되도록 바위를 제거하는 문제. 풀이 풀이 알고리즘 각 지점들 사이에 벌어져야할 최소 간격을 "이분탐색"을 통해서 탐색한다. 벌어저야할 간격의 범위는 0 ~ distance 이내 일 것이다. L = 0, R = distance로 잡고 mid 값을 지점들 사이 벌어져야할 최소 .. 2022. 6. 21.

[프로그래머스 Lv3] : 입국심사 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 모든 입국자를 심사하기 위해 걸리는 최소시간을 리턴하는 문제. 풀이 각 심사관마다 심사하는데 걸리는 시간은 다르며 이는 입력으로 주어진다. 풀이 알고리즘 주어진 시간이 T라고 했을 때, 임의의 i 심사관이 T시간동안 심사할 수 있는 사람의 수는 T / times[ i ] 를 내림한 것과 같다. 그렇다면 T 시간동안 모든 심사관이 입국 심사할 수 있는 사.. 2022. 6. 21.

[프로그래머스 Lv3] : 순위 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 경기 결과의 전체가 아닌 일부가 주어졌을 때, 순위를 정확히 알 수 있는 선수의 수를 리턴하는 문제. 풀이 만약 경기 전체의 결과가 주어졌다면 모순이 없다는 전제 하에 위상정렬로 풀 수 있다. 하지만 경지 전체의 결과가 아닌 일부만 주어졌기 때문에 위상정렬을 사용할 수가 없었다. 풀이 알고리즘 순위를 정확히 알 수 있는 선수는 어떤 선수들인가? 자신을 제외한 n-1명과의 경기 결과가 모두 드러난 선수는 순위를 알 수 있다. 하지만 주어진 경기결과엔 제한이 있.. 2022. 6. 20.

[프로그래머스 Lv3] : 여행경로 문제 링크 https://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 비행기 표가 주어졌을 때 모든 표를 사용해서 여행할 수 있는 경로를 리턴하는 문제. 풀이 각각의 공항을 노드라고 생각했을 때 공항 i에서 j로 가는 표가 있으면 i와 j 사이에 간선이 존재한다고 생각할 수 있다. ICN 공항을 시작 노드로 연결된 노드들로 이동해서 모든 노드를 방문할 때까지 이동한다. 모든 노드를 방문.. 2022. 6. 20.

이전 1 2 3 4 5 다음

티스토리툴바