Algorithm

백준 18428 감시 피하기 Gold V - JAVA 📌https://www.acmicpc.net/problem/18428문제 설명문제 풀이접근 💡2차원 배열에서 주어지는 정보는 선생님의 위치와 학생의 위치이다. 장애물을 빈 칸에 세 개를 놓았을 때 감시를 피할 수 있는 경우를 찾아야 한다. 장애물을 3개 놓는 경우는 조합으로 생각하면 된다. 빈칸의 좌표를 리스트로 받아서 그 리스트 안에서 조합을 뽑아 모든 경우의 수를 탐색할 수 있다.이 때 빈칸의 최소 갯수는 3개이고 최대 갯수는 선생님의 최소 수는 1, 학생의 최소 수는 1 이다. N의 최댓값이 6이므로 6 * 6 = 36, 36 - 2 = 34,  34C3의 경우의 수가 생긴다. 이는 5,984의 경우의 수가 생기며 이는 완전탐색 하기에 충분한..

백준 3980 선발 명단 Gold V - JAVA 📌https://www.acmicpc.net/problem/3980문제 설명문제 풀이접근 💡요새 최적화에 관심이 많아져서 완전탐색을 떠올리지 않고 문제에 접근했던 것 같다.. 반성하고 자숙하자.. 모든 알고리즘의 시초는 완전탐색이다!!! 본론으로 들어가서 현재 선택하고 있는 포지션을다음 선수는 선택할 수 없을 때 포지션 점수의 최댓값을 구하는 문제이다.모든 포지션을 선택했을 때 최댓값을 갱신해주면 되는 간단한 문제였다. 한 행(선수)의 포지션을 선택했을 때, 다음 행(선수)로 넘어가서 겹치지 않는 포지션을 선택하는 모~~~~~~~든 경우의 수를 구해 최댓값을 구하면 된다. 코드로 알아보자  코드 💡import java.io.BufferedReader..

백준 15662 톱니바퀴 (2) Gold V - JAVA 📌https://www.acmicpc.net/problem/15662문제 설명문제 풀이접근 💡사실 이 문제는 엄청난 아이디어를 떠올려야 한다기 보다는 문제에서 주어진 조건 그대로 구현하면 되는 시뮬레이션 문제이다. 이 문제에 접근하기 위해 가장 중요하게 생각해야 하는 부분은 톱니바퀴가 회전하면 양 옆 톱니바퀴는 반대로 회전하게 된다는 것이다.이 점을 활용하여 문제에 천천히 접근해보자. 우선 테스트케이스 1번을 살펴보자. 4개의 톱니바퀴가1010111101111101110011100000010 으로 되어있다. 톱니바퀴의 12시부터 차례로 0, 1, 2 ... 인덱스가 부여된다.우리가 살펴봐야 할 부분은 톱니바퀴가 맞물리는 2번 인덱스와 6번 인덱..

백준 2156 포도주 시식 Silver I - JAVA 📌https://www.acmicpc.net/problem/2156문제 설명문제 풀이접근 💡문제에서 주어진 조건 중 와인 3잔을 연속해서 마실 수 없다는 조건을 잘 생각해보자.현재 위치에서 OOX, OXO, XOO의 경우를 생각해 볼 수 있는데, 이 경우 중에 어떤 경우가 제일 많이 먹을 수 있는 경우인지 판단해야 한다. 표로 그려 예시를 확인해보자. 현재 선택하고 있는 와인은 3번째 와인이라고 가정한다. dp 배열을 만들어보자.dp[1] = wine[1], dp[2] = wine[1] + wine[2]로 초기화 해준다.  1. OOX 의 경우와인순서 (i)123456선택여부OOX    이 경우에는 dp[i - 1]이 된다. 2. OXO의 경우와..

백준 2512 예산 Silver II - JAVA 📌https://www.acmicpc.net/problem/2512문제 설명문제 풀이접근 💡이 문제의 핵심은 주어진 총액을 초과하지 않고 상한액을 설정하는 것이다.지방마다 요청하는 예산이 주어지고 모든 요청을 배정할 수 없으면 상한액을 정해서 초과분을 상한액에 맞춰 배정하야 한다.상한액을 계속 조정해가면서 총 배정액이 주어진 총액을 넘지 않도록 해야한다.이 조건 속에서 가능한 최대 상한액을 찾아야 한다. 최대 예산이 10억이므로 이분탐색으로 효율적으로 상한액을 찾아보자! 1. 탐색 범위를 설정해보자.    정렬을 한 후에 최소상한액을 0, 최대 상한액을 arr[N - 1]과 주어진 총액의 최댓값으로 설정한다.2. 상한액을 logN으로 탐색해보기 위해 ..

💡위상정렬이란?위상정렬은 방향이 존재하는 그래프에서 정점들의 진행 순서를 지키며 모든 정점을 순서대로 나열하는 알고리즘이다. 간단한 예시로, 대학교 수업 과정을 생각해 보자.자료구조 수업을 들으러면 먼저 프로그래밍 기초를 들어야 한다.알고리즘 수업을 들으려면 먼저 자료구조를 들어야 한다.운영체제 수업을 들으려면 먼저 자료구조를 들어야 한다. 이런 선수과목 관계를 위상정렬하게 되면 다음과 같은 순서가 나올 수 있다.👨🏻‍💻 프로그래밍 기초 -> 자료구조 -> 알고리즘 -> 운영체제 ❗️위상정렬의 주요 특징순환(싸이클)이 없는 유향 그래프에서만 가능하다.같은 그래프여도 여러 가지 위상 정렬이 나올 수 있다.주로 스케쥴링이나 작업 순서 결정, 선수 과목 계산 등에 활용한다.   위상정렬 구현해 보기 1..

백준이나 SWEA에서 문제를 풀다보면테스트 케이스를 확인하기 위해 계속 복사+붙혀넣기를 하기 귀찮을 때가 있다. SWEA 같은 경우에는 입력 테스트케이스를 복붙하여 입력할 때 가끔 오류가 날 때도 있다.. 우리는 평소 아래와 같이 입출력을 사용한다! 디버깅을 하다보면 디버깅 할 때마다 이 테스트 케이스를 계속 복사 붙혀넣기 해야 하기 때문에상 당 히번거롭다... 하지만..! 디버깅때 매번 테스트케이스 입력 없이 한번 입력해두고 디버깅을 할 수 있는 방법이 있다!!!!!   1. 아래와 같이 코딩테스트를 연습할 프로젝트를 생성 하고 클래스명 왼쪽에 있는 초록색 실행버튼을 눌러준다 2. 텍스트 파일 input.txt와 output.txt 파일을 만들어 준다! 3. 우측 상단에 Main (클래스이름) -> E..

백준 13418 학교 탐방하기 GoldIII - JAVA 📌https://www.acmicpc.net/problem/13418문제 설명문제 풀이접근 💡0번에서 시작하는 최소신장트리를 구하는 문제이다.0은 오르막길, 1은 내리막길이고 오르막길인 간선에서만 비용이 1 증가한다. 문제에서는 최악의 비용이 발생하는 경우와 최선의 비용이 발생하는 경우의 비용 차를 요구한다. 최소신장트리 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 사용하여 풀 수 있다.두 알고리즘 모두 그리디 알고리즘에 기반한 알고리즘이기 때문에, 0을 우선순위로 두는 정렬, 1을 우선순위로 두는 정렬을 하여 최대비용과 최소 비용을 구해보자  코드 💡1. 크루스칼 풀이import java.io.BufferedReader;import jav..

SWEA 2477 차량 정비소 - JAVA 📌https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy 풀이 기간으로는 이틀 좀 안걸렸어요.. 코응애한테는 너무 버거운 문제였다.요새 모의 SW 역량테스트를 조금씩 건드려 보고 있는데,마치 헬스로 따지면 벤치프레스 뽑지도 못하는 100kg을 뽑으려고 안간힘 쓰는데 절대 뽑을 수 없는 그런 느낌? 다시 기본기부터 천천히..점진적 과부하 식으로 마음 급하게 먹지 않고 기본기부터 천천히 다져야 겠다는 생각이 들었다!문제 풀이접근 💡지문에서 요구하는 것은 고객이 어느 창구에 머물렀냐는 것이다.고객의 정보를 가지는 클래스를 하나 선언하자.static cl..

부분 집합이란?A라는 집합이 있고 B라는 집합이 있다고 가정해보자.A라는 집합이 B라는 집합에 속하면 A는 B의 부분 집합이 된다.예를 들어, 집합 {1, 2, 3}의 부분 집합은 {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 으로 자기 자신까지 포함해서 총 8개가 된다. 즉 부분 집합의 개수는 원래 집합의 원소의 개수를 N이라고 할 때, 2^N 개라고 할 수 있다.먼저 비트 연산자를 알아보자. 위에서 설명한 부분 집합의 개수를 구하는 것을 비트 연산자로1  이렇게 나타 낼 수 있다.1을 2진수로 나타냈을 때 0001이고, N이 3일 때 3만큼 왼쪽으로 비트를 이동시키면 1000으로 8이 된다.public class Main { public static voi..