지나공 : 지식을 나누는 공간

문제 출처입니다. https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그�� programmers.co.kr 구하고자 하는 건 한 지방의 예산 상한액이고, 이 예산의 범위가 1이상 100,000이하인 걸 보면 for문을 돌려 일일이 계산하는 방식이 아니라는 걸 알 수 있습니다. 따라서 효율을 위해 이분탐색을 합니다. 이분탐색 문제는 유형이 거의 비슷해요. 구하고자 하는 것의 범위를 알 때, 이분탐색을 통해 그 값 중 가장 적절한 값이 뭔지 찾는 겁니다...

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr dfs를 활용해서 풀었습니다. 빼기도 하고 더하기도 하고 이렇게 모든 경우를 다 하기 위해 재귀함수를 사용합니다. #include #include using namespace std; int ans; void dfs(vector &numbers, int target, int i, int sum)..

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr dfs로 풀었습니다. 재귀함수, dfs 기본 구현에 충실한 문제였습니다. dfs, bfs에 대해서는 추후에 포스팅을 할 예정입니다. [주석 없는 코드] #include #include #include using namespace std; int ans = 50; bool check[50]; bool diff..

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 해시로 푸는 방식과 정렬로 푸는 방식 모두 통과됩니다. 두 코드 모두를 첨부합니다. 하지만 이 문제에서 phone_book의 길이가 1이상 1000000 이하인 것은 문제의도가 시간복잡도라는 걸 알 수 있습니다. 따라서 해시로 푸는 것을 권장합니다. 먼저 정렬 후 벡터로 푸는 코드입니다. 한 번호가 다른 번호 앞부분과 완전히 일치해야 합니다...

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42576 순서가 상관이 없으므로 unordered_map을 사용하였습니다. unordered_map은 비정렬 연관컨테이너로, 중복을 허용하지 않고 map과 달리 key를 기준으로 자동정렬하지 않습니다. unordered_map과 map, hash_map 등의 개념을 다른 포스팅으로 정리했습니다. 맨 아래에 첨부한 링크를 참고해 주세요. 이제 문제를 살펴볼게요. 마라톤 경기에 참여한 선수의 수인 participant가 있고, 그보다 1 작은 크기의 completion 벡터에는 완주한 선수가 담겨있으니, 완주하지 못한 선수는 전체에서 1명입니다. 여기서 포인트는 '마라톤 경기에 참여한 선수의 수는 1명 ..

hash_와 unordered_에 대하여 hash라는 말이 붙지 않은 map,set은 자료를 정렬해서 저장합니다. (key를 기준으로 오름차순 정렬) 따라서 순회할 때도 저장된 데이터를 넣은 순서대로가 아닌 자동정렬된 순서대로 순회합니다. hash_map과 unordered_map은 유사한 컨테이너인데 차이를 말하자면 hash_map은 비표준(namespace가 stdext)이고 unordered_map은 표준(namespace가 std)입니다. 성능도 unordered_map이 더 우월하고 표준이므로 unordered_map 사용을 권장합니다. 이제, 출력결과를 통해 비교해볼게요. 출력하면서 생각했던 의문들을 같이 적어봤습니다. 엉뚱하고 너무 당연한 의문이 많아서 민망하지만........ map 중복을..

STL(Standard Template Libarary)이란? 컨테이너(자료구조) 클래스, 반복자, 알고리즘 간 협력에 기반한 템플릿 라이브러리 STL 컨테이너의 종류 - 순차 컨테이너 array : 배열 vector : 동적 배열 deque : 양방향 큐 forward_list : 단뱡향 리스트 list : 양방향 리스트 - 연관 컨테이너 ( 정렬된) set : 정렬된 중복 없는 key의 집합 / 중위순회 형식으로 자동정렬됨 map : 정렬된 중복 없는 key-value의 집합 / key를 타겟으로 오름차순 자동정렬됨 multiset : 정렬된 중복 허용 key의 집합 multimap : 정렬된 중복 허용 key-value의 집합 - 비정렬 연관 컨테이너 (정렬 안 된 - 넣은 순서대로 저장됨) uno..

프로그래머스 스택/큐 Level 2인 탑 문제에 대한 풀이입니다. 문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑..

나무 재테크 문제에서 제가 푼 방식처럼, 벡터의 중간 원소를 삭제하되, 빠짐 없이 모든 요소를 체크해야 할 때가 있습니다. 그럴 때 잊지 말아야 하는 것이 인덱스 값의 변경입니다. vectorv; v.push_back(3); v.push_back(6); v.push_back(5); v.push_back(9); v.push_back(2); for (int i = 0; i < v.size(); i++) { cout

나무재테크 문제는 삼성SW역량테스트 기출문제로, 난이도 Gold4의 시뮬레이션 문제였습니다. (문제출처 : https://www.acmicpc.net/problem/16235 ) 일단, 문제를 읽으면서 필요한 변수를 생각해봅시다. 개요부분과 주 내용, 두 부분으로 나눠서 살펴볼게요. 1. 입력받은 값에 따라 땅의 크기가 정해집니다. 하지만 N의 최댓값이 크지 않다면 동적할당으로 하나씩 할당하지 않고, 처음부터 최댓값만큼의 크기로 배열을 선언합니다. 2. r,c가 1부터 시작하므로 각각 1~N까지의 값을 가집니다. 따라서 위에서 말한 이차원 배열의 크기 [11][11] 로 했습니다. 3. 땅을 표현할 이차원배열이 필요합니다. 전부 5로 초기화합니다. → int ground[11][11]; 4. 같은 칸에 ..