문제 문제 바로가기> BOJ 2042번: 구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 indexed tree를 이용해서 푸는 문제다. 다음과 같이 구간합을 저장하고 있는 트리를 만들 것이다. 크게 4가지 단계로 볼 수 있는데, 1. tree의 크기를 설정한다. tree의 크기는 N보다 크면서 N과 가장 가까운 2의 거듭제곱으로 설정하는데, 이는 tree의 depth가 1 증가할수록, 노드의 개수가 2배씩 늘어나는 특징을 반영한..

문제 문제 바로가기> BOJ 10597번: 순열장난 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 풀이 1 ≤ N ≤ 50이므로, 수를 한개 또는 두개 씩 잘라가며, 순열을 만들어 본다! 이 때, 이미 사용한 수, 수열의 범위를 넘어서는 수의 경우는 더 이상 탐색해 볼 필요가 없다. C++ #include #include #define MAX 51 using namespace std; int N, len; vector v; bool isuse[MAX]; void solution(string..

문제 문제 바로가기> BOJ 1655번: 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 2개의 우선순위 큐를 이용하여 문제를 해결할 수 있다. 💡 문제의 핵심은 2개의 우선순위 큐의 차이를 최대 1로 유지하며, 2개의 우선 순위 큐를 1차원적으로 봤을 때, 오름차순 수열이 되도록 만들어주는 것이다! 💡 maxHeap(오름차순)의 top은 항상 minHeap(내림차순)의 top보다 작다. → 오름차순 1. 두 힙의 size의 최대 차이를 1로 만들기 위해서, minHeap..

Next Permutation next permutation ! 말 그 대로 다음 순열을 찾는 방법이다. = 현재 순열의 상태에서 크기순으로(사전 순) 다음에 올 수 있는 순열을 생성 구현에 들어가기 전에 기억 할 것 첫 순열 = 오름차순 마지막 순열 = 내림차순 → 모든 수가 내림차순으로 정렬되어 있다면, 순열을 모두 만들어 낸 것이고, 따라서 종료 조건이다! 그렇다면, Next Permutation을 어떻게 구현할까? 1. 뒤에서부터 역방향으로 탐색하면서 교환위치( i-1 , 오름차순이 깨지는 부분)을 찾는다. 💡 오름차순이 깨지는 부분이 교환 위치인 이유 자 예를 들어 ` int a = {1, 4, 9, 8, 3, 2,1}; ` 배열이 있다고 하자. a[2] ~ a[6] 은 모두 내림차순으로 정렬되..

문제 문제 바로가기> BOJ 9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 `board[row] = col` 값을 저장하여, 2차원 배열이 아닌 1차원 배열로 문제를 해결할 수 있다. 퀸을 놓을 때 가로, 세로, 대각선을 확인해야 하는데, solution() 함수에서 한 줄에 하나를 놓고, 유망한 경우, 다음 solution을 호출하기 때문에 자동으로 한 row에는 퀸이 하나만 놓인다. 따라서 대각선과 동일한 column에 퀸이 놓여 있는지를 통해 해당 위치가 유망한지 판단해주면 된다. C+..

문제 문제 바로가기> Programmers : 상품 별 오프라인 매출 구하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 -- PRODUCT 테이블과 OFFLINE_SALE 테이블에서 상품코드 별 매출액(판매가 * 판매량) 합계를 출력하는 SQL문 -- 결과는 매출액을 기준으로 내림차순 정렬하고, 매출액이 같다면 상품코드를 기준으로 오름차순 정렬 select PRODUCT_CODE, sum(PRICE*SALES_AMOUNT) SALES from PRODUCT join OFFLINE_SALE on PRODUCT.PRODUCT_ID = OFFLINE_..

문제 문제 바로가기> Programmers : 조건에 맞는 도서와 저자 리스트 출력하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 -- '경제' 카테고리에 속하는 도서들의 도서 ID(BOOK_ID), 저자명(AUTHOR_NAME), 출판일(PUBLISHED_DATE) 리스트를 출력하는 SQL문을 작성 -- 결과는 출판일을 기준으로 오름차순 정렬 select BOOK_ID, AUTHOR_NAME, DATE_FORMAT(BOOK.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE from BOOK join AUTHOR ..

문제 문제 바로가기> BOJ 2493번: 탑 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 stack을 이용해서 푸는 문제다! 이전에 비슷한 문제를 풀어봤었는데, 처음 접했으면, stack으로 풀어야지라고 생각하지 못했을 것 같기도 하다. 현재 빌딩의 높이가 입력으로 들어올 때, 총 3가지의 경우가 있다. 1. stack이 비어 있는 경우 : 레이저를 수신할 탑이 없다. 따라서, 0을 출력한다. 2. stack의 top이 현재 빌딩의 높이보다 큰 경우 : stack의 top이 바로 레이저를 수신할 탑..

문제 문제 바로가기> BOJ 2023번: 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 왼쪽 부터 자리 수를 늘려가면서 소수인지 판정한다. cnt == N , 즉 N 자리가 되기전에, 소수가 아니라고 판별되면, 그 이후로는 더 볼 필요가 없다! 첫 째 자리 수가 소수일 수 있는 경우는 `2, 3, 5, 7` 뿐이고, 둘 째 자리부터 짝수로 끝나는 경우는, 소수가 될 수 없다. 소수를 판별할 때는 N의 제곱근 까지만으로 나누어 보면 된다! 💡 소수 판별 시 N의 제곱근 까지만 나누..

MySQL 세계에서 가장 많이 쓰이는 오픈 소스의 관계형 데이터베이스 관리 시스템 다양한 운영체제에서 사용할 수 있으며, 여러 가지의 프로그래밍 언어를 지원 크기가 큰 데이터 집합도 빠르고 효과적으로 처리할 수 있음 널리 알려진 표준 SQL 형식을 사용 MySQL 응용 프로그램을 사용자의 용도에 맞게 수정할 수 있음 키워드와 구문에서 대소문자를 구분하지 않음 DB 서버마다 독립적인 스토리지를 할당하는 방식을 사용 MySQL 장점 용량 & 처리 : 적은 용량 차지(1MB RAM), 매우 적은 오버 헤드, 빠른 처리 속도로 대용량 데이터 처리에 용이 접근성 : 다른 데이터 관리 툴에 비해 구조가 간단하여 사용이 쉬움 지원 : 다양한 프로그래밍 언어와 통합 가능, 거의 모든 운영체제에서 사용을 지원 유연성 :..

문제 문제 바로가기> BOJ 17837번: 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 문제에서 요구하는 조건대로 구현해주었다. 원판을 업을 수 있으므로, 2차원 배열의 각 칸을 vector 또는 ArrayList로 관리한다! 주의할 점은, 움직인 후 바뀐 좌표 업데이트 잘해주기?! 정도인 것 같다 C++ #include #include #define MAX 13 #define WHITE 0 #define RED 1 #define BLUE 2 using namespace std; s..

OSI 7 계층 OSI = Open Systems Interconnection Reference Model 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것 하위 계층 → 상위 계층에 서비스 제공 왜 ? ✔️ 통신이 일어나는 과정을 단계별로 파악하기 위해! ✔️ 통신 과정에서 문제가 발생할 경우, 다른 단계를 건드리지 않고, 해당 단계만 고치면 됨! 💡 OSI 7Layer : 네트워크 전송 시 데이터 표준을 정리 💡 TCP/IP 4계층 : 정리한 이론을 실제로 사용하는 인터넷 표준 1 Layer - Physical Layer ( 물리 계층 ) 전기 신호의 전송만을 담당 송수신 데이터가 무엇인지, 어떤 에러가 있는지 등은 신경쓰지 않음 장비 : 통신 케이블, 리피터, 허브 등 전송 단위 : 비트 (Bi..

문제 문제 바로가기> BOJ 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬 (2 ≤ 섬의 개수 ≤ 6) 에 대표 번호? 를 매겨주었다. 어떤 섬에서 어떤 섬으로 이어지는 다리인지 알기 위해서! 2. 문제에서 준 조건인, ▷ 다리의 길이 > 2 ▷ 중간에 방향 변화 불가 를 만족 시키는 다리(edge)가 이어주는 섬 두개 (from, to), 다리 길이(len)를 pq에 넣어준다! 이 때, 상 하 좌 우 탐색을 모두 진행하면, 중복되는 edge들..

문제 문제 바로가기> BOJ 17478번: 재귀함수가 뭔가요? 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 풀이 종료 조건과, 규칙을 찾아서 구현해주면 된다 ! C++ #include using namespace std; void recursive(int cnt, int maxcnt){ for(int i=0; i

문제 문제 바로가기> BOJ 15684번: 사다리 조작 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 ** 시간 초과 방지를 위한 Tip ** 1. h번 가로선에서 사다리를 조작한 경우, 그 다음 조작할 사다리는 h번 가로선 부터 찾아가면 된다. → 이미 앞에서 계산했으므로 ! (이 부분이 중요 ) 2. 가로선을 연속해서 나란히 놓을 필요가 없기 때문에, `isLine[a][b] || isLine[a][b+1] || isLine[a][b-1]` 다음 중 하나라도 해당 된다면, 가로선을 놓을 필요가 없다..