https://www.acmicpc.net/problem/4672풀이체스판이 주어졌을 때 놓을 수 있는 최대 룩 개수를 구하는 문제다. 체스판은 빈 칸은 '.', 벽은 'X'로 되어있다. 룩은 벽을 통과하여 이동할 수 없다. n-Queen 문제와 비슷하게 백트래킹을 사용하여 풀었다. 로직1. 체스판을 입력하면서 빈 칸의 수를 카운트한다. 빈 칸의 수는 답(최대 룩 개수)이 될 수 있는 최댓값이기 때문에, 추후 탐색할 때 이미 해당 값을 구한다면 탐색을 더 이상 하지 않는다.2. rook(0, 0, 0)을 호출한다. rook(int r, int c, int count)(r,c) 좌표에 룩을 놓을 수 있는지 검사한 후 놓을 수 있다면 rook(r, c+1, count+1)을 호출한다.해당 칸을 스킵하는 경우..

https://www.acmicpc.net/problem/2206풀이BFS를 사용하여 최단 경로를 구하는 문제다. 이동하는 도중에 최대 1개까지 벽을 부수고 이동할 수 있기 때문에, 처음 풀 때는 모든 벽에 대해서 1개씩 부서졌을 때 BFS를 수행했다. 하지만 시간초과가 났다. 다른 사람의 풀이를 찾아본 결과 visited 배열을 3차원으로 선언하여 벽을 부쉈을 때와 부수지 않았을 때를 따로 처리하였다.boolean[][][] visited = new boolean[n][m][2]; // [r][c][0] = 벽을 부수지 않고 이동한 경우 , [r][c][1] = 벽을 부수고 이동한 경우 BFS 수행 과정1. (0, 0) 좌표에서 시작한다. 시작하는 칸도 포함해서 카운트하기 때문에 dist는 1, des..

https://www.acmicpc.net/problem/9663문제대표적인 백트래킹 문제다.완전탐색/DFS와 비슷하지만, '정답이 될 수 없다면 다시 돌아오는 과정' = 가지치기를 한다.즉, 불필요한 경로는 끝까지 탐색하지 않는다. 백트래킹의 개념과 문제 모음 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n; static boolean[][] board; static int count = 0; public static void main(String[] args) throws ..

https://www.acmicpc.net/problem/7576풀이대표적인 BFS 문제다.토마토 상태를 입력받을 때 익지 않은 토마토의 개수를 미리 카운트하고, BFS를 하며 익은 토마토의 개수를 카운트한다.BFS가 종료된 후 익지 않은 토마토가 있다면 -1을 출력하고, 모두 익었다면 모두 익을 때까지의 걸린 시간을 출력한다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n, m; static int[][] map; static int[] dr = {0, 1, 0, -1}; s..

https://softeer.ai/practice/6287 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai풀이처음에는 BFS를 통해 가장 빠른 조립시간을 구하려 했다. 하지만 BFS로 수행할 시 메모리 초과가 발생했다.풀이방법에 대해 더 생각해보았더니 DP를 사용하여 해당 작업장까지의 최소 조립시간을 구하는 방식으로 풀었다.// 0 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

https://softeer.ai/practice/6294 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai풀이누적합 배열을 사용하여 풀이하였다.코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLi..

https://www.acmicpc.net/problem/4920 4920번: 테트리스 게임 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓 www.acmicpc.net 풀이 5가지 조각으로 배치할 수 있는 모든 도형의 경우의 수(총 13가지)를 배열로 지정하여 풀었다. 주의할 점 - n을 입력받을 때와 NxN 표를 입력받을 때 trim()을 해주어야 한다. - 표에 쓰이는 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다. 즉, 음수가 입력될 수 있으므로 초기 max값을 Integer.MIN_VALUE로 초기화한다. 코드 import java.i..

https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 풀이 처음 문제를 봤을 때는 BFS 알고리즘을 생각했다. 같은 위치를 다시 방문하면 안되기 때문에 boolean[] visited 방문 배열을 사용해야겠다고 생각했다. 하지만 단순한 방문배열이 아닌, 현재 탐색 단계와 이전 탐색 단계를 구분하는 방문 배열이 필요하다. ex) EEW W EW - 인덱스가 3인 W부터 시작해서 탐색할 때 왼쪽의 EEW와 합쳐진다. 따라서 카운트하지 않는다..

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 5 ≤ sequence의 길이 ≤ 1,000,000 = 10^6 이기 때문에 O(n) 알고리즘을 사용해야 한다. 따라서 투포인터 알고리즘을 사용하여 문제를 풀었다. 코드 class Solution { public int[] solution(int[] sequence, int k) { int sum = sequence[0]; int i = 0, j = 0; // 답이 [0, 0]인 경우 if..

https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이처음에는 BFS로 풀었다가 틀린 결괏값이 나와서 의아했는데, 입력값과 출력값을 보니 각 자리 숫자로만 답을 구할 수 있는 것 같아서 로직을 바꿨다.storey % 10으로 한 자리씩 처리하는 로직을 작성하였고, 각 자리 숫자가 5보다 큰 경우, 작은 경우, 같은 경우를 나누어서 처리하도록 하였다. 같은 경우(숫자가 5인 경우)에는 앞 자리 숫자가 5보다 크거나 같은 경우, 작은 경우로 나누어서 처..

https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 누적값이 최소가 되게 하는 경우를 찾기 위해 다음의 예시를 들어보았다. A: [x, x+1] B: [y, y+1] 1. x*(y+1) + (x+1)*y = xy + x + xy + y = 2xy + x + y 2. xy + (x+1)*(y+1) = xy + xy + x + y + 1 = 2xy + x + y + 1 A: [x, x+k] B: [y, y+m] 1. x*(y+m) + (x+k)*..

https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다. 또한 이미 탐색했던 상태가 나올 수 있으므로, Map map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다. 동전 상태는 다음과 같이 문자열로 저장된다. H T T H T T T H H -> HTTHTTTHH BFS 로직 1. 초기 동전상태를 큐와 Map에 추가한다..