본문 바로가기
◀ PREV [1] [2] [3] [4] [···] [16] NEXT ▶
백준 18870 : 좌표압축 (TreeMap) TreeMap  문제수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.입력첫째 줄에 N이 주어진다.둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.출력첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.제한1 ≤ N ≤ 1,000,000-109 ≤ Xi ≤ 109예제 입력 1 복사52 4 -10 4 -9예제 출력 1 복사2 3 0 3 1예제 입력 2 복사61000 999 1000 999 100.. 2024. 12. 19.
빠른 입출력 실험하기(버퍼리더 + 스트링빌더) 오름차순 정렬 후 하나씩 뱉는 문제를 풀다가 뭐가 젤 나은지 궁금해져서 해봤다 일단 버퍼리더랑 스트링빌더 조합이 가장 빨랐다 1. 스캐너 + stringbuilder진짜 정말 느리다..import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException{ Scanner in = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int n = in.nextInt(); int[] arr= new int[n]; for (int i =0; i  2.. 2024. 12. 17.
가격대 별 상품 개수 구하기 GROUP BY https://school.programmers.co.kr/learn/courses/30/lessons/131530 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr • 풀이 처음에는 CASE 구문으로 풀어보려고 했다가 실패..하고 풀이를 찾아보니 나눗셈을 이용해서 푸는 방법이 있었다 만원 단위로 그룹을 짓는걸 나눗셈과 FLOOR 메서드를 이용해서 만 단위로 해서 처리하고다시 * 10000을 해서 만원 단위로 깔끔하게 나오게 끊는 쿼리 SELECT PRICE, FLOOR(PRICE/10000) FROM PRODUCT위 처럼 만의자리 숫자만 남게 나와서 해당 숫자를 기준으로 그룹바이를 하면 1만원대.. 2만.. 2024. 12. 17.
백준 1730 : 판화 (구현) 문제W대학교 미술대학 조소과에서는 지루한 목판화 작업을 하는 학생들을 돕기 위해 판화 기계를 제작하였다.기계는 로봇 팔이 쥔 조각도를 상하좌우 네 방향으로 움직일 수 있는 구조로서, 조각도 아래에 목판을 놓으면 그 위에 선들을 자동으로 그어주는 기능을 가지고 있다.목판에는 N2개의 점들이 일정한 간격으로 N행 N열의 격자모양을 이루며 찍혀있다. 처음 로봇의 조각도를 올려놓는 위치는 항상 이 점들 중 맨 왼쪽 맨 위의 꼭짓점이다.로봇 팔을 움직이는 명령의 순서가 주어졌을 때, 목판 위에 패인 조각도의 혼적을 출력하는 프로그램을 작성하시오.판화 기계는 작동 도중 로봇 팔이 격자 바깥으로 나가도록 하는 움직임 명령을 만나면, 무시하고 그 다음 명령을 진행한다.입력첫째 줄에 목판의 크기 N (2 ≤ N ≤ 10.. 2024. 12. 16.
입양 시각 구하기(1) - GROUP BY, DATE 자료형 변환 https://school.programmers.co.kr/learn/courses/30/lessons/59412 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr • 24시 형식으로 시간 구하기TO_CHAR(DATETIME,'HH24') • 24시 형식으로 시간 01, 02, 03.. 형태가 아닌 1, 2, 3 형태로 구하기TO_CHAR(DATETIME,'FMHH24')FM을 붙이면 Fill Mode로 동작해서 09가 아닌 9로 들어가게 된다 • TO_CHAR로 문자열로 변환한 DATE 자료형 숫자로 변환하기TO_NUMBER(TO_CHAR(DATETIME,'HH24')) HOURTO_NUMBER 메서드로.. 2024. 12. 16.
년, 월, 성별 별 상품 구매 회원 수 구하기 - group by https://school.programmers.co.kr/learn/courses/30/lessons/131532 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 구매기록이 있는 회원 아이디 월별 조회SELECT USER_ID, TO_CHAR(SALES_DATE, 'YYYY-MM') ODATE, SALES_DATE FROM ONLINE_SALE GROUP BY USER_ID, TO_CHAR(SALES_DATE, 'YYYY-MM'), SALES_DATE 2. 년, 월, 성별별로 그룹바이하면서 id 중복되지 않게 세어주기 SELECT TO_CHAR(SALES_DATE,'YYYY') YE.. 2024. 12. 16.
백준 3085 사탕게임 문제상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.사탕의 색이 다른 인접한 두 칸이 존재하는.. 2024. 12. 15.
11068 : 회문인 수 문제어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다. 입력입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64 이상 1,000,000 이하인 하나의 정수로 주어진다.출력출력은 표준출력.. 2024. 12. 15.
대여 횟수가 많은 자동차들의 월별 대여 횟수 구하기 - 그룹바이 https://school.programmers.co.kr/learn/courses/30/lessons/151139 • 풀이 1. 8월~10월 중 대여횟수가 5회 이상인 car_id를 구한다 select car_id from CAR_RENTAL_COMPANY_RENTAL_HISTORY WHERE TO_CHAR(START_DATE,'YYYY-MM') BETWEEN '2022-08' AND '2022-10' GROUP BY CAR_ID HAVING COUNT(car_id) >= 5 2. 안에서 구해진건 car_id 뿐이고 전체 그룹쿼리에서는 다시 한번 위처럼 8~10월 .. 2024. 12. 10.
자동차 대여 기록에서 대여중 / 대여 가능 여부 구분하기 - 조인 https://school.programmers.co.kr/learn/courses/30/lessons/157340 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr차량 대여 일지를 보고 특정 날짜에 대여중인지 아닌지를 구분하는 쿼리 10/16/일에 대여중인 차량의 id를 구하는 쿼리SELECT CAR_ID FROM CAR_RENTAL_COMPANY_RENTAL_HISTORYWHERE '2022-10-16' BETWEEN TO_CHAR(START_DATE, 'YYYY-MM-DD') AND TO_CHAR(END_DATE, 'YYYY-MM-DD' 위의 id에 포함되면 대여중, 아니면 대여 가능으로 표기한다CA.. 2024. 12. 9.
상품을 구매한 회원 비율 구하기 - 플머 https://school.programmers.co.kr/learn/courses/30/lessons/131534 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr • 풀이 2021년도에 가입한 유저 ID, 유저수를 USER_INFO에서 빼온다둘이 동시에 빼오지는 못해서 각각 서브쿼리로 빼오고  -- 2021 가입한 유저 ID ( SELECT USER_ID FROM USER_INFO WHERE TO_CHAR(JOINED,'YYYY') LIKE '2021%') U-- 2021 가입한 유저 수 ( SELECT COUNT(USER_ID) CNT .. 2024. 12. 4.
그룹별 조건에 맞는 식당 목록 출력하기 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/131124 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr • 풀이 조인된 테이블에서 가장 많이 리뷰를 작성한 사람을 찾아서 가져오는 문제 1. 리뷰 가장 많이 한 사람이 리뷰 몇번이나 했는지를 찾기SELECT MAX(COUNT(1)) FROM REST_REVIEW GROUP BY MEMBER_ID 2.  해당 횟수만큼 리뷰한 멤버아이디들을 조회하기 SELECT MEMBER_ID FROM REST_REVIEW GROUP BY MEMBER_ID HAVING COUNT(1) =.. 2024. 12. 3.
백준 3273 : 두 수의 합 문제n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 입력첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)출력문제의 조건을 만족하는 쌍의 개수를 출력한다.예제 입력 1 복사95 12 7 10 9 1 2 3 1113예제 출력 1 복사3 • 풀이 전형적인 투 포인터, 정렬 후 양 끝에서 가운데로 오면서 탐색하는 구조 중복되는 숫자도 없어서 오름차순 정렬 후 투포인터로 풀렸다import java.io.*;import j.. 2024. 12. 1.
백준 10431 : 줄세우기 문제초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이.. 2024. 12. 1.
문자열 관련 메서드, 사용법 정리 contains(특정 문자열) indexOf  메서드 str.chartAt(i) string.charAt(i) == 'A' 식으로 비교 문자열 뒤집기StringBuilder를 사용하면 편함StringBuffer sb = new StringBuffer(s[i]);String reverse = sb.reverse().tostring(); Character.isAlphabetic(char) str.indexOf(str.charAt(i))==i String sb = new StringBuilder(s1).reverse().toString();문자열 뒤집기, StringBuilder를 이용 String s1 = s.toUpperCase().replaceAll("[^A-Z]", "");replaceAll에 정규식을.. 2024. 11. 27.
오프라인/온라인 판매 데이터 통합하기 https://school.programmers.co.kr/learn/courses/30/lessons/131537?language=oracle 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr !오프라인은 USER_ID가 없기에 NULL로 넣는다!ORDER BY는 UNION 할 시에도 마지막에 넣어야 한다!ORDER BY 할때 SELECT에 쓴 순서대로 지정해서 굳이 컬럼명 안쓰고도 정렬할 수 있다SELECT TO_CHAR(SALES_DATE,'YYYY-MM-DD') AS SALES_DATE, PRODUCT_ID, USER_ID, SALES_AMOUNTFROM ONLINE_SALE WHERE TO_CHA.. 2024. 11. 22.
조건에 맞는 회원수 구하기(DATE 문자열 변환) https://school.programmers.co.kr/learn/courses/30/lessons/131535?language=oracle 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr TO_CHAR(DATE형 컬럼, 포맷)으로 DATE를 문자열로 변환할 수 있다 SELECT COUNT(*) FROM USER_INFO WHERE TO_CHAR(JOINED,'YYYY') = '2021' AND AGE BETWEEN 20 AND 29; 2024. 11. 19.
상위 N개 레코드(N개 출력 - ROWNUM, FROM 절 서브쿼리) https://school.programmers.co.kr/learn/courses/30/lessons/59405?language=oracle 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 들어온 날짜가 가장 오래된 동물의 이름을 고르는 문제 SELECT NAME, DATETIMEFROM ANIMAL_INSWHERE ROWNUM  ROWNUM 키워드로 1개를 뽑아냈지만 정렬이 제대로 되지 않았다 -- 정답아래처럼 FROM 절 서브쿼리로 정렬된 컬럼을 먼저 뽑아낸 다음 갯수를 제한해주는 방식으로 제대로 가장 먼저 들어온 원숭이를 찾을 수 있었다SELECT NAMEFROM (SE.. 2024. 11. 19.
백준 2108 : 통계학(구현?) 문제수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.산술평균 : N개의 수들의 합을 N으로 나눈 값중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값최빈값 : N개의 수들 중 가장 많이 나타나는 값범위 : N개의 수들 중 최댓값과 최솟값의 차이N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.출력첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올.. 2024. 11. 19.
백준 18110 ( 구현, 정렬, 소수점 처리) 문제solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다. ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을.. 2024. 11. 18.
백준 1927 : 최소 힙 문제널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경.. 2024. 11. 15.
백준 11047 동전 0 (그리디) 문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.예제 입력 1 복사10 4200151050100500100050001000050000예제 출력 1 복사6예제 입력 2 복사10 47901510501005001000500010000.. 2024. 11. 14.
백준 2839 : 설탕배달(DP) 문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)출력상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로.. 2024. 11. 11.
백준 12869 : 뮤탈리스크 (bfs) bfs인데 visited가 3차원이였던 문제  문제수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.첫 번째로 공격받는 SCV는 체력 9를 잃는다.두 번째로 공격받는 SCV는 체력 3을 잃는다.세 번째로 공격받는 SCV는 체력 1을 잃는다.SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해.. 2024. 11. 8.
백준 4179 불! (bfs) 문제지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.불은 각 지점에서 네 방향으로 확산된다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.지훈이와 불은 벽이 있는 공간은 통과하지 못한다.입력입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.다음 입력으로 R줄동안 각각의 미로 행이 주어진다.각각의 문자들은 다음을 뜻한다.#: 벽.: 지나갈.. 2024. 11. 6.
백준 16234 : 인구 이동 (dfs) 문제N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.오늘부터 인구 이동이 시작되는 날이다.인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고.. 2024. 11. 4.
백준 2589 : 보물섬 (bfs) 문제보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동.. 2024. 11. 3.
백준 15686 : 치킨배달(백트래킹) 문제크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.예를 들어, 아래와 같은 지도를 갖.. 2024. 11. 3.
백준 17298 오큰수 (스택) 문제크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,00.. 2024. 11. 1.
백준 1325 : 효율적인 해킹 (dfs) 문제해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.입력첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 .. 2024. 11. 1.

티스토리툴바