문제 문제 바로가기> BOJ 2531번: 회전초밥 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 두 포인터를 조작해가며, 푸는 문제다. 회전 초밥이 "회전하는 벨트 위"에 있음을 주의해야 한다. 따라서 종료 조건이 right == k-1, 즉 회전 초밥 벨트를 모두 확인했을 경우다!!!! C++ #include #define DISH 30001 #define KIND 3001 using namespace std; int N, d, k, c; // 회전 초밥 벨트에..

문제 문제 바로가기> BOJ 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 주의할점 1. 파이어볼이 나눠진 후, 방향이 변화되어 제자리에 담긴다. 이동 x 2. 인덱스 `-`가 되지 않도록, N*s를 더해 준다. → 어짜피 modulo 하면 사라짐 #include #include #define MAX 51 using namespace std; struct FIREBALL { int m, s, d; }; vector map[MAX..

문제 문제 바로가기> BOJ 11053번: 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP와 이중 for문을 이용해 "현재 수를 마지막으로 하는 가장 긴 증가하는 부분 수열"의 길이를 저장해주었다. 이렇게 저장해두면, 답은 dp 배열 중 가장 큰 값이 되고, 이를 반복문을 돌 때 함께 업데이트 해주면 된다! #include #define MAX 1001 using namespace std; in..

문제 문제 바로가기> BOJ 2098번: 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 중요한 Point 1. 출발지가 어디든 그 결과는 같다. A → B → C → A B → C → A → B C → A → B → C 조금만 들여다보면, 순회하기 때문에, 어느 지점에서 출발하든 동일한 경로가 되는 것을 확인할 수 있다. 따라서 출발지를 고정 시킨 후 탐색을 진행한다! 2. 중복되는 경로가 생긴다. 이미 방문해서 최소값을 찾아 놓은 부분 경로의 경우, ..

문제 문제 바로가기> BOJ 12100번: 2048 (Easy) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 블록이 이동하는 순서를 미리 정해 놓은 뒤 시뮬레이션 해보는 문제다. 블록을 합칠 때, vector를 이용하면 좀 더 쉽게 문제를 해결할 수 있다. C++ #include #include #define MAX 21 #define CNT 5 using namespace std; int N, ans=0; int dir[CNT]; vector tmp; int map[MAX..

문제 문제 바로가기> 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..

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

문제 문제 바로가기> 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..

문제 문제 바로가기> 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