반응형 백준알고리즘68 [백준] 9663번 - N-Queen (Java) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표 문제이다. 퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다. * 두가지 문제 1. 재귀호출을 어떤 방식으로 할 것인가 2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가 * 체스판의 퀸을 일차.. 2022. 10. 13. [백준] 15651번 - N과 M(3) (Java) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복숫자와 순열 모두 허용이다. N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다. 다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다. 대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다. import java.util.Scanner; //[백준] 15651번 - N과 M(3) (Java).. 2022. 10. 13. [백준] 15650번 - N과 M(2) (Java) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다. 이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다. 예제를 보면, 4 2 ---- 1 2 1 3 1 4 2 3 2 4 3 4 이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다. (1)에서는 재귀 호출에서 돌아오면 중복체크.. 2022. 10. 13. [백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13. [백준] 14713번 - 앵무새 (Java) N마리의 앵무새가 한 문장씩 이야기 한다. 다른 앵무새가 문장을 이야기 하는 중간에 다른 앵무새가 치고 들어올 수 있다. 예제 문장이 조합이 가능하면 possible, 불가능하면 Impossible을 출력한다. 큐를 배열로 N개만큼 만들어서 앵무새의 문장을 단어로 잘라서 저장한다. 테스트 문장은 배열, 리스트 혹은 큐로 저장하자. 테스트 문장을 루프를 돌리면서 첫 단어를 앵무새 문장의 첫 단어에 있는지 루프를 돌리며 탐색하자. 있으면 그 단어는 삭제하고 다음으로 넘어가자. 없으면 바로 Impossible 출력한다. 테스트 문장 끝까지 무사히 탐색했으면 Possible을 출력한다. 받아적은 문장의 단어의 수와 N개의 앵무새가 말한 단어의 수가 같아야 한다. 받아적은 문장의 단어검색이 끝났는데 앵무새의 단어.. 2022. 10. 12. [백준] 2304번 - 창고 다각형 (Java) https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. N개의 막대기둥이 늘어서있다. 폭은 모두 1m이다. 2. 막대기둥을 다 덮을 지붕을 만들어야 한다. - 지붕은 각 기둥의 윗면과 닿아야 한다. - 지붕은 어떤 기둥의 옆면과 닿아야 한다. 1. class point { int x, int y } 선언한다. 2. 배열로 입력받은 기둥을 삽입한다. 3. stack으로 비교 함수를 만든다. - 첫 기둥을 스택에 넣는다. - stac.. 2022. 10. 11. [백준] 1931번 - 회의실 배정 (Java)(○) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [첫번째] N개의 회의가 주어지고, 각 회의마다 시작시간과 끝나는 시간이 주어진다. 각 회의가 겹치지 않게 하면서 최대한 많이 회의를 사용할 수 있는 개수를 구하라. 회의의 시작시간과 끝나는 시간이 같을 수 있다. 그리디 알고리즘으로 접근하자. class를 선언해서 시작시간과 끝나는 시간을 저장하자. 이 클래스 배열을 끝나는 시간 기준으로 오름차순 정렬을 하자. 루프를 돌리면서 지금 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교하자. 다음 회의의 시작 시간이 같거나 더 크면 회의 갯수를 누적합 시킨다. 선택.. 2022. 10. 11. [백준] 1926번 - 그림 (Java) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net map : 1과 0으로 구성. 그림 : 상하좌우가 1로 연결된 것 그림의 갯수와 가장 큰 그림의 넓이를 출력한다. 그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다. 입력정보 세로축 N : 2022. 10. 10. [백준] 14496번 - 그대, 그머가 되어 (Java) https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 문자열 a를 b로 바꾸는 최소 치환 횟수를 구하는 문제이다. 문자열 관련 문제처럼 보이나 실상은 문자열 a에서 b로 가는 최단경로를 구하는 문제이다. 우선순위 큐와 다익스트라 알고리즘을 사용해서 풀면된다. 인접리스트 방식 둘로 나눠서 풀어보자. 1. class Node를 구성하자. cost로 오름차순으로 PQ를 구성한다. 2. 방문배열(boolean v.. 2022. 10. 8. 이전 1 2 3 4 5 6 7 8 다음 반응형
