본문 바로가기

전체 글133

[프로그래머스] level 3 - 최고의 집합 https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 | 프로그래머스 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 } programmers.co.kr 본 문제는 자연수 n 개로 이루어진 중복 집합 중에 다음 두 조건을 만.. 2020. 2. 9.
[프로그래머스] level 3 - 기지국 설치 https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 | 프로그래머스 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g programmers.co.kr 본 문제는 아파트 옥상에 있는 4g 기지국을 5g 기지국으로 바꾸려고 .. 2020. 2. 9.
[프로그래머스] level 3 - 베스트앨범 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play programmers.co.kr 본 문제는 해시와 정렬을 이용해야 하는 문제다. 결과를 장르별, 많이 재.. 2020. 2. 9.
[프로그래머스] level 3 - 예산 https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 | 프로그래머스 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 programmers.co.kr 본 문제는 정해진 예산 총액 이하에서 가능한 최대의 총예산을 나눠주는 문제다... 2020. 2. 9.
[프로그래머스] level 3 - 타일 장식물 https://programmers.co.kr/learn/courses/30/lessons/43104 코딩테스트 연습 - 타일 장식물 | 프로그래머스 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1 programmers.co.kr 본 문제는 DP 문제로 분류되어 있지만 메모이제이션 없이도 문제가 해결.. 2020. 2. 9.
[프로그래머스] level 3 - 이중우선순위큐 https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 programmers.co.kr /* 문제의 해설에 앞서 내가 프로그래머스 문제를 푸는 나만의 기준에 대해 알리고자 한다. 백준은 온라인 강의 중급 2/3까지, 프로그래머스는 level 3까지의 문제를 해결하려고 노력하고 있다. 개인적인 생각으로는 프로그래머스 level 2까지는 백준 온라인 강의 초급보다 쉬운 거 같다. 그렇기 때문에 다음과 같은 순서로 코딩 문제를 풀고 있다. 프로그래머스 level 1, 2 문제 다 풀기기 백준 초급문제 풀기 백준 중급문제 풀기 풀다가 막히면 프로그래머스 level 3 문제 풀기 다시 백준 중급문제 풀기 (brute .. 2020. 2. 8.
[백준 6087] 레이저 통신, C++ https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. www.acmicpc.net 본 문제는 Olympiad 2008-2009 Season January 2009 Contest Silver 3번 문제다. 지도에 빈칸과.. 2020. 2. 7.
[백준 1790] 수 이어 쓰기 2, C++ https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 본 문제는 1 ~ n 까지의 수를 이어서 썼을 때 길이를 구하고 k의 위치의 값을 출력하는 문제다. n의 최대값이 매우 크기 때문에 실제로 값을 구해서 찾는 것은 불가능 하다. 따라서, k와 인접한 위치를 찾아서 출력하는 방식을 이용해야 한다. 이때, 이분 탐색을 이용하면 빠르게 답을 구할 수 있다. 예를 들어 n = 20 일 때, 우선 n까지의 길이가 k보다 짧을 경우를 예외처리 한다. 1 ~ 9 까지의 길이를 구하고 10 ~.. 2020. 2. 5.
[백준 11728] 배열 합치기, C++ https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net 본 문제는 merge sort 문제다. 분할 정복으로 정렬을 해야 하는 문제인데 실제 문제에서는 분할 부분은 생략되어있다. /* 개인적으로 merge sort는 군 복학하고 첫 학기때, for를 이용하여 1 ~ 100까지 더하는 코딩도 못할 시기에 했던 첫 과제였다. 그 당시 또 C언어 기초를 배울 시기라 linked list로 구현했던 것으로.. 2020. 2. 5.

티스토리툴바