본문 바로가기

Algorithm

 (175)
[BOJ] 7576. 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력받은 그래프에서 토마토가 있는 지점부터 for문을 돌려 BFS 처리는 할 것이다. - 방문기록 체크하면서 돔. - 방문기록이 False 경우와 방문하고자 하는 인덱스 값이 0인 경우에만 방문해서 인덱스 값을 +1로 하고 방문기록을 True로 한다. - bfs를 완료하고 열 인덱스에 값이 0이 존재하는 경우, -1을 print 2. 시간복잡..
[BOJ] 1759. 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 최소 1개 이상의 모음(a e i o u)과 최소 2개 이상의 자음으로 구성되어 있고, 오름차순으로 정렬을 한다. - if문으로 먼저 1개 이상의 모음을 구하고, 그 다음은 자음 2개 이상을 조건화 한다. - 원소 중복이 일어나면 안되기 때문에 방문기록을 체크할 것이다. 2. 시간복잡도 3. 자료구조 - 백트래킹 : 재귀 """ 2. 정답코드 입력 예제(1) 4 ..
[BOJ] 9663. N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 체스판 위의 퀸은 같은 열과 행에 두개의 퀸이 존재할 수 없고, 왼쪽 및 오른쪽 대각선에 다른 퀸이 존재하는 경우가 되면 안된다. - 2차원 배열을 이용할 경우, 퀸을 놓은 자리를 기준으로 열과 행, 대각선의 값을 1로 처리하고 방문기록도 체크한다. -> 2차원 배열을 사용하면 시간복잡도가 엄청나게 커짐. - 열을 기준으로 한 리스트를 만들고 리스트 열 값에 퀸이 위치한 행..
[BOJ] 1012. 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - BFS를 돌면서 배추가 심어진, 즉 그래프 상에서 1로 연결된 지점을 돌면서 끝나면 +1을 해준다. - 방문기록을 체크하면서 이중 for문을 돈다. 2. 시간복잡도 - O(V + E) 3. 자료구조 - BFS - 2중 for문 """ 2. 정답코드 입력 예제(1) 2 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 ..
[BOJ] 1182. 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력받은 정수 S가 되기 위해 모든 경우의 수를 구함. - 원소 하나씩 추가시키는 재귀랑 추가시키지 않는 재귀 두개를 구현해서 모든 경우의 수를 확인. - 결과 리스트에 들어간 원소 값의 합들이 S가 되면 종료, print 2. 시간복잡도 - O(2^N) 3. 자료구조 - 백트래킹 : 재귀 """ 2. 정답코드 입력 예제(..
[BOJ] 14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 각 팀을 n // 2로 나누어서 처리한다. - 2중 for문을 사용해서 선수를 추출한다. 방문기록 체크 - 먼저 Start Team을 n // 2만큼 append하고, 재귀 종료 지점으로 이동한다. - Start Team에 append된 팀을 제외한 나머지 팀을 Link Team에 append 한다. - 각 팀의 시너지 합을 구하고 최소값이 되도록 비교한다. 2. 시간복잡도 - ..
[BOJ] 14888. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력 받은 연산자를 리스트로 넣고 각 연산자의 수 만큼 재귀 - 재귀에서 n개를 선택 후 연산 결과가 크커나 작으면 변수 값 변경 한 다음 종료, print - 백트래킹 for문을 돌면서 입력 숫자 원소와 연산자를 순차적으로 선책해서 모든 경우의 수를 연산 2. 시간복잡도 - O(N) 3. 자료구조 - ..
[BOJ] 15663. N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력 리스트를 오름차순으로 리스트에 저장 - 백트래킹 for문 돌면서 해당 원소를 append - 원소의 중복되는 수열 때문에, 이전 인덱스를 기억하고 선택하면 패스하도록 함 - 재귀에서 m개를 선택하면 종료, print 2. 시간복잡도 - N^N (N = 7) : 가능 3. 자료구조 - 배열 : 입력 int[] - 백트래킹 : 재귀 """ 2. 정답코드 ..

티스토리툴바