본문 바로가기

Algorithm94

[알고리즘 문제풀이] 백준 1938 통나무 옮기기 (JAVA코드) https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net /** * bfs 구현 * * 1. 50*50 크기 * * 2. bfs를 나무의 중심으로 방문여부 체크하여 진행 * 2-1) bfs엔 나무의 중심과 가로 세로 여부 확인. * * 3. 각 조건별로 모듈화해서 진행 예정 * * 4. 최종 목적지 도착 최소 동작 회수 출력 * */ import java.util.*; import java.io.*; public class Mai.. 2022. 4. 27.
[알고리즘 문제풀이] 백준 1726 로봇 (JAVA코드) https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net /** * 1. 100*100 맵 크기. * * 2. 로봇의 위치와 방향, 도착위치와 도착방향이 주어짐. * * 3. 몇번의 명령만에 도착할 수 있는지 체크하여 반환. * * --------------------------------------------- * * 1. bfs로 행할 수 있는 모든 명령 실행.(총 5개) * * 2. 해당좌표에 해당방향으로 방문했었는지 체크. * * 3. 방문안했었고 이동 가.. 2022. 4. 8.
[알고리즘 문제풀이] 프로그래머스 - 단어 변환 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr /** 1. queue를 사용하여 변경가능한 단어 변경 2. 해당 단어를 썻는지 안썻는지 체크 3. 변경할때 변경회수 증가 4. target과 동일 시에 변경횟수 반환 **/ import java.util.*; class Solution { public class Word{ String word; int cnt; pub.. 2022. 4. 7.
[알고리즘 문제풀이] 백준 15686 치킨 배달 (JAVA코드) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net /** * 1. 50*50 맵 크기. 최대 13개의 치킨집 고를 수 있음 * * 2. m개의 치킨집 선택. * 2-1) 50*50 에서 m개를 고를려면 시간복잡도 문제가 됨.. * 2-2) 맵에서 치킨집리스트를 별도로 빼고, 그 안에서 선택!(최대 13개 있다고 함.) * 2-3) 13개중에서 m개 선택 시간복잡도. 13Cm * * 3. 선택한 치킨집에서 집리스트를 돌면서 거.. 2022. 4. 6.
[알고리즘 문제풀이] 프로그래머스 - n^2 배열 자르기 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/87390 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr /** 1. 구현.. 2. i행 i열까지 모든 숫자를 i로 채운다는 것은 행과 열중에 높은 숫자가 들어간다는 것. 즉 2,3 이면 더 높은 숫자인 3으로 채워져 있고, 5,3 이면 더 높은 숫자인 5로 들어가져 있음. 1 2 3 2 2 3 3 3 3 3. 2차원 배열을 모두 이어붙인 1차원 배열에서 le.. 2022. 4. 5.
[알고리즘 문제풀이] 백준 14500 테트로미노(JAVA코드) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net /** * 1. 맵 크기 500*500 * * 2. 4칸짜리 테트로미노를 둬서, 최대 정수 합의 크기 출력 * * 3. 각 칸마다 4칸을 갈 수 있는 모든 경우의 수 구해보기? * 500*500 * 4*4*4*4 가능.. * * 4. 2중 포문으로 각 칸을 넣고, dfs를 통해 4칸 가보기로 코드 진행 * * 5. 들렸던 칸은 방문하지 않아야하므로 체크할 visited 필요 * * 6. 0 0 0.. 2022. 4. 5.
[알고리즘 문제풀이] 백준 2293 동전 1(JAVA코드) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net /** * 1. n개의 동전 종류를 이용해 k원 맞추기 * * 2. 모든 경우의 수 출력 * * 3. 완탐은 불가능하므로 DP 사용 * * 4. DP[가치] = 경우의 수 * * 5. 2중 포문으로 동전과 가치를 돌려, * 각 동전마다 가치에 나올 수 있는 경우의수를 구하고 * 더해가며 진행 * * 6. 가치 다음에 동전을 돌리면 중복이 존재함.. */ import java.util.*; impor.. 2022. 4. 4.
[알고리즘 문제풀이] 프로그래머스 - 가장 큰 정사각형 찾기 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr /** 1. 1000*1000에서 가장 큰 정사각형 찾기 2. 완탐은 불가..(10^3*10^3*10^3) 3. dp..? 4. dp로 사각형 모양(현재위치,위,좌측,대각선) 전부 존재할때 가장 적은 값 +1로 설정 5. dp[세로][가로] = 길이 1000*1000으로 해결! 10^6 **/ class Solution { public int solution(int [][]board) { int result = 0; for(int i = 0; i < b.. 2022. 4. 3.

티스토리툴바