➡️ 프로젝트 생성 0. 사전 준비 : Java 11 설치, Java 17 설치, IntelliJ 설치 Spring Boot 2.3.x 를 사용할 경우는 Java 11을 Spring Boot 3.0.x 를 사용할 경우에는 Java 17을 설치해야 한다. 글에서는 11로 설치했다가 다시 17로 재설치 하였다... ㅠ 더보기 1. Java 버전 확인하기 cmd 창에 java -version 명령어를 입력하면 자바 버전을 확인 할 수 있다. 현재 자바 8을 사용하고 있음을 확인 했다. Java 11을 설치해보도록 하자. 2. Java 11 설치하기 www.oracle.com/java/technologies/javase-jdk11-downloads.html 위 링크에서 jdk-11.0.9 를 설치 하면 된다. ..

[Gold III] 줄 세우기 - 2252 문제 링크 성능 요약 메모리: 46084 KB, 시간: 4360 ms 분류 그래프 이론, 위상 정렬 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 ..

Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc...

[Silver V] 수 정렬하기 2 - 2751 문제 링크 성능 요약 메모리: 134424 KB, 시간: 692 ms 분류 정렬 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 💡 나의 접근 주어진 N의 개수가 1,000,000이기 때문에 O(N^2) 시간복잡도를 가지게 되면 터지게 된다. 그래서 O(NlogN)이나 O(N) 시간복잡도를 가지는 정렬을 생각해 보아야 할 것이다. A..

Counting Sort (계수 정렬) 이란? 계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다. 더보기 백준 문제 https://www.acmicpc.net/problem/2751 과정 과정은 간단하다. 1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기 2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기 3. 각 값의 개수를 누적으로 바꾸기 4. 뒤에서부터 자리 찾아주기 위 순서에 따라서 위 arr 배열을 정렬해보자 1. 가장 큰 값을 찾는다. ➡️ max = 5 2. 각 값의 개수를 담는다. arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다. 3. 각 값의..

[Silver III] 계단 오르기 - 2579 문제 링크 성능 요약 메모리: 11608 KB, 시간: 76 ms 분류 다이나믹 프로그래밍 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 ..

[Bronze I] 비밀편지 - 2596 문제 링크 성능 요약 메모리: 11476 KB, 시간: 72 ms 분류 구현, 문자열 문제 설명 병현이는 지은이에게 문자 A, B, C, D, E, F, G, H 로 쓰여진 편지를 날마다 보내는데, 컴퓨터로 보내는 비밀편지로, 한 문자마다 0 또는 1인 숫자 여섯 개를 사용하여 보낸다. 둘 사이의 약속은 다음과 같다. A 000000 B 001111 C 010011 D 011100 E 100110 F 101001 G 110101 H 111010 병현이가 어느 날 001111000000011100 을 보내면 지은이는 이것을 BAD로 이해하게 된다. 그런데 둘 사이에 약속이 잘 만들어져 있기 때문에, 통신에 문제가 생겨서 한 문자를 표시하는 여섯 숫자 중 어느 한 숫..

[Silver I] 주지수 - 15724 문제 링크 성능 요약 메모리: 121296 KB, 시간: 648 ms 분류 다이나믹 프로그래밍, 누적 합 문제 설명 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 는 1 ..

[Silver III] 안테나 - 18310 문제 링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 프리뷰 답을 도출하는 데 살짜쿵 버벅했지만 막상 코드를 짜고보니 너무너무 간단해서 이게 맞나 싶었다... 돌려보니 이게 돌아가서 당황했다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 성능 요약 메모리: 40748 KB, 시간: 348 ms 분류 그리디 알고리즘, 수학, 정렬 문제 설명 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의..

[Silver I] 트럭 - 13335 문제 링크 성능 요약 메모리: 12844 KB, 시간: 96 ms 분류 자료 구조, 구현, 큐, 시뮬레이션 문제 설명 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의..

10진 문자 0 NULL 48 0 65 A 97 a

[Silver II] 화학식량 - 2257 문제 링크 성능 요약 메모리: 11516 KB, 시간: 80 ms 분류 자료 구조, 스택, 문자열 문제 설명 우리가 널리 사용하는 H2O(물), CH3COOH(아세트산)과 같은 화학식은 알파벳과 숫자, 그리고 괄호로 구성된다. 먼저 알파벳은 원자를 나타내는 것으로 H는 수소(Hydrogen), C는 탄소(Carbon), O는 산소(Oxygen) 원자를 뜻한다. 또한 원자를 나타내는 알파벳 뒤에 따르는 숫자는 그 원자가 몇 개 포함되어 있는지를 뜻한다. 따라서 COOHHH 분자는 CO2H3로 나타낼 수 있다. 이 문제에서, 숫자는 항상 2 이상 9 이하로만 입력으로 주어진다. 따라서 CO23과 같이 숫자가 두자리인 경우는 없다. 물의 화학식을 보고 물은 두 개의 ..

[Silver II] DNA 비밀번호 - 12891 문제 링크 성능 요약 메모리: 34668 KB, 시간: 208 ms 분류 슬라이딩 윈도우, 문자열 문제 설명 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에..

[Silver II] 꽃길 - 14620 문제 링크 성능 요약 메모리: 15968 KB, 시간: 132 ms 분류 브루트포스 알고리즘 문제 설명 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다. 꽃을 심을 때는 주..

[Silver II] 친구 - 1058 문제 링크 성능 요약 메모리: 11984 KB, 시간: 84 ms 분류 브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색 문제 설명 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. 입력 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 ..