본문 바로가기

알고리즘/BOJ

 (95)
[JAVA]BOJ(백준) - 단지번호붙이기 - 2667 - 문제 내용 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net - 문제 접근 방법 입력받은 값을 2차원배열에 넣어 하나씩 0인지 1인지를 확인하기 2차원배열의 방문배열을 만들어서 방문여부도 함께 확인하기 확인된 집으로부터 dfs로 상하좌우를 돌면서 집이 있는지 없는지 확인하기 집이 없다면 해당 dfs를 끝낸다. 집이 있다면 다음 dfs를 호출한다. 이렇게 문제를 접근하면서 필요한것들 -> 집세주는 변수, 단지수 알려주는 변수, 방문배열 까지는 생..
[JAVA]BOJ(백준) - 바이러스 - 2606 - 문제 내용 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - 문제 접근 방법 전에 풀었던 'DFS와 BFS' 문제를 이용하면 되는 문제이다. 바이러스에 감염된 시작 컴퓨터에서 부터 간선이 연결된 컴퓨터들만 연결되는 것이므로 시작 컴퓨터로부터 간선이 이어지지 않은 컴퓨터는 신경 쓸 필요가 없다고 생각한다. 어차피 재귀 과정에서 간선이 연결된 것들만 방문하면서 바이러스 감염여부를 판단하기 때문!! 따라서 풀이과정은 간단해진다! 아 그리고 DFS, ..
[JAVA]BOJ[백준] - DFS와 BFS - 1260 - 문제 내용 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 문제 접근 방법 단순히 DFS와 BFS를 구현해내면 되는 문제이다. DFS, BFS 구현은 많은 사람들이 구현해 놓은 방식이 있는데 간선의 경우 2차원배열을 이용해서 풀었다. 그리고 DFS와 BFS 문제에 접근하기 전에 백트래킹 알고리즘 문제에 먼저 익숙해지고 시작하는 편이 수월할 것 같다. - 풀이 입력값 및 배열 선언 public clas..
[JAVA] BOJ(백준) - N과 M(2) - 15650 - 문제 내용 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 참고로 처음에 나는 문제 이해를 중복제외한 모든 수열이 출력되고 출력된 수열을 오름차순 하는건줄 알고 예제 출력이 잘못됐나 생각했는데, 그게 아니라 수열 하나의 경우에 한해서 오름차순을 진행하는 것이였다ㅠㅠ,, 헷갈리지말자.. - 문제 접근 방법 기존에 풀었던 N과 M(1) 문제랑 매우 유사한 문제이다. 이 문제는 수열 하나를 만들때 오름차순을 고려해야 하므로 전의 값을 알고 있어..
[JAVA]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 - 문제 접근 방법 처음 생각했던 방법은 수열이 주어졌을때 어차피 수의 순서는 바꾸지 못하기때문에 순서대로만 찍어내서 계산하고 계산한 값을 담을 변수하나를 추가해주는 것이다. 그리고 값의 계산은 연산자만 바꿔가면서 모든 경우의수를 알아보는 것이므로 재귀함수의 for Loop의 범위는 연산자 배열을 만들어서 그 크기만큼 돌리면 M..
[JAVA]BOJ(백준) - N Queen - 9663 - 문제내용 - 문제 접근 방법 문제 자체는 N을 입력 받았을때 N*N 체스판에다 N개의 퀸을 서로 공격 못하는 위치에 올려 놓을수 있는 경우의 수를 구하면 되는 문제이다. 이 방법도 전에했던 N과 M(1) 문제처럼 백트래킹으로 풀면되는데 가장먼저 고려해야 했던것들이 있다. 퀸은 상,하,좌,우,대각선 방향으로 끝에서 끝까지 공격 범위이다. 상,하,좌,우에 대해선 퀸은 무조건 체스판에서 하나의 행이나 하나의 열에 한개밖에 못놓는다. 즉, 행과 열마다 겹치는 퀸이 있으면 안된다. 이부분이 가장 어려웠는데,, 체스판에서 대각선 방향도 겹치는 퀸이 있어선 안된다. 쓰고보니 결국 다 같은 말같은데 음,., 저 조건을 고려해야 필요없는 경우의 수를 줄일수 있다. 처음엔 체스판을 2차원 배열로 만들어서 하나하나의 경..
[JAVA] BOJ(백준) - N과 M(1) - 15649 - 문제내용 - 문제 접근 방법(내 생각) 첫번째 접근 방법(시간 초과남) 자연수 1~N까지의 숫자로 만들수 있는 모든 경우의 수를 고려해 수의 조합을 만든다. 수를 조합하기 위해 1~N까지 자연수를 받는 String[] kindN 배열을 초기화 해준다. kindN 배열의 길이만큼 재귀를 통해 for문을 반복적으로 돌면서 요소 하나하나를 String temp 에 붙여준다. 해당 요소에 볼일이 끝나면 temp의 맨뒤의 문자를 빼준다. 재귀의 종료조건은 temp의 길이가 M과 같을때로 설정한다. - 내코드(시간 초과) import java.util.*; public class BOJ_15649 { static ArrayList list = new ArrayList(); public void seqence(S..

티스토리툴바