백준 | 1915번. 가장 큰 정사각형 찾기 - DP 문제
🟦 백준 1915번. 가장 큰 정사각형 찾기 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 풀이 가장 큰 정사각형 넓이 구하기 == 가장 큰 한 변의 길..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 14.
백준 | 9252번. LCS - 최장 공통 부분 수열 찾기 - DP 문제
🟦 백준 9252번. 최장 공통 부분 수열 찾기 (LCS) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS | longest common subseuence : 최장 공통 부분 수열 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 문자열과 관련된 DP는 이 문제와 비슷한 방식으로 풀이 가능한 것이 많다. 이 문제를 꼼꼼히 숙지하여 연습할 것 문제 LC..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 14.
intelliJ_gitHub 연결하기
왼쪽엔 깃허브 오른쪽엔 깃허브에 연결을 원하는 인텔리제이 프로젝트를 켠다. 깃허브 레포지토리를 생성하고 주소를 복사한다. 인텔리제이 하단의 ‘터미널’에 다음과 같이 입력한 뒤 주소도 붙여서 연결 git init git add . git commit-m "first commit" git branch -M 이름(main) git remote add origin 복붙한 주소 git push -u origin 이름(main)
- Web(웹)_관련 공부 모음/[강의] intellij_Gradle
- · 2023. 7. 12.
[해결] IntelliJ | Cannot open Local Terminal
[해결] IntelliJ | Cannot open Local Terminal IntelliJ의 터미널을 실행시키면 계속해서 이 에러가 발생했다. Cannot open Local Terminal Error running process: CreateProcess failed. Code 2 이 문제는 [파일/설정/도구/터미널] 에 들어가서 powershell.exe로 되어 있는 Shell path 를 cmd.exe 로 변경해주면 된다.
- Web(웹)_관련 공부 모음/[강의] intellij_Gradle
- · 2023. 7. 12.
백준 | 10844번. 계단 수 구하기 - DP 문제
🟦 백준 10844번. 계단 수 구하기 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 D[i][j] 의 정의 : i자릿수에서 j로 끝나는 계단 수 구하기 경우의 수 나누..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 12.
백준 | 11726번. 타일 채우기 - DP 문제
🟦 백준 11726번. 타일 채우기 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 문제 분석 : 2 X N 크기의 직사각형을 1 X2 or 2 X 1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 1) D[N] = 2 X N크기의 직사각형을 타일로 채울 수 있는 경우의 수 2) D[1] = 1. D[2] = 2. D[3] = 3. D[4] = 5 … 이런 식으로 확장된다. 규칙성이 보인다. 즉. D[i] = D[..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 12.
백준 | 9095번. 1, 2, 3 더하기 - DP 문제
⬛ 백준 9095번. 1, 2, 3 더하기 - DP 문풀 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 11.
섹션 3. 코딩테스트 [실전편] - 11. 동적 계획법
섹션 3. 코딩테스트 [실전편] - 11. 동적 계획법 ⬛ 11. 동적 계획법 ⬛ 11-1. 동적 계획법 DP 🟦 동적 계획법 복잡한 문제를 여러 개의 단순한 문제로 분리하여, 부분 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방식 🟧 동적계획법 원리와 구현 1) 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2) 작은 문제들이 반복되어 나타나고, 이 작은 문제들의 결과값이 항상 같아야 한다. 3) 메모이제이션 기법을 사용 : 모든 작은 문제들을 한 번만 계산하여 미리 DP 테이블에 저장해놓고, 추후 재사용 시 DP 테이블을 이용하는 방식 4) 동적 계획법 구현 방식 2가지 : (1) 톱 다운 방식 (2) 바텀 업 방식 🟦 예시 : 피보나치 수열 문제 피보나치 수열은 규칙성이 존재하는데 그..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 11.
섹션 3. 코딩테스트 [실전편] - 10. 조합
섹션 3. 코딩테스트 [실전편] - 10. 조합 ⬛ 10. 조합 동적 계획법을 이해하는 기초가 됨 조합 점화식 도출 방법을 제대로 이해하자. ⬛ 10-1. 조합 알아보기 🟦 조합 Combination | nCr 조합 : n개의 숫자에서 r개를 뽑는 경우의 수 cf. 순열 : n개의 숫자에서 r개를 뽑고, 그 순서를 나열 일반적으로 조합을 구현할 때는 점화식을 이용 🟧 조합 구현하는 방식 1. 특정 문제를 가정하기 예를 들어. 5개의 데이터 중 3개를 선택하는 경우의 수를 구한다고 가정해보자. 2. 모든 부분 문제가 해결됐다고 가정하고, 지금 문제만 생각하기 5개 중에서 4개의 데이터들의 선택 여부를 모두 고려했다고 생각하고. 지금 시점은 가장 마지막 (5번째) 데이터의 선택 여부를 고려하는 중이라고 생각..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 10.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (3) 세그먼트 트리
⬛ 09-4. 세그먼트 트리 🟦 세그먼트 트리 주어진 데이터들의 **‘구간 합’과 ‘데이터 업데이트’**를 빠르게 수행하기 위해 고안해낸 자료구조 세그먼트 트리의 종류 : 1) 구간합, 2) 최대/최소 구하기 구현 단계 : (1) 트리 초기화 하기 (2) 질의값(요구사항) 구하기 (3) 데이터 업데이트 🟧 세그먼트 트리의 구현 단계 1) 트리 초기화 하기 (1) 리프 노드의 개수가 데이터 개수 N 이상이 되도록 2^k ≥ N을 만족하는 k의 최솟값 구한 뒤 2^k * 2를 트리 배열의 크기로 정의 ex) 샘플 데이터 = {5, 8, 4, 3, 7, 2, 1, 6} : N = 8 2^3 = 8 따라서 배열크기는 2^3 X 2 = 16 크기로 정의 (2) 리프 노드에 원본 데이터를 입력한다. 이때 리프 노드..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 10.
백준 | 1922번. 네트워크 연결 - 최소비용 신장트리
🟦 백준 1922번. 네트워크 연결 | 최소비용 신장트리 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 7.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (2) 이진 트리
⬛ 09-3. 이진 트리 🟦 이진 트리 (binary tree) 각 노드와 자식 노드의 개수(차수)가 2 이하로 구성되어 있는 트리 종류 : 편향 이진 트리, 완전 이진 트리, 포화 이진 트리 보통 1차원 배열의 형태로 표현 🟧 트리의 노드와 배열 인덱스 간 상관 관계 루트 노드 : index = 1; 부모 노드 : index = index / 2;// 현 인덱스 상위로 이동 왼쪽 자식 노드 : index = index*2; 오른쪽 자식 노드 : index = index*2 + 1; 🟧 트리의 순회 전위 순회 : U L R 중위 순회 : L U R 후위 순회 : L R U 🟦 백준 1991번. 트리 순회하기 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorde..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 7.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (1) 트리, 트라이
섹션 3. 코딩테스트 [실전편] - 09. 트리 🏓 선형 vs 비선형 자료구조 1) 선형 자료구조 : 현재 자료와 뒤 자료가 1:1 관계 2) 비선형 자료구조 : 현재 자료와 뒤 자료가 1:n 관계 ⬛ 09. 트리 ⬛ 09-1. 트리 사이클 X. 1개의 루트 노드만 가지고 있는 원소들 간의 1대 n 관계를 갖는 비선형 자료구조 상위 원소 → 하위 원소로 확장되는 구조 사이클X, 간선 N-1개 연결 그래프 🟧 트리의 구성요소 루트 노드 : 트리 가장 상위의 노드 부모 노드 : 두 노드 사이 관계에서 상위 노드 자식 노드 : 두 노드 사이 관계에서 하위 노드 리프 (단말) 노드 : 트리 가장 하위의 말단에서 자식 없는 노드 서브 트리 : 전체 트리에 속해있는 작은 하위 트리 각각의 노드는 자식 노드의 수만큼..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 7.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (6) 최소 비용 신장 트리
⬛ 08-7. 최소 신장 트리 🟦 신장 트리 n개 정점. 무방향 그래프에서 (사이클 없이) 간선 n-1 개로 이루어진 부분 그래프 🟦 최소 비용 신장 트리 정점 n개, 간선 n-1개. 사이클 X . 연결 그래프인 신장 트리의 조건을 만족하면서 총 간선의 가중치의 합이 최소인 트리 그래프의 모든 노드들을 연결하는 부분 그래프 중 가중치 합이 최소인 트리를 의미 🟧 1) 크루스칼 알고리즘 - (I) 가중치 ‘높은’ 간선 제거하여 최소비용 만듬 (1) 그래프의 모든 간선들 가중치 내림차순 정렬 (2) 사이클 X, 단절 X 가장 큰 간선 제거 (3) 간선 n-1개 남을 때까지 반복 후 종료 🟧 1) 크루스칼 알고리즘 - (II) 가중치 ‘낮은’ 간선 삽입하며 최소비용 만듬 (1) 그래프의 모든 간선들 가중치 오..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 6.
백준 | 2660번. 회장 뽑기 - 플로이드-워샬
🟦 백준 2660번. 회장 뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 6.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (5) 플로이드 워샬
🔎 벨만-포드 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와샬(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-6. 플로이드-워셜 🟦 플로이드-워셜 알고리즘 플로이드-워셜 : 모든 노드 간에 최단 경로 탐색 알고리즘 음수 가중치 엣지 존재해도 수행 가능 DP 동적계획법 원리 이용하여 접근 전체 경로의 최단 경로는 부분 경로의 최단경로 조합이다. //점화식 // s -> E까지의 최단 경로 vs s-> k, k->e 를 껴서 가는 경로 // 중 작은 값으로 업데이트한다. D[S][E] = ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 5.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (4) 벨만-포드
🔎 벨만-포드 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와셜(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-5. 벨만-포드 알고리즘 🟦 벨만- 포드 알고리즘 벨만-포드 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 알고리즘 cf. 다익스트라와 다른 점 : 음수 가중치 엣지 있어도 수행 가능 ! 보통 음수 사이클 존재 여부 판별하는 문제가 多 출제 🟧 벨만-포드 핵심 이론 1) 에지 리스트로 그래프 구현 후, 최단 경로 배열 초기화 2) 모든 엣지 확인하며 정답 배열 업데..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 5.
백준 | 1504번. 특정한 최단 경로 - 다익스트라
🟦 백준 1504번. 특정한 최단 경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 3.