sarang넘치는 코딩 공작소
close
프로필 배경
프로필 로고

sarang넘치는 코딩 공작소

  • 분류 전체보기 (106) N
    • Java (15)
    • SpringBoot (0)
    • 코딩테스트 (57) N
      • 개념정리 (7)
      • 문제풀이 (50) N
    • 자격증 (16) N
      • 정보처리기사 (12)
      • AWS Solution Architecture (4) N
    • JavaScript (1)
    • Vue.js (8)
    • 프로젝트 (1)
    • RabbitMQ (1)
    • Network (5) N
    • Database (2)
  • 홈
  • 태그
  • 방명록

[ 알고리즘 ] Dijkstra Algorithm

시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘⚠️ 음의 가중치를 가지지 않는 그래프에서만 동작(음의 가중치 → Bellman-Ford Algorithm)🔎 핵심그래프 : edge에는 weight(가중치) 존재최단 경로탐욕 알고리즘 기반 : 현재 가장 비용이 적은 경로를 우선적 탐색🔎 Flow초기화시작 노드의 최단 거리 = 0나머지 모든 노드의 거리 = ∞방문하지 않은 노드 배열(or 우선순위 큐 생성)방문 처리최단 거리 업데이트 필요 없는 노드는 방문 완료로 처리방문하지 않은 노드 중 최단 거리가 가장 작은 노드를 선택해 탐색최단 거리 업데이트현재 노드에서 연결된 인접 노드들의 최단 거리 계산 → 기존의 최단 거리보다 작다면 갱신모든 노드를 방문할 때까지 반복🔎 배열import ja..

  • format_list_bulleted 코딩테스트/개념정리
  • · 2025. 1. 8.
  • textsms

[ 프로그래머스 ] #12905 : 가장 큰 정사각형 찾기 - JAVA

🔗 가장 큰 정사각형 찾기 dp는 해당 위치에서 확장가능한 정사각형의 한 변의 길이를 저장첫 행, 첫 열은 board 배열과 동일하게 함dp[i][j] 을 기준으로 위쪽, 왼쪽, 대각선 위치의 dp에서 가능한 한 변의 길이를 확인대각선으로 확장되므로 최솟값으로 저장해야 함이때, 한 변이 증가 되므로 최솟값+1🔎 점화식dp[n] = min( dp[i-1][j-1] , dp[i-1][j], dp[i][j-1] ) + 1class Solution{ public int solution(int [][]board) { int rows=board.length; int cols=board[0].length; // 최대 한 변의 길이 int area=0; ..

  • format_list_bulleted 코딩테스트/문제풀이
  • · 2025. 1. 6.
  • textsms

[ 프로그래머스 ] #12902 : 3 x n 타일링 - JAVA

🔗 3 x n 타일링🔎 점화식$f(n) = f(n-2) * f(2) + f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2$class Solution { static int MOD=1000000007; public int solution(int n) { long [] dp = new long [n+1]; // 초기 값 dp[2] = 3; for(int i = 4; i

  • format_list_bulleted 코딩테스트/문제풀이
  • · 2025. 1. 5.
  • textsms

[ 프로그래머스 ] #42898 : 등굣길 - JAVA

🔗 등굣길🔎 Dynamic Programming작은 문제를 통해 큰 문제 해결 가능(i, j)의 값을 구하려면 이전 칸들의 값(dp[i-1][j], dp[i][j-1])을 이용하여 구할 수 있음중복계산 많음dp[i][j]에 최단 경로의 개수를 저장해 재사용최적 부분 구조문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있음(i, j)로 가는 경로의 개수는 (i-1, j)와 (i, j-1)에서의 경로 개수만 알면 구할 수 있음점화식 기반의 계산웅덩이인 경우 dp[i][j]=0나머지 dp[i][j]=dp[i-1][j]+dp[i][j-1]class Solution { static int MOD=1000000007; static int[][]dp; public int solution(in..

  • format_list_bulleted 코딩테스트/문제풀이
  • · 2025. 1. 2.
  • textsms

[ 프로그래머스 ] #12900 : 2 x n 타일링 - JAVA

🔗2 x n 타일링class Solution { // Dynamic Programming public int solution(int n) { // 모듈러 값 int MOD = 1000000007; // dp 배열 초기화 if (n == 1) return 1; if (n == 2) return 2; // 동적 계획법 배열 초기화 int[] dp = new int[n + 1]; dp[1] = 1; // n = 1 dp[2] = 2; // n = 2 // 점화식에 따라 dp 계산 for (int i = 3; i

  • format_list_bulleted 코딩테스트/문제풀이
  • · 2024. 12. 30.
  • textsms

[ 알고리즘 ] BackTracking

재귀적으로 문제를 해결하되 상태가 제한조건에 위반되는지 판단확인 중인 상태가 제한 조건에 위배된다면 그 상태 이후의 탐색을 하지 않고 다음 단계로 탐색을 진행함🔍 백트래킹 vs. DFS(Depth First Search)공통점원하는 값을 찾기 위해서 탐색하는 알고리즘차이점백트래킹 : 불필요한 탐색을 하지 않고 조건에 맞지 않으면 더 이상 탐색을 진행하지 않음, 확인해야하는 경우의 수 줄일 수 있음DFS : 모든 경우의 수를 탐색[ 프로그래머스 ] #1835 : 단체사진 찍기 - JAVA

  • format_list_bulleted 코딩테스트/개념정리
  • · 2024. 12. 30.
  • textsms
  • navigate_before
  • 1
  • ···
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • navigate_next
공지사항
전체 카테고리
  • 분류 전체보기 (106) N
    • Java (15)
    • SpringBoot (0)
    • 코딩테스트 (57) N
      • 개념정리 (7)
      • 문제풀이 (50) N
    • 자격증 (16) N
      • 정보처리기사 (12)
      • AWS Solution Architecture (4) N
    • JavaScript (1)
    • Vue.js (8)
    • 프로젝트 (1)
    • RabbitMQ (1)
    • Network (5) N
    • Database (2)
최근 글
인기 글
최근 댓글
태그
  • #bfs
  • #dynamic_programming
  • #vue.js
  • #HashMap
  • #Stack
  • #소프트웨어개발
  • #queue
  • #소프트웨어설계
  • #정보처리기사
  • #Interview
전체 방문자
오늘
어제
전체
Copyright © 쭈미로운 생활 All rights reserved.
Designed by JJuum

티스토리툴바