분류 전체보기

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐배열은 동일한 데이터 타입의 요소들이 연속된 메모리 위치에 저장되는 자료구조이다.   📌 배열의 정의배열은 선형 자료구조이며, 대부분의 프로그래밍 언어에서 기본적으로 제공되는 만큼 가장 기초적인 자료구조이다.  그럼, 배열이란 무엇일까?배열은 동일한 데이터 타입의 요소들을 1열로 나열, 즉 연속된 메모리 위치에 저장하는 구조이다. 순차적으로 저장되기 때문에, 인덱스 번호가 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치를 뜻한다.예를 들어, 인덱스 번호가 0인 arr[0]은 arr배열의 첫 번째 주소 즉, 기본 주소를 뜻한다.또, 인덱스 번호가 1인 arr[1]은 arr배열의 기본 주..

🔗 문제 링크 : https://www.acmicpc.net/problem/15649  문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열     입출력 예시입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.        풀이 백트래킹 기초에 도움이 되는 문제이다. 몇 번째 수까지 사용했는지를 n에 담아서 재귀 호출을 한다. (다음 재귀 호출은 n + 1) 1~N 까지..

🔗 문제 링크 : https://www.acmicpc.net/problem/10026  문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강..

🔗 문제 링크 : https://www.acmicpc.net/problem/7576  문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익..

🗨 개인적인 공부 목적으로 정리한 내용입니다.     ⭐자료구조는 데이터를 효율적으로 저장하고, 관리하고, 사용할 수 있도록 조직화하는 방법이나 체계를 의미한다.     자료구조(Data Structure)는 컴퓨터 과학에서 매우 중요한 개념이다. 자료구조가 다양한 알고리즘의 성능과 효율성을 크게 좌우하기 때문이다. 따라서, 다양한 프로그램 설계나 문제 해결을 위해서 적합한 자료구조를 선택해야 하므로 각 자료구조에 대해 잘 알아두어야 한다.  📌 자료구조란? 간단하게 표현하자면, 자료구조는 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계를 정하는 것을 말한다. 우리가 일상에서 물건들을 정리하는 방법을 떠올려보자.예를 들어, 여러 개의 칸으로 나누어져 있는 책장에 책을 정리하는 상황을 가정해 보..

🔗 문제 링크 : https://www.acmicpc.net/problem/2003  문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.  출력첫째 줄에 경우의 수를 출력한다.       풀이 #include #include using namespace std;int mai..

🔗 문제 링크 : https://www.acmicpc.net/problem/13144  ☁ 어떻게 해야 투포인터를 더 효율적으로 움직일 수 있을지.. 수많은 고민을 하며 풀었던 문제 아직 투포인터 구현이 미숙했기에 첫 접근 방식부터가 잘못됐었다.투포인터를 구현하면서 중복 확인 부분을 unordered_set을 이용하는 방법을 택했는데, 갈수록 복잡해지는 코드에 잘못된 길(?)을 걷고 있음을 깨달았다. 투포인터조차 제 기능을 못 하는 상황까지.. 🥊  결과적으로, 배열을 이용하여 현재 숫자의 빈도를 카운트를 하고, 중복이 발생하면 투포인터의 움직임으로 구간의 중복을 제거하며, 중복이 없는 구간에서 가능한 경우의 수를 누적해 나가도록 구현한 코드가 최종 정답이 되었다.   역시 다양한 유형의 문제를 풀..

🔗 문제 링크 : https://www.acmicpc.net/problem/3273  문제n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i     입출력 예시입력첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)  출력문제의 조건을 만족하는 쌍의 개수를 출력한다.       풀이 수열은 서로 다른 양의 정수로 이루어졌다. -> 중복되는 수가 없다.(1 ≤ i 예를 들어, 1 3 7 5 인 수열에서 합이 10이 되..

🔗 문제 링크 : https://www.acmicpc.net/problem/1406  문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D : 커서를 오른쪽으로 한 칸 옮김 (커서가..

🔗 문제 링크 : https://www.acmicpc.net/problem/1806  문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 N (10 ≤ N   출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.       풀이 해당 문제는 투포인터를 이용해 해결하였다.현재 부분 합이 S보다 작으면 end를 1 증가 시킨다.현재 부분 합이 S보다 크거나 같으면 수열의 길이를 비교 및 갱신하고, start를 1 증가시킨다.위 과정을 반복한다.#include #in..