본문 바로가기

Algorithm/BOJ

 (95)
[BOJ] 14503. 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - while문을 사용해서 특정 조건이 끝날 떄, 루프를 해제 - while문 안에 for문을 사용해서 동서남북을 체크 - for문으로 체크가 안되거나 완료 시, 보는 방향을 그대로 하고 뒤로 후진 2. 시간복잡도 - O(NM) : 50^2 3. 자료구조 - 2차원 배열 : graph[][] - 청소가 안된 빈 칸 : 0, 벽 : 1, 청소가 완료된 칸 : 2..
[BOJ] 10819. 차이를 최대로 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 배열안 2개의 원소 값 차이의 합 중 최대 값을 구하는 문제. - 하나의 원소를 먼저 선택하고, n-1개 중 추가적으로 계속 뽑는 형식. - n-1, n-2 ... 재귀적으로 들어가면서 차이 값을 구한다. 2. 시간복잡도 - O(2^n) 3. 자료구조 - 백트래킹 : 재귀 """ 2. 정답코드 입력 예제(1) 6 20 1 15 8 4 10 출력 예제(1) 62 코드 imp..
[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. 시간복잡도 - ..

티스토리툴바