Little cabin in the woods

그래프를 표현하는 방법은 크게 3가지가 있다.1. 에지 리스트edge 를 중심으로 그래프를 표현하는 방법이다.  [ 출발 노드, 도착 노드 ] 형태의 배열로 에지를 표현하거나 edge에 가중치가 있는 경우는 [ 출발 노드, 도착 노드, 가중치 ] 형태의 배열로 표현한다.방향이 없는 그래프일 경우 출발 노드와 도착 노드의 순서가 중요하지 않으니 유의해서 확인해야 한다.벨만포드, 크루스칼 알고리즘 등에 사용하며, 노드 중심 알고리즘에는 자주 사용하지 않는다. ( = 특정 노드에서 출발하는 ~ 등 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. )import java.util.ArrayList;import java.util.List;public class Main{ static class Edg..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2504📌 문제 탐색하기목표주어진 괄호열을 읽고 그 괄호 값을 규칙대로 계산하여 출력하기해야 할 것1. 계산 규칙 이해하고, 구현하기2. 입력이 올바르지 못한 괄호열이면 반드시 0 출력하기입력[첫줄] 괄호열 (1 ≤ 괄호열의 길이 ≤ 30)아이디어1. 계산 규칙 이해하고 구현하기- '()' 의 값 = 2- '[]' 의 값 = 3- '(x)'의 값 = 2*x의 값- '[x]'의 값 = 3*x의 값- xy = x의 값+y의 값 괄호 문제는 스택을 이용해서 풀 수 있다는 것을 알고 있으니, 이 문제도 스택을 활용해서 해결할 수 있는지 생각해보자. 스택에 쌓을 때,  고려해야 할 점은 크게 세 가지이다.1. 짝이 맞는 지 확..

메서드 오버로딩과 오버라이딩은 면접에서 자주 등장하는 개념인 것 같으니 한 번 정리하고 넘어가도록 하자.일단 이 게시글에서는 오버로딩만 정리해보겠다. 오버로딩이란?한 클래스 내에서 같은 이름의 메서드를 매개변수의 개수나 타입, 또는 순서를 다르게 하여 여러 개 정의하는 것을 말한다. 아주 처음 이 개념을 접할 때는 이게 뭐 그리 특별하길래, 따로 이름까지 붙여서 정의하나 싶었다. 하지만 생각해보면 메서드도 변수와 마찬가지로 같은 클래스 내에서 서로 구별될 수 있어야 하기 때문에 각기 다른 이름을 가져야 하는 것이 자연스럽다. 그렇다면, 굳이 왜 이런 기능을 만들었을까? 오버로딩이 필요한 이유같은 기능을 하는 메서드들을 하나의 이름으로 통일해 묶으면, 메서드를 사용하는 쪽에서도 기억하기 쉽고 만드는 쪽에서..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/10799📌 문제 탐색하기목표잘려진 쇠막대기 조각의 총 개수 구하기해야 할 것1. 쇠막대기와 레이저 구분하기2. 각 쇠막대기가 몇 조각으로 잘리는 지 어떻게 구할까?입력[첫줄] 괄호 문자 ( 최대 길이 10^6 ) 아이디어1. 쇠막대기와 레이저 구분하기 '()'처럼 괄호가 인접하게 닫히면➡️ 레이저( 가 바로 인접하게 닫히지 않으면 ➡️ 쇠막대기, 만나는 첫번 째 ')'가 이 쇠막대기의 끝  2. 각 쇠막대기가 몇 조각으로 잘리는 지 어떻게 구할까? ➡️ 스택을 통해 괄호의 짝을 맞출 수 있다는 걸 이전 문제들을 풀며 알게 되었다. 이걸 응용할 수 없을까? 1) 일단, ( 과 ) 이 만났을 때 얘네가 레이저인지 쇠막대..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/9012📌 문제 탐색하기목표VPS인지 아닌지 판별하기해야 할 것1. VPS를 어떻게 판별할까?- VPS :  괄호가 순서에 맞게 잘 짝지어져 있는 조합입력[첫줄] 테스트 케이스의 수 T[둘째줄 ~ ] 괄호 문자열 ( 2 ≤ 괄호 문자열의 길이 ≤50)아이디어1. VPS를 어떻게 판별할까? 1단계. 괄호 문자열을 한 글자씩 탐색하며 스택의 가장 위에 있는 원소와 현재 문자를 비교한다.2단계. 만약 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞다면, 가장 위에 있는 원소를 스택에서 제거한다.3단계. 스택이 비어있거나, 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞지 않다면, 현재 문자를 스택에 삽입한다.4단계...

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/3986📌 문제 탐색하기목표입력된 단어 중 좋은 단어의 개수 세기해야 할 것1. 좋은 단어를 어떻게 판별할까?➡️선끼리 교차하지 않으면서 각 글자를 정확히 한개의 다른 위치에 있는 같은 글자와 짝 지을 수 있는 단어(예시 : ABAB는 좋은 단어x, AABB는 좋은단어, ABBA는 좋은 단어 )입력[첫줄] 단어의 수 N ( 1 ≤ N ≤ 100)[둘째줄 ~ ] 단어 ( 2 ≤ 단어의 길이 ≤10^5)아이디어1. 좋은 단어를 어떻게 판별할까? 이전에 푼 괄호 문제와 거의 유사한 유형의 문제이다.2024.12.15 - [STUDY/알고리즘&코딩테스트] - [백준] 4949. 균형잡힌 세상 (JAVA) 이 문제 역시 스택의..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/4949📌 문제 탐색하기목표문자열이 주어졌을 때, 균형잡힌 문자열인지 판단하기해야 할 것1. 균형잡힌 문자열인지 어떻게 판단할까?[규칙]- "("은 ")"을 만나야 한다. - "["은 "]"을 만나야 한다.-  괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.입력[첫줄~] 문자열. (100글자 이하)*종료조건 : "." 아이디어1. 균형잡힌 문자열인지 어떻게 판단할까? 문자열을 왼쪽부터 차례대로 탐색하다가 "(" 또는 "[" 가 나오면 스택에 쌓는다.")" 또는 "]"가 나오면 스택의 가장 윗 원소와 짝을 이룰 수 있는지 비교한다.짝을 이룰 수 있다면 스택에서 제거하고, 만약 ")"또는 "]"이 나왔는데 ..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/11003📌 문제 탐색하기목표D에 저장된 수를 출력하기해야 할 것1. D에 저장되는 규칙 이해하기2. L과 N의 범위를 고려하여 효율적인 알고리즘 설계하기입력[첫줄]  N : 주어질 수의 개수 , L ( 1 ≤ L ≤ N ≤ 5,000,000 )[둘째줄] N개의 A(i) ( -10⁹ ≤ A(i) ≤ 10⁹  ) 아이디어1. D에 저장되는 규칙 이해하기D(i) = A(i-L+1) ~ A(i) 중의 최솟값, 이때, i ≤ 0 인 A(i)는 무시할 것  (입력 예시)12 31 5 2 3 6 2 3 7 3 5 2 6 D(1) : A(1-3+1) ~ A(1) 중의 최솟값 = A(-1), A(0) , A(1) 중 최솟값 = A..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/5430📌 문제 탐색하기목표배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과 구하기해야 할 것1. 주어진 연산 구현하기R : 배열에 있는 수의 순서를 뒤집기D : 첫 번째 수를 버리기 (배열이 비어있는데 사용하면 error 출력)입력[첫줄]  테스트 케이스의 개수 T (1 ≤ T ≤100)[둘째줄 ~ 테스트 케이스 수만큼] 수행할 함수 p ( 1 ≤ p의 길이 ≤10^5 )배열의 원소 개수 n ( 0 ≤ n ≤ 10^5 )배열 [x1,...,xn] ( 1 ≤ xi ≤ 100 ) * 전체 테스트 케이스의 p의 길이의 합 + n의 합 ≤ 700,000아이디어1. 주어진 연산을 어떻게 구현할까?🤔 배열의 원소의 개수..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1021📌 문제 탐색하기목표원소를 주어진 순서대로 뽑아내려면 2번, 3번 연산을 최소 몇 번 수행해야 하는지 구하기해야 할 것1. 주어진 연산 구현하기- 1번연산 : 큐의 첫 번째 원소 뽑아내기 - 2번연산 : 큐의 첫 번째 원소를 뽑아 마지막에 삽입하기- 3번연산 : 큐의 마지막 원소를 뽑아 첫 번째 자리에 삽입하기 2. 2,3번 연산을 최소한으로 사용해서 주어진 수들을 뽑아내는 방법은?입력[첫줄]  큐의 크기 N , 뽑아낼 수의 개수 M (1 ≤ M ≤ N ≤ 50)  [둘째줄] 뽑아내려고 하는 수 M개 (1 ≤ 뽑아내려는 수 ≤ N )아이디어1. 주어진 연산 구현하기➡️ 큐에 삽입과 삭제가 양방향에서 일어나고 있..