겜돌이의 개발일지

문제 프로그래머스 131130 혼자 놀기의 달인 C# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제 설명이 너무 장황하게 되어 있어서... 처음에 독해가 힘들었는데 그냥 간단히 말하면 카드에 적혀있는 숫자를 인덱스로 생각해서 루프를 돌고, 루프 중 제일 긴 것과 그 다음으로 긴 것의 곱만 구하면 되는 문제이다. 루프를 돌 때 어디를 출발지점으로 지정하느냐가 중요할 거 같았는데 생각해보니 카드 숫자는 중복이 없으므로 무조건 순회하는 루프를 만들게 된다. (즉, 루프의 어디서든 시작해도 길이가 항상 똑같음) 그래서 방문 체크를 하는 리스트 visi..

문제 프로그래머스 132266 부대복귀 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아주 일반적인 BFS문제. destination(start)부터 BFS를 돌면서, 각각 노드 첫번째 방문시에 얼마나 걸렸는지(cnt)를 배열(dist)에 넣어준다. 방문 전에 배열은 -1로 초기화하고, 처음 방문시에 걸린 횟수(cnt)를 넣어준다. BFS 특성상 가장 첫 방문이 최단 거리이므로 dist값이 -1이 아니라면 이미 방문한 노드이니 갱신해주지 않는다. BFS를 끝내면 sources에 들어있는 노드까지 얼마나 걸리는지를 answer에 넣어준다. 소스..

문제 프로그래머스 132265 롤케이크 자르기 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 토핑 최대 개수가 백만개이기 때문에, 시간복잡도에 유의해야 한다. 루프를 여러번 돌면 시간초과가 나므로, 처음 top2 확인에 1번, 토핑 전체 검사 후 answer 증가에 1번 루프를 돈다. 먼저 토핑 전체를 검사해서, 서로 다른 토핑의 개수를 top2에 저장한다. 그 후에 토핑을 하나하나 확인해서, top1에 없는 토핑이라면 top1을 늘려준다. top2에 토핑이 없어지면 top2를 1감소시킨다. top1와 top2가 같다면 answer를 1증가시..

문제 프로그래머스 할인 행사 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 조건을 만족하려면 want에 있는 물품이 number에 있는 수 만큼 할인 받아야 한다. map을 활용해 cntMap 선언한 뒤 할인을 받을 때마다 cntMap의 값을 1감소 시키고, 할인 받지 못할 때는 cntMap의 값을 1증가 시키면 된다. 11일차 부터는 해당 날짜의 물품의 cntMap 값을 1감소시키고 (할인 받았으므로), 해당 날짜로 부터 10일 전 물품의 cntMap 값은 1 증가시키면(할인을 이제 못 받으므로) 된다. 오랜만에 map 자료 구조를 이용하는..

문제 프로그래머스 42898 등굣길 C++ 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 해당 좌표가 웅덩이인지 저장하는 water배열을 선언하고, 웅덩이 좌표를 넣어줍니다. 그 이후에는 일반적인 길찾기 처럼 DP를 이용하되, 웅덩이일 경우에는 경로를 계산하지 않고 넘어갑니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #includ..

문제 프로그래머스 43105 정수 삼각형 C++ 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 지금까지의 경로의 합 중 최댓값을 저장해놓은 배열을 DP라고 선언합니다. DP는 다음과 같은 규칙을 따릅니다. 1. 줄의 첫 칸 일 경우 : 자신의 DP값 = 전 줄의 첫 칸의 DP값 + 자신의 값 2. 줄의 마지막 칸 일 경우 : 자신의 DP값 = 전 줄의 마지막 칸(j-1)의 DP값 + 자신의 값 3. 그 외의 경우 : 자신의 DP값 = 전 줄의 j-1, j번째 DP값 충 더 큰 값 + 자신의 값 삼각형의 값은 0이상이므로 마지막 줄인 경우에만 최댓값을 갱신해주면 됩니다. 소스 코..

문제 프로그래머스 43162 네트워크 C++ 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 BFS를 사용합니다. 1. 네트워크에 방문해, 인근 네트워크를 모두 방문 처리 해줍니다. 2. N번째 네트워크까지 반복하면서, 그 네트워크를 방문하지 않았다면 1과정을 반복합니다. 3. 총 네트워크의 개수를 return 합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

문제 프래그로머스 43165 타겟 넘버 C++ 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 BFS를 사용했습니다. 첫 숫자의 음수 값, 양수 값을 queue에 push 해주고 queue에서 하나씩 꺼내며 양수를 더한 값, 음수를 더한 값을 다시 queue에 push 합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include..