본문 바로가기

전체 글

 (126)
[BOJ] 백준 15651. N과 M (3) ▶문제설명[BOJ] 백준 15651. N과 M (3)https://www.acmicpc.net/problem/15651 ▶ 설계[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제에서 N과 M (1)과 다른점은 진한 글씨로 표시된 부분 밖에 없습니다.N과 M(1) 풀이 링크 ( https://it-earth.tistory.com/138 ) 1차원 bool 배열로 중복 체크를 해주었던 부분만 제거하면 이 문제의 정답이 됩니다. ▶..
[BOJ] 백준 15650. N과 M (2) ▶문제설명[BOJ] 백준 15650. N과 M (2)https://www.acmicpc.net/problem/15650 ▶ 설계[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제에서 N과 M (1)과 다른점은 진한 글씨로 표시된 부분 밖에 없습니다.N과 M(1) 풀이 링크 ( https://it-earth.tistory.com/138 ) N과 M (1)의 풀이와 거의 같지만 오름차순인 순열만 출력되게 하기 위해서,..
[BOJ] 백준 15649. N과 M (1) ▶문제설명[BOJ] 백준 15649. N과 M (1)https://www.acmicpc.net/problem/15649 ▶ 설계[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 무식하게 모든 경우를 다 해보면 되는 문제입니다. (브루트 포스)이런 식의 문제는 재귀로 구현하면 편합니다. 1 ~ n의 수 중에 아직 사용되지 않은 수를 벡터에 push_back 하면서 가능한 경우를 모두 탐색합니다.사용된 수를 체크하기 위해 1차원 bool 배열을 사용합니다. 벡터의 사이즈가 M이 되면 M개의 수를 선택한 것이 되므로 수열을 출력합니다. 재귀호출 전에 true, 호출 후에 false로 바꾸어..
대소문자를 구분하지 않는다는 조건에 대하여 (대/소문자 변경) 우리가 문제를 해결하다 보면 대소문자를 구분하지 않고 문자열을 비교해야 하는 경우가 있습니다."Talk" 와 "taLk" 를 같은 문자열로 보겠다는 뜻입니다. 어떻게 하면 이 두 문자열을 같은 문자열로 만들어 줄 수 있을까요? 간단한 방법이 하나 있습니다.모든 영문자를 대문자로 변경하거나 소문자로 변경해주면 됩니다. 저는 소문자로 변경해주는 방법에 대해서 이야기해보겠습니다.가장 먼저 떠오르는 생각은 반복문으로 문자열의 첫 문자부터 끝 문자까지 확인하면서 대문자를 소문자로 변경해주는 방법입니다. 12345678910111213141516171819#include#include#includeusing namespace std; int main(){ vector vt = {"Talk", "taLk"}; cout
[BOJ] 백준 1074. Z ▶문제설명[BOJ] 백준 1074. Zhttps://www.acmicpc.net/problem/1074 ▶ 설계문제에서 주어진 그림을 관찰해보자. N이 2인 경우 순회하는 순서를 나타내는 그림이다. 변의 길이가 2^2 = 4이다. 4등분하여 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단을 순서대로 방문해야한다.즉, 변의 길이가 2^N인 사각형을 더이상 등분하지 못할 때까지 4등분할 수 있는지를 묻는 문제이다. 변의 길이가 2^N인 사각형을 가능한 한 4등분해서 Z가 시작되는 위치의 좌표와 변의 길이를 2로 나눈 값을 인자로 넣어서 재귀호출 하면 될 것으로 보인다. 규칙을 파악했다면 N이 3인 경우에는 어떻게 되는지 그려보자. 편의상 같은 숫자가 적힌 것으로 붙여넣었지만, 오른쪽 상단은 16~31, ..
[BOJ] 백준 2447. 별 찍기 - 10 ▶문제설명[BOJ] 백준 2447. 별 찍기 - 10https://www.acmicpc.net/problem/2447 ▶ 설계별이 찍힌 모습에서 규칙을 찾을 수 있다. N이 3인 경우 N이 9인 경우 N이 27인 경우 규칙이 보이는가? 잘 안보인다면 아래의 그림을 보자. N에 따라서 균등하게 9등분을 해보면 가운데 부분만 비어있는 모습을 볼 수 있고, 각 등분된 조각을 또 9등분 해보면 가운데 부분만 비어있는 것을 볼 수 있다. 더 이상 범위를 나눌 수 없을 때까지 나누면서 가운데 부분을 제외하고 재귀호출하면 문제를 해결할 수 있을 것으로 보인다. ▶ 구현우선 메인문을 작성해보자. 12345678910111213141516int main(){ scanf("%d",&N); for(int i=0; i
[BOJ] 백준 1654. 랜선 자르기 ▶문제설명[BOJ] 백준 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 ▶ 설계현재 K개의 랜선이 있는데 가지고 있는 랜선들을 일정한 길이로 잘라서 N개의 랜선으로 만들어야한다. 랜선을 N개 이상으로 만들 수 있는 랜선 길이의 최대값을 구하는 문제이다. 랜선 길이 len을 먼저 정하고 해당 길이로 N개 이상의 랜선을 만들 수 있는지 판단하는 방식으로 문제를 해결할 수 있을 것으로 보인다. len의 길이는 이분탐색으로 값을 정해주면 빠른 시간에 문제를 해결할 수 있게 된다. left는 가능한 랜선 길이의 최소값, right는 가능한 랜선 길이의 최대값으로 초기화 한다. 그리고 (left+right)/2에 해당하는 mid 값으로 N개 이상의 랜선을 만들 수 있는지 ..
[STL 컨테이너] deque 한번에 정리하기 ▶ [STL] deque 컨테이너vector 컨테이너는 컨테이너의 맨 앞에 원소를 추가하는 멤버함수가 없다. 배열의 맨 앞이나 중간에 원소를 추가하려면 나머지 원소들을 모두 뒤로 한 칸씩 이동시켜야한다. vector 컨테이너는 배열 기반으로 구현되어있으므로 원소를 앞이나 중간에 삽입하는 기능이 매우 비효율적으로 동작하게 된다. 또한 배열의 사이즈를 초과하는 경우 사이즈를 늘려서 재할당하고 기존의 값을 복사해주는데, 이 작업도 오버헤드가 크다. deque는 컨테이너의 앞과 뒤로 삽입과 삭제가 자유롭도록 구현되어있다. deque도 배열 기반으로 구현되어있지만, 원소를 앞으로 밀어내거나 뒤로 밀어내는 게 가능해졌기 때문에 vector의 삽입 연산보다는 좀 더 빠르게 동작한다. 컨테이너에 대해 알고싶다면 아래의..
[STL 컨테이너] vector(벡터) 한번에 정리하기 ▶ [STL] vector 컨테이너배열을 선언할 때 입력으로 몇 개의 데이터가 들어올 수 있는지 정확히 알지 못할 때가 있다. 표준 라이브러리에 있는 malloc()으로 배열을 동적 할당해본 경험이 있는가? 오늘 vector를 배우고 나면 특별한 경우가 아닌 이상 일일이 동적 할당해줄 필요가 없다. STL의 vetor는 배열을 동적 할당한 뒤 입력이 너무 많아 할당된 공간을 초과하는 경우 자동으로 사이즈를 늘려주도록 구현되어 있기 때문이다. 이미 구현되어 있는 클래스를 가져다가 사용 방법만 익혀 사용하면 된다. 벡터는 대표적인 시퀀스 컨테이너이다. 컨테이너에 대해 알고싶다면 아래의 링크를 클릭하세요. link : 컨테이너란? vector 컨테이너의 자주 사용되는 생성자와 멤버 함수를 살펴보자. 더 다양한..
[STL 알고리즘] sort - 구조체 정렬 ▶ [STL 알고리즘] sort - 구조체 정렬알고리즘 문제를 해결하다보면 구조체를 정렬해야 할 경우가 생긴다. STL 알고리즘 중에 컨테이너를 정렬해주는 sort가 있다. 이를 활용하여 구조체를 정렬하는 방법을 알아보자.이해하기 쉽도록 간단한 문제를 만들어서 sort를 사용해 문제를 해결하는 과정을 설명하려한다. ▶ 문제우리는 사람 10명의 이름, 나이, 키, 몸무게를 알고있다. 10명의 사람들 중 모델이 될 사람을 뽑아야 한다. 그래서 키가 가장 크고, 몸무게가 적게 나가면서, 어린 사람을 찾으려 한다. 키가 큰 사람을 우선하는데, 키가 같은 경우에는 몸무게가 적은 사람을 우선하고, 키가 같으면서 몸무게도 같은 경우에는 어린 사람을 우선한다. STL 알고리즘 중 sort를 활용해서 문제를 해결하라. ..
[프로그래머스] 주식가격 ▶문제설명코딩테스트 연습 > 스택/큐 > 주식가격https://programmers.co.kr/learn/courses/30/lessons/42584 ▶ 설계prices의 길이가 2 이상 100,000이하이고,prices에 저장된 각 가격은 1 이상 10,000이하의 자연수이다. 2중 for문으로 일일이 확인하도록 구현하는 방법이 가장 먼저 떠올랐다.이렇게 나이브한 알고리즘으로 문제를 해결한다고 하면100,000개의 가격 각각에 대해 1초에 가격이 1부터 1씩 증가한다고 했을 때 최대 10,000번을 확인하게 된다.1부터 10,000까지 1씩 증가시키고 그 다음 또 1부터 10,000까지 1씩 증가시키는 것을 반복했다고 한다면따라서, 최악의 경우에 대략적으로 100,000 * 10,000 = 1,000,..
[프로그래머스] 네트워크 ▶문제설명코딩테스트 연습 > DFS/BFS > 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 ▶ 설계DFS로 해결이 가능한 문제이다. 2차원 벡터 매개변수인 computers는 인접행렬로 정점들 사이의 간선 여부를 나타낸다. 문제에서 연결 요소를 네트워크라고 표현했을 뿐, 그래프의 연결 요소의 개수를 세서 리턴하는 문제라고 생각하면 된다. 네트워크가 몇 개인지를 구하는 함수의 시그니처를 정의해보자. 123void findNetworkNum(int n, int nowComputer, const vector& computers, vector& visited){ }Colored by Color Scriptercs 매개변수명 의미 n 컴퓨터의 개수..

티스토리툴바