코딩테스트/BOJ

문제 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 풀이 1. 그룹에 따라 리스트에 입력 받음 (1). 본인보다 키가 큰 여성을 원하는 남자 리스트 (man_wanna_taller) (2). 본인보다 키가 작은 여성을 원하는 남자 리스트 (man_wanna_smaller) (3). 본인보다 키가 큰 남성을 원하는 여자 리스트 (woman_wanna_taller) (4). 본인보다 키가 작은 남성을 원하는 여자 리스트 (woman_wanna..

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 1. 7명의 조합을 만든 뒤 2. 연결되게 앉았는지 체크 1. 7명의 조합 - dfs로 구현 public static void comb(int depth, int cnt) { if(cnt==7) { if(bfs()) answer++; return; } for(int i=depth; i

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 이 문제는 깊게 생각을 안 했다. 문제에 있는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열을 보자마자 arr[i] = arr[i-2] + arr[i-3] 의 점화식을 떠올렸다. 이를 dp배열을 생성하여 그대로 구현 (주의) dp배열을 int형으로 선언 시 계산값이 오버플로우가 발생할 수 있음 long타입으로 선언할 것. package dp; import java.io.BufferedR..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리 구조를 입력 받기 위해 ArrayList의 배열을 사용하였다. tree = new ArrayList[N]; 처음부터 입력을 다 받아 놓고, 노드들의 부모 정보를 저장 받을 때, 애초에 삭제할 노드와 삭제할 노드의 자식 노드의 정보를 저장하지 않았음. for(int i=0; i

https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. ..

문제 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 ..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 풀이 ArrayList의 특성을 이용하여 풀면 쉬운 문제. package greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class BOJ_1138_한줄로서기 { public static..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 문제를 꼼꼼히 읽어야 겠다고 생각했던 부분.. 이걸 고려 하지 않아서 처음에 실패했다.. 풀이 1. 간단한 bfs 탐색 2. 목적지를 시작점으로 잡고 목적지부터 다른 노드들까지의 거..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 1. ArrayList 배열을 만들어 graph 입력을 받는다 (양방향) graph = new ArrayList[V + 1]; for (int i = 0; i 같은 색이면 이분 그래프가 아니므로 flag를 false로 바꿔준다. (2) 방문한 노드가 아니었다면, 그 노드의 색깔을 현재 노드와 반대되는 색으로 정해준다. (방문체크와 비슷) 4. 노드들의 집합마다 이분 그래프인지 확인해야 하므로..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 좌표 때문에 고민이 많았지만.. 그냥 고민하지 않고 풀면 되는 문제 1. (0,2) ~ (4, 4)라면 i의 반복문은 for(int i=0; i 0) { st = new StringTokenizer(br.readLine()); int si = Integer.parseInt(st.nextToken()); int sj = Integer.parseInt(st.nextToken(..