본문 바로가기

알고리즘87

[프로그래머스] 택배상자 c++ (풀이,코드) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/131704 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 코드, 풀이 아래의 주석을 보시면 바로 이해가 되실겁니다. 처음 문제에서 요구하는것과 반대로 생각을 했습니다. 4,3,1,2,5가 결국 order[i]의 값이 1,2,3,4,5순서대로 보조컨베이어벨트를 활용해서 최대 갯수를 구하는줄 알았는데 그것이 아닌 인덱스 +1 번째로 트럭에 실어야 한다는 것이었습니다. (문제 잘 읽자.) /* 1~n번 상자 / 한방향 / 보조컨베이어 -> L.. 2023. 9. 8.

[프로그래머스 완주하지 못한 참가자] c++ (풀이,코드) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 코드, 풀이 풀이 1 완주자에서 참여자를 뺀 나머지 결국 완주를 못한 사람은 제한사항을 따른 한명뿐이다. 생각을 해보니 그냥 completion에 대해서 먼저 map을 추가하고 키값이 false라면 그걸 리턴하면 되지 않을까? 근데 세번째 예시와 제한사항에 중첩이 있을 수 있다니 int로 선언하고 ++을 해준다. -> 0이라면 return해준다. #include #include #.. 2023. 7. 9.

크루스칼 알고리즘(kruskal Algorithm), 최소 신장 트리(MST) c++ 구현 우리는 흔히 알고리즘 문제를 풀다보면 적은 비용으로 연결! 하는 문제를 자주 접하게 되는데요. 자주는 보지는 않지만 가끔씩 보면 까먹기 마련입니다. 저도 까먹고 풀다가 어..? 크루스칼 알고리즘인데 하는 생각이 들어서 이번에 다시 기억하고자 포스팅을 하려합니다. 크루스칼 알고리즘 (Kruskal Algorithm) -> 최소신장트리(MST) 구하기 위해 사용 앞서 위에서 말씀 드린듯이 적은 비용으로 연결하는 것이 핵심입니다. 무방향으로 연결된 노드와 간선이 주어졌을때 우리는 간선의 가중치(비용)에 대해서 모든 노드가 연결이 되어야 하는데 가중치(비용)이 최소화 되는것을 찾을때 사용하게 되는 알고리즘입니다. 최소 신장 트리(MST)가 뭐야? 신장 부분 그래프 (Spanning tree)에서 사용된 간선들의.. 2023. 7. 6.

[프로그래머스 섬 연결하기] c++ (풀이,코드, 크루스칼 알고리즘) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이, 코드 (크루스칼 알고리즘) 이 문제를 처음에는 어 그냥 최솟값에 대해서 연결만 하면 끝나는거 아니야? 하면서 코드를 일일히 나열했다. 근데 풀다가 생각을 해보니 이럴때 각 노드의 연결 값을 최소화!! 할때 크루스칼 알고리즘을 사용하는것이 기억이 났습니다. 크루스칼 알고리즘, 최소신장트리(MST)에 대한 그림과 함께 쉽게 설명👇👇👇 https://bendeng-life.tis.. 2023. 7. 6.

[프로그래머스 개인정보 수집기간] c++ (풀이,코드) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 코드,풀이 이 문제는 문자열을 뽑는 문제로 귀찮은 구분자를 기준으로 뽑을 필요가 없이 달(month)나 일수가 한자리일때 앞에 0을 친절하게 붙혀주는 문제였습니다. 그래서 저는 substr를 활용하여 원하는 위치의 인덱스들의 문자열들을 뽑아와 stoi를 해주었습니다. 사실 틀은 하라는대로 하기만하고 따로 알고리즘을 엄청나게 요구하지 않아 아래의 코드를 보시게 되면 이해가 되실거라고.. 2023. 7. 5.

[프로그래머스 신고결과받기] c++ (풀이,코드) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/92334?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 코드, 풀이 프로그래머스 level1에서 가장 정답률이 낮은 문제인데요. 카카오 문제는 문자열 처리때문에 극혐하지만 그래도 이번에 진행해봤습니다..ㅎ 저의 풀이는 이런식으로 풀었습니다. 1. 맵에 string,int로 id_list와 인덱스를 받아왔습니다. (나중에 int로 처리하기 편하게 하기 위해) 2. report를 돌게 되면서 신고자와 피신고자를 받아와.. 2023. 7. 5.

[프로그래머스 가장 먼 노드] c++ (풀이,코드, bfs) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이, 코드(bfs) 효율성을 요구하는 문제가 없어서 조금은 당황했습니다. 오지 정확성을 확인하고 처음에 통과를 했는데 이게 내 풀이가 맞나...? 하는 생각이 들어 다른 풀이를 복붙하여 확인을 해본결과 메모리와 시간이 어느정도 비슷한것을 확인했습니다. 저는 이 문제를 BFS(너비탐색)로 풀었습니다. 우선 arr이 노드의 갯수가 굉장히 많아 배열로 선언하면 테스트예제 7,8에서 터.. 2023. 7. 4.

[프로그래머스 크레인 인형뽑기 게임] c++ (풀이,코드,스택) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자.. 2023. 7. 4.

[프로그래머스 키패드 누르기] c++ (풀이, 코드) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 코드, 풀이 처음에 풀이를 가로^2 + 세로^2을 거리로 생각을 해서 (문제를 제대로 읽어야지 바보야..) 처음에 틀렸었습니다. 문제는 10분 정도 내외의 시간이 걸렸습니다. 좌표값이라고 생각을 하고 0,0기준으로 y,x좌표를 추출하였습니다. y = (numbers[i] - 1) / 3; x = (numbers[i] - 1) % 3; 1,4,7의 경우에는 왼쪽에 대한 map을 갱신.. 2023. 7. 4.

[프로그래머스 징검다리 건너기] c++ (풀이,코드,이분탐색) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이, 코드(이진탐색) 이 문제는 풀때 어떤 알고리즘이다! 라는 생각이 아니고 처음 풀때는 아주 뇌를 비우고 풀었었습니다.. 경우의 수도 생각없이 그냥 뭐 일단 가장 적은값에 대해서 다 빼버리고 그다음에 탐색을 순차접근을 하면 되지 않을까 하는 생각으로 뇌를 비우고 아래의 코드처럼 짰었습니다. 틀린 이상한 코드 #include #include #include #include usin.. 2023. 7. 3.

[프로그래머스 스티커 모으기] c++ (풀이, 코드, DP) 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 및 코드 (DP) 이 문제는 저 DP에요~ 하는 문제라고 할 수 있습니다. 규칙성이 존재하면서 최댓값을 구하는 문제에서 DP를 자주사용하는것 같은데요. 이 문제의 규칙성에 대해서 문제의 예시에 대해서 그림과 함께 잠시 보겠습니다. 즉 DP[i] = DP[i-2] + sticker[i] 과 dp[i-1]중 최댓값이 담기게 됩니다. 우리는 선택지가 첫번째를 선택하였을때와 두번째를.. 2023. 6. 29.

투포인터 알고리즘(Two-Pointer Algorithm)이란? (예시,활용코드) Two Pointer 알고리즘이란 1차원 배열에서 두개의 포인터를 활용하여 원하는 결과를 얻기 위한 알고리즘입니다. 보통 연속된 수의 합이 충족하는 갯수를 구하게 되는데 dfs로 풀게 되면 엄청난 시간복잡도를 야기하게 됩니다. 이를 위해 1차원 배열에서 두개의 포인터를 이용하여 경우의 수에 대해서 마지막에 도달할 경우 값을 구할 수 없어 종료를 시키게 합니다. 시간 복잡도는 O(n)으로 굉장히 알고리즘 문제에서 가끔씩 사용하게 됩니다. 예시의 이해를 위해 우리가 주어진 1차원 배열에서 합이 6인 숫자들의 케이스를 모두 카운팅하는 것에 대해서 예시를 들어보겠습니다. 배열 예시 [1,2,3,3,6,5,1] 원하는 합이 6이 되는 연속된 숫자들의 조합 갯수 투포인터 활용 설명 합이 6보다 작을때는 end의 인.. 2023. 6. 28.

이전 1 2 3 4 ··· 8 다음

티스토리툴바