고슴도치의 IT여행

풀이 문제 : 프로그래머스 코딩테스트 고득점 Kit - 해시 level2 : 전화번호 목록 풀이 언어 : C++ 알고리즘 : 정렬 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제요약 전화번호가 주어지는데, 하나의 전화번호가 다른 하나의 접두어가 된다면 false를 리턴하게 해야한다. 접근 방식 2중 for문을 이용해 확인할수도 있겠지만, 주어진 전화번호 배열을 정렬 후, for문 한개 앞뒤 번호를 비교하는 것이 효율적이다. 코..

풀이 문제 : 프로그래머스 코딩테스트 고득점 Kit - 해시 level1 : 완주하지 못한 선수 풀이 언어 : C++ 알고리즘 : 정렬 문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제요약 participant 과 completion 배열이 주어지는데 participant에는 있지만 completion에는 없는 한명의 이름을 출력하는 문제이다. 접근 방식 처음엔 단순히 2중 for문으로 비교하면 될거라고 생각했지만, 선수 수가 1..

풀이 문제 : 프로그래머스 코딩테스트 고득점 Kit - 해시 level1 : 폰켓몬 풀이 언어 : C++ 알고리즘 : 그리디 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제요약 N마리의 폰켓몬이 주어질 때 N/2 마리를 가져갈 수 있는데, 최대한 다양한 종류의 폰켓몬을 가져간다면 몇 종류인지 알아내야한다. 접근 방식 만약 모든 N마리의 폰켓몬이 다른 종류의 폰켓몬이라면, 답은 N/2 가 될 것이다. 한편, 종류가 하나라면 답은 ..

인터넷 검색 결과 2의 N승 형태와 함께 나타난 범위를 찾기가 어려워서 내가 만들어보기로 했다. 자료형 크기와 범위 구분 자료형 크기(byte) 범위 범위(2ⁿ) 문자형 char signed char 1 -128 ~ 127 -2⁷ ~ 2⁷ - 1 unsigned char 1 0 ~ 255 0 ~ 2⁸ - 1 정수 short short int 2 -32,768 ~ 32,767 -2¹⁵ ~ 2¹⁵ - 1 unsigned short unsigned short int 2 0 ~ 65,535 0 ~ 2¹⁶ - 1 int signed int 4 -2,147,483,648 ~ 2,147,483,647 -2³¹ ~ 2³¹ - 1 unsigned unsigned int 4 0 ~ 4,294,967,295 0 ~ 2³² ..

우선순위 큐 자료구조를 이용할 때, 구조체를 이용할 때가 있는데 이럴 땐 어떻게 큐를 정의하는 지 살펴보자. 기본 자료형 sort와 같은 방식으로, greater, less를 이용한다. priority_queue pq; // 오름차순 주의할 점은 algorithm 내 sort의 greater은 내림차순이고, 우선순위 큐의 sort의 greater은 오름차순이다. 구조체 이번에는 compare 구조체를 만들어서 대소비교하는 operator 함수를 오버로딩한다. 여기서 주의해야할 점은 인자의 순서다. right, left 순서로 정의해 주어야 한다. struct compare { bool operator()(const Struct right, const Struct left) { return s1.value..

algorithm 라이브러리 내 sort 함수를 이용한 구조체 정렬 방법에 대해 알아보겠다. 자료형 정렬 먼저, 기본적인 자료형의 정렬은 이미 선언되어있는 greater, less 함수를 이용한다. #include int arr[5] = { 5,2,4,3,1 }; int main(){ sort(arr, arr+5, greater()); // 내림차순(큰 것 먼저) return 0; } // 결과 : arr[5] = { 5,4,3,2,1 } 구조체 정렬 구조체를 정렬하기 위해서는 어떤 것을 기준으로 정렬할 것인지 정의하는 함수를 직접 만들어야한다. 나는 주로 함수명을 compare로 선언하고, 인자값을 순서대로 left와 right로 선언해준다. compare함수의 두 인자값인 왼쪽 값(left) 와 오른..

풀이 문제 : 백준 11726번 2×n 타일링 풀이 언어 : C++ 알고리즘 : 다이나믹 프로그래밍 문제링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제요약 문제는 매우 간단하다. 접근 방식 처음엔 짝수랑 홀수를 따로따로 생각해봤는데 아무리 해도 답이 안나와서 알고리즘 분류를 봤더니 다이나믹 프로그래밍 문제였다,, 다이나믹 프로그래밍은 문제를 보자마자 알고리즘이 떠오르지 않아 어려운거 같다. DP문제인 것을 깨닫고 나서 처음엔 재귀함수를 짜서 풀었다. ..

풀이 문제 : 백준 1158번 요세푸스 문제 풀이 언어 : C++ 알고리즘 : queue 문제링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제요약 원으로 이어진 배열에서 돌아가며 k번째 수를 제거하고, 제거한 순서대로 출력하는 문제다. 접근 방식 처음엔 구현문제 처럼 풀었다. while 문으로 숫자를 점점 키우면서 k번째가 되면 정답배열에 넣고, used 배열(visited 배열) 에 사용 표시를 하는 식으로 구현했다. 정답은 맞았지만 풀면서 약간 갸우뚱해서 구현 후 정답 코드를 봤다. queue를 이용해 k만큼 돌면서 p..

풀이 문제 : 백준 10815번 숫자카드 풀이 언어 : C++ 알고리즘 : 이분탐색 문제링크 : https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제요약 상근이가 가지고 있는 숫자 카드 배열 N과, 다른 숫자카드 M을 받고 M배열에 상근이의 숫자카드 N이 존재하는 지 확인하는 문제다. 1920번 문제와 매우 유사하므로 이번 문제가 어려웠다면 1920번 문제를 풀어보는 것을 권한다. [백준] 1920번: 수 찾기 /..

풀이 문제 : 백준 1920번 수 찾기 풀이 언어 : C++ 알고리즘 : 이분탐색 문제링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제요약 배열 N, M 두개를 받고 M배열에 N배열 안에 존재하는 지 확인하는 문제다. 접근 방식 처음엔 간단히 이중 for문으로 구성했더니 시간초과가 나왔다. 각 배열 크기가 최대 100,000라서 2중 for문 돌리면 1초가 훌쩍 넘기 때문이다. 그래서..