본문 바로가기

ALL

 (73)
[프로그래머스] 최고의 집합 [프로그래머스] 최고의 집합 코딩테스트 연습 - 최고의 집합 | 프로그래머스 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 } programmers.co.kr 자연수1 + 자연수2 + ... + 자연수n = S 이면서 자연수1 * 자연수2 * ... * 자연수n 이 최대가 되는 집합 자연수를 중복해서 ..
[프로그래머스] 방문 길이 [프로그래머스] 방문 길이 코딩테스트 연습 - 방문 길이 | 프로그래머스 programmers.co.kr 캐릭터가 좌우 10칸짜리 공간을 이동하는데 새로운 길을 지나가는 수를 세는 문제이다 방문노드가 아닌 방문 선분이 필요한데 check[x][y][dx][dy]라는 체크 변수를 만들었다 x, y 좌표에서 dx, dy 좌표로 이동하는 것을 체크하는 변수이다. 음수 좌표는 코드가 귀찮아지니까 전부 5씩 더해 -5,-5 좌표를 0,0으로 두고 시작좌표를 5,5로 바꾸어 진행했다. 주의할 점은 새로운 길을 찾을 때 카운트를 하는데 x,y 좌표에서 dx, dy 좌표를 체크했으면 반대로 dx, dy 에서 x, y로의 좌표도 체크를 해줘야한다. 방향만 다를 뿐 같은 길이기 때문이다. #include using nam..
[프로그래머스] 라면공장 [프로그래머스] 라면공장 코딩테스트 연습 - 라면공장 | 프로그래머스 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량 programmers.co.kr 우선순위 큐를 사용하면 쉽게 풀 수 있는 문제였지만, 나느 전혀 생각하지 못하였다. 내가 처음에 생각했던 방식은 현재 재고에서 공급받을 수 있는 날짜 ..
[프로그래머스] 땅따먹기 [프로그래머스] 땅따먹기 코딩테스트 연습 - 땅따먹기 | 프로그래머스 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면 programmers.co.kr 단순히 DFS나 단순 for문으로 모든 경우를 탐색하는 경우에는 시간초과가 일어난다. 행의 갯수가 100000개라고 가정했을 때 4 * 3 * 3 * ..
[프로그래머스] 입국심사 [프로그래머스] 입국심사 코딩테스트 연습 - 입국심사 | 프로그래머스 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사 programmers.co.kr 이분탐색으로 분류되어 있는 문제다. 핵심은 이분탐색을 하는데, 입국 심사관이 검사할 수 있는 사람들 수를 맞추면서 가장 최소가 되는 시간을 구하면되는 ..
[프로그래머스] 숫자 야구 숫자 야구 코딩테스트 연습 - 숫자 야구 | 프로그래머스 [[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]] 2 programmers.co.kr 중, 고등학교 때 수업시간, 자습시간에 했던, 군복무할 때 할게 없어서 하던 그 숫자 야구게임. 완전 탐색 문제이기 때문에 모든 3자리 숫자에 대해서 스트라이크, 볼 검증을 하면 된다. 정답이 123이면 baseball 벡터의 숫자와 비교하면서 스트라이크 개수, 볼의 개수가 모두 같으면 정답이 가능한 숫자로 answer를 카운트하면 된다. 다만 문제에 조건들을 자세히 읽어보지 않으면 아마 채점 결과가 계속 50 ~ 60일 것이다. 문제에서 숫자는 3자리 숫자라고 하지만 문제 설명을 다시 자세히 읽어보면 각자 서로 다른 ..
[프로그래머스] 여행경로 [프로그래머스] 여행경로 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 티켓을 가지고 모든 공항을 순회하여야 하고 여러곳을 갈 수 있을경우 알파벳순으로 방문한다. 그리고 모두 방문하지 못하는 경우는 없다. 나는 key - value를 이용할 수 있는 map을 이용하여 티켓별로 갈 수 있는 곳을 지정하였고 value는 리스트로 가지고있어야하니 vector값을 키의 value로 했다 vector는 공항 이름과 방문 여부를 가진 구조체의 벡터로 설정하였다.. 그리고 그 value들을 알파벳 순으로 정렬한 뒤 dfs 탐색..
[프로그래머스] 가장 큰 수 https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 | 프로그래머스 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. programmers.co.kr 알고보면 엄청나게 간단한 문제이지만 방법을 생각해내지 못했을 때 30,..

티스토리툴바