본문 바로가기

Algorithm29

20230627 [Java] 문제풀이 20230627 [Java] 문제풀이 [프로그래머스] 안전지대 행렬이 주어진다 1은 지뢰가 있는 곳 그리고 0은 지뢰가 없는 곳이다 지뢰 기준으로 8방면 (위, 아래, 좌, 우, 대각선) 모두 위험 지역이다 위험 지역이 아닌 곳의 개수를 찾으면 된다 1) 델타 탐색 (dr, dc) 를 통해 1을 발견하면 8방면을 2로 만들어 준다 2) 그렇게 위험 지역을 1과 2로 표시하고, 다시 2중 for문을 통해 안전 지역인 0을 세준다 class Solution { public int solution(int[][] board) { int answer = 0; int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1}; int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1}; for (in.. 2023. 6. 27.
[Java] 문제풀이 (Programmers) Java 문제풀이 (Programmers) 분수의 덧셈 (numer1 / denom1) + (numer2 / denom2) 의 값을 구해, 분자는 answer[0]에, 분모는 answer[1]에 저장하는 것이다 먼저 answer[0]와 answer[1]에 나누지 않은 채로, 그냥 더해서 저장을 한다 그리고 2부터 시작해서 for문을 돌면서 answer[0]과 answer[1]를 나눌 수 있으면, 계속 나눠준다 최대공약수를 나누는 방법과 똑같은 것이다 (대신 최대공약수를 따로 구하는 것이 아니라, 최대공약수를 구하는 식을 for문과 while문을 통해서 구하는 것이다) class Solution { public int[] solution(int numer1, int denom1, int numer2, in.. 2023. 5. 26.
[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.
[Python] 백준 1018 체스판 다시 칠하기 🧑‍💻 [Python] 백준 1018 체스판 다시 칠하기 Silver 4 - 완전 탐색 코드 N, M = map(int, input().split()) board = [list(input()) for _ in range(N)] def chess(i, j): global result change_1,change_2 = 0, 0 for row in range(8): for column in range(8): if (row + column) % 2 == 0 and board[i + row][j + column] == "B": change_1 += 1 elif (row + column) % 2 == 1 and board[i + row][j + column] == "W": change_1 += 1 if (row .. 2023. 3. 24.
Udemy : 동적 계획법 (DP) Udemy : 동적 계획법 (DP) udemy 알고리즘 코딩 테스트 Dynamic Programming 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복 분할정복과 비슷한 느낌 배열 또는 딕셔너리를 만들어서, 작은 문제의 답을 넣는다 메모이제이션 (Memoization) 구현 : 재귀 | 저장방식 : 메모이제이션 (Top-down) cache 방식이라고 할 수 있고, 중복연산을 방지한다 직관적이라 코드 가독성이 좋다 재귀함수 호출이 많이 해서 느릴 수 있다 타뷸레이션 (Tabulation) 구현 : 반복 | 저장방식 : 타뷸레이션 (Bottom-up) 테이블을 채워나가는 것 필요 없는 부분 문제까지 전부 구하는 것 시간과 메모리를 좀 더 아낄 수 있다 DP 테이블 채워.. 2023. 3. 23.
[Python] 백준 14502 연구소 🧑‍💻 [Python] 백준 14502 연구소 Gold 4 - 구현 from copy import deepcopy 깊은 복사를 하는 것이다 깊은 복사를 하면, 완전 다른 인스턴스가 만들어진다 (남남이 되는 것) combinations 을 사용해서 배치할 벽들의 좌표를 구했다 empty_space 리스트에 비어 있는 공간들의 좌표들을 넣었다 비어있는 공간들의 좌표의 순열을 통해 벽들을 배치하고, 바이러스가 얼마나 퍼지는지 구하는 것 for empty in combinations(empty_space, 3): 비어있는 공간들의 좌표 3개를 통해 벽들을 배치해준다 BFS를 하는데, BFS는 마지막에 퍼진 바이러스의 개수를 반환해준다 퍼진 바이러스의 개수의 최소값을 구하면 된다 코드 디테일 queue = deq.. 2023. 3. 14.
[Python] 백준 1913 달팽이 🧑‍💻 [Python] 백준 1913 달팽이 Silver 3 - 구현 무조건 matrix[0][0]은 N * N 이다 시작을 N * N으로 하고, 내려가면서 -1 을 한다 만약에 다음 좌표가 0이 아니거나, 행렬을 나가게 된다면 왼쪽으로 90도를 돌아서 앞으로 가면서 -1을 하면 된다 이것을 좌표의 값이 1이 될때까지 진행을 한다 코드 N = int(input()) M = int(input()) matrix = [[0] * N for _ in range(N)] num, i, j = N * N, 0, 0 ans_row, ans_column = 0, 0 while num > 0: # 아래로 내려가기 while i < N and matrix[i][j] == 0: if num == M: ans_row, ans_.. 2023. 3. 4.
[Python] 백준 13397 구간 나누기 2 🧑‍💻 [Python] 백준 13397 구간 나누기 2 Gold 4 - 이진 탐색 구간의 점수의 최댓값의 최솟값을 기준으로 mid를 구하는 것이다 즉 주어진 배열에서 순회하면서 구간의 최댓값과 최솟값을 구해서 mid보다 작거나 같으면 계속 탐색을 한다 그게 아니면 새로운 구간을 만들어서, 새로운 최댓값과 최솟값을 구해준다 코드 N, M = map(int, input().split()) array = list(map(int, input().split())) def groups(mid): min_num, max_num = array[0], array[0] count = 1 for i in range(N): min_num = min(min_num, array[i]) max_num = max(max_num, a.. 2023. 3. 1.

티스토리툴바