Coding Test (40) 썸네일형 리스트형 백준 댄스 파티(2831) 오늘은 투포인트 문제를 풀어보았다. https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 위에 조건을 따지고 보면 두가지 조건의 그룹이 생긴다. 큰 남자를 좋아하는 여자 & 작은 여자를 좋아하는 남자 큰 여자를 좋아하는 남자 & 작은 남자를 좋아하는 여자 이렇게 두그룹으로 구분한뒤 큰 사람, 작은사람 비교하는 알고리즘을 만들면 된다. import java.io.BufferedReader; import java.io.IOException; impo.. 백준 암호만들기(1759) bruteforcing 문제를 풀어보았다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 풀이 문자의 정렬 순서는 a-z배열을 기준으로 인덱스를 비교하여 정렬을 보장했다. 자음 모음 확인은 마지막으로 만들어진 문자를 기준으로 확인했다. 출력시 정렬 하는방식은 우선순위 큐를 이용했다. 코드 package bruteforcing; import java.io.BufferedReader; import java.io.IOException; import.. 백준 색칠하기(13265) 오늘 DFS 문제를 풀어보았다. https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 문제 풀이 각 노드를 서로 다른색으로 색칠을 해준다. 각 노드와 연결된 노드가 색이 다른지 확인 해준다. 두가지 기준으로 풀이를 해주면 된다. ※ 노드는 모두 연결되어 있지 않을 수도있다. 해당 부분을 생각하지 못하여 문제를 틀렸어서 시간을 소비했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.. 백준 김바천국의 계단(28069) 오늘은 DP문제를 풀어보았다. https://www.acmicpc.net/problem/28069 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 해당 문제를 N * K 번 수행을 하게되면 메모리 초과 혹은 시간 초과가 발생된다. 해당 문제를 풀기 위해서 DP를 이용했다. 키 포인트 현재 계단이 밝을 수 있는 계단인가? 현재 계단은 몇번째 행위로 밝을 수 있는 계단 인가? 위 두가지 사항을 누적해가며 김밥 가게 위치에 최소 행동 값을 DP하면 된다. import java.io.BufferedReader; import java.io.IOException;.. 백준 준규와 사과(5913) 오늘은 백트래킹 문제를 풀었다. https://www.acmicpc.net/problem/5913 5913번: 준규와 사과 대학교를 졸업한 준규는 농부의 꿈을 이루기 위해서 가로 5m, 세로 5m 크기의 땅을 구입했다. 준규는 땅을 가로 1m, 세로 1m 크기로 구역을 나누었다. 가장 왼쪽 위 칸은 (1,1)이고 가장 오른쪽 아래 www.acmicpc.net 장애물을 제외하고 모든 경우를 진행해야하는 케이스이다 문제 조건중에서는 두 명의 포인트가 동등하게 움직여서 모든 경우를 채워야하는 조건이 붙어있다. 장애물을 제외하고 모든 경우를 지나가야한다 두 포인트가 동등하게 움직여 모이는 포인트를잡아야한다 필자의 풀이는 k는 짝수로 각 포인트가 움직여야하는 거리를 계산 0,0 포인트에서 해당 거리를 움직인 이후.. 백준 십자뒤집기(10472) bruteforcing 문제를 풀어보았다. https://www.acmicpc.net/problem/10472 10472번: 십자뒤집기 당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색 www.acmicpc.net 인접한 블록들을 내가 클릭했을 때 변경되는 문제이다. 해당 수를 클릭하였을때 인접한 블록들의 상태를 변경해준다. 클릭하지 않고 지나간다. 두 가지 방식으로 총 9개의 블록을 지나갔을때 블록이 전부가 하얀색이 되는지 확인하면 된다. import java.io.BufferedReader; import java.io.IOException; import jav.. 백준 회장뽑기(2660) 최단거리 문제를 풀었다 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제를 해독력이 생각보다 필요한 문제였다. 친구의 친구 .. 의 의미는 결국 현재 노드로부터 최단거리로 가장 멀리느있는 노드 결국 시작 위치 노드에서 가장 멀리 있는 노드의 거리가 가장 작은것을 조회하면 되는 문제였다. 조금 구현에 가까운 문제였다 import java.io.BufferedReader; import java.io.IOException; import java... 백준 좋다(1253) 이분 탐색 문제를 풀어보았다. https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 투포인터로 문제를 해결 할 수 있었다. 정렬된 수를 가지고 선택한 수를 투포인트 진행하며 가능여부를 체크하면된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.ut.. 백준 물통(2251) DFS 문제를 풀어보았다. https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 물통은 A B C개가 존재하며 물은 한통에서 다른 통으로 옮긴다라는 하나의 액션을 생각해보면 된다. 내가 현재 잡은 물통에 물이 있으면 나머지 통에 옮길수 있을만큼 옮기면 된다. 키 포인트 선택한 물통을 다른 물통으로 옮길 수 있는 만큼 옮기기 몰통들의 수량 케이스를 담아서 방문기록 유지하기 import java.io.BufferedReader; im.. 백준 결전의 금요일(25194) DP 문제를 풀었다. https://www.acmicpc.net/problem/25194 25194번: 결전의 금요일 곰곰이는 올해도 운동하기를 신년 목표로 삼았지만, 지금까지 헬스장을 한 번도 가지 않았다. 운동하라고 잔소리하는 당신에게, 곰곰이는 금요일에 정확히 일을 끝마치는 시점이 있다면 헬스 www.acmicpc.net 금요일은 작업일%7 이 나머지가 4인경우를 구하면 된다. 작업일들의 모든 경우의수를 구하게 처음 구했다 시간초과가 발생되었다. 생각 가능한 범주로는 작업일기준으로 월화수목금토일만 관리하면된다. 그렇게 발생된 케이스에서 게속 DP를 진행하면된다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inp.. 이전 1 2 3 4 다음
