두부의 코딩일기

https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 🔶 풀이 11명 선수의 포지션 별 능력이 입력된다. 포지션 별로 중복되지 않은 선수 11명을 뽑아서 최대 점수를 구하라. 완전 탐색으로 진행하게 되면 경우의 수는 11! (39,916,800)로 시간 초과가 발생할 수 있다. 때문에 백트래킹을 사용해서 시간 복잡도를 줄여야한다. 위 문제에서 능력치가 0인 경우에는 해당 포지션에 설 수 없다고 했다. 또한, 이미 선발된 선수가 또 다시 선발될 수 없으므로 selected[] 배..

https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 🔶 풀이 BFS로 충분히 해결할 수 있는 문제. (0, 0)에서 시작해서 (x, T)까지 올라가면 된다. 우선 입력값을 y값을 기준으로 배열을 만들어서 입력해줬다. rock = new ArrayList[200001]; // T의 최대값: 2,000,000 for (int i=0; i

ServletContextListener 웹 애플리케이션의 컨텍스트의 생명주기 이벤트를 처리하기 위한 인터페이스로 웹 애플리케이션이 시작과 종료 시점에서 특정 클래스의 메서드를 실행할 수 있는 기능을 제공한다. ServletContextListener 생성 방법 어떠한 방법을 사용해도 기본적으로 해당 클래스에 ServletContextListener 를 구현해야 한다. 1. web.xml 이용하는 방법 [MyServletContextListener.java] import javax.servlet.ServletContextEvent; import javax.servlet.ServletContetxtListener; public class MyServletContextListener implements Se..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🔶 풀이 불특정한 도시 A에서 출발해서 한 바퀴를 돌고 도시 A로 다시 돌아왔을 때 최소 비용을 구하는 문제. 시간 제한이 적기 때문에 dp와 비트마스크를 활용해야함. 비트마스크(Bit Mask) 알고리즘 장점 및 연산자 사용 방법 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법 ✅ 이진..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🔶 풀이 오랜만에 나온 다익스트라 문제. 완전 탐색으로 풀려고 했지만 시간 초과가 발생할 것 같아서 다른 방향을 생각해 봄. bfs와 다익스트라 알고리즘을 헷갈려하시는 분들이 있는 것 같은데 큰 차이점은 그래프의 가중치 유무와 dp 활용이다. 두 가지 알고리즘 모두 최단 거리를 찾는 알고리즘이지만 그래프의 가중치가 생기면 다익스트라 알고리즘을 사용하는 것이 좋다. 또한, 그래프의..

이클립스 실행 시에 아래와 같은 에러가 발생할 수 있다. The default workspace '지정한 경로' is in use or cannot be create, please choose a different one. 해결하는 방법은 총 두 가지가 있다. 에러 해결 방법 1. 작업관리자에서 eclipse.exe 프로세스 종료 2. 지정한 workspace의 .metadata 폴더에 .lock 파일 삭제

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 🔶 풀이 그리드 알고리즘으로 충분히 해결할 수 있는 문제. 1번부터 N번까지의 책을 가지고 있고, a부터 b까지 중 하나의 책을 최대한 많은 학생에게 나눠주면 된다. 중복된 책을 나눠주면 안되기 때문에 book 배열로 나눠줌 여부를 판단해줬다. 문제를 잘 살펴보면 한 가지 예외가 있다. 1 5 4 1 5 // 1번 책을 나눔 2 5 // 2번 책을 나눔 3 4 // 3번 책을 나눔 3 3 위의 예제를..

자바에서는 선언 위치에 따라서 크게 지역 변수와 전역 변수 2개로 나눌 수 있다. 전역 변수에는 클래스 변수와 인스턴스 변수가 있다. 1. 지역 변수 (Local Variable) public class Main { public static void main(String[] args) { int localVar = 10; System.out.println(localVar); // 10 } } 메서드 내에서 선언된 변수로 해당 메서드 내에서만 사용이 가능하다. 메서드 호출이 끝나면 소멸되고, 초기화하지 않으면 컴파일 에러가 발생한다. 2. 전역 변수 전역 변수에는 클래스 변수와 인스턴스 변수가 존재한다. [인스턴스 변수] public class Main { public int globalVal; publi..

https://www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 🔶 풀이 각 줄에서 맨 앞에 있는 사람끼리 비교해야하는 문제. 1. M개의 줄로 나눠서 WaitLine 배열리스트에 사원들을 입력해준다. ArrayList[] waitLine = new ArrayList[M]; for (int i=0; i

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔶 풀이 유니온-파인드 문제. 1 → 3 으로 가려고할 때, 바로 연결되어있지 않아도 1 → 2 → 3 이 연결되어있다면 갈 수 있다. 즉, 가고자하는 경로가 쭉 이어져있으면 여행이 가능하다는 뜻이다. 유니온-파인드에 대해서 처음 접하신 분들은 아래 링크를 보고 오는 것을 추천한다. 유니온-파인드를 이용한 대표적인 알고리즘을 설명하고있다. 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Krus..