[백준 kotlin] 3372 보드 점프

[백준 kotlin] 3372 보드 점프

문제 보드게임에서 목표지점까지 도달할 수 있는 경우의 수를 구하는 문제이다.풀이DP를 사용하여 해결할 수 있는 문제이다.Dp배열의 각 원소는 해당 지점까지 갈 수 있는 경우의 수로 구분된다. for (i in 0 until N) { for (j in 0 until N) { val right = matrix[i][j] + j val down = matrix[i][j] + i if (matrix[i][j] == 0) continue if (right  그 후 보드게임을 순회하며 dp배열을 채운다.먼저 보드게임에 적혀있는 숫자 만큼 오른쪽 또는 아래로 이동할 수 있으므로 이동될 오른쪽 좌표와 아래 좌표를 계산한다. 그 후 만약 현재 위치의 dp값이 0이라..

  • format_list_bulleted 알고리즘
  • · 2024. 6. 17.
  • textsms
[프로그래머스 python] 다음 큰 숫자

[프로그래머스 python] 다음 큰 숫자

문제풀이이진수로 변환하는 방법을 알면 간단히 풀 수 있다.전체적인 과정은 다음과 같다. 1. 먼저 처음 수와 그 수보다 1 큰 수를 선언한다.2. 두 수를 이진수로 변환해서 1의 개수를 세는 함수에 입력한다.3. 1의 개수가 일치하면 반복을 종료하고 일치하지 않으면 수를 1증가시킨다.  tmp = n + 1처음 수는 n으로 받아오고 n보다 1 큰 수를 정의하였다. def calOneNum(num1, num2): tranNum1 = deque() cntNum1 = 0 cntNum2 = 0 while num1 > 0: if (num1 % 2 == 1): cntNum1 += 1 num1 //= 2 while num2 > 0:..

  • format_list_bulleted 알고리즘
  • · 2024. 6. 1.
  • textsms
[백준 python] 1926 그림

[백준 python] 1926 그림

문제 풀이DFS를 사용하면 간단히 해결할 수 있는 문제이다.n, m = map(int, input().split())graph = [list(map(int, input().split())) for _ in range(n)]먼저 그래프의 크기와 정보를 입력받는다.visited = [[False] * m for _ in range(n)]dr = [1, -1, 0, 0]dc = [0, 0, -1, 1]방문여부를 저장해 줄 visited 변수를 선언한뒤 False로 초기화하였다.def DFS(sr, sc): global tmp tmp += 1 visited[sr][sc] = True for i in range(4): nr = sr + dr[i] nc = sc..

  • format_list_bulleted 알고리즘
  • · 2024. 5. 30.
  • textsms
[백준 kotlin] 1956 운동

[백준 kotlin] 1956 운동

문제 그래프 중 사이클을 찾는 문제이다.풀이그래프 알고리즘 중 사이클을 고려해야 하는 문제이다.기존에 자주사용하는 다익스트라의 경우 사이클은 감지하지 못하므로 다른 알고리즘을 사용해야 한다.  따라서 플루이드 워셜 알고리즘을 사용하였다. const val INF = Int.MAX_VALUE / 2먼저 최대값을 정의하였다. 최대값은 MAX_VALUE에 2를 나누어 주었는데 그 이유는 overflow를 방지하기 위함이다. val (V, E) = readLine().split(" ").map { it.toInt() } val node = Array(V + 1) { IntArray(V + 1) {INF} } repeat(E) { val (a, b, c) = readLine().split(..

  • format_list_bulleted 알고리즘
  • · 2024. 5. 27.
  • textsms
[백준 kotlin] 17609 회문

[백준 kotlin] 17609 회문

문제 회문 또는 유사 회문이 가능한지 출력하는 문제이다.풀이투포인터를 이용하여 해결하였다.해결 아이디어는 다음과 같다.투포인터를 문자열 양 끝에 설정한다.왼쪽 포인터와 오른쪽 포인터를 하나씩 움직이면서 비교한다.만약 비교시 두 문자가 다르다면 유사회문가능성을 표시하고 재귀한다. 이 때 틀린 문자열 두개를 기준으로 왼쪽 +1 오른쪽 -1 로 각각 한개씩 재귀한다.재귀 하여 받은 리턴값이 0 이면 유사회문이므로 1을 출력한다. fun twoPointer(str: String, isDeleted: Boolean, left: Int, right: Int): Int { var left = left var right = right while (left 투 포인터의 구현은 다음과 같다. 유사회문을 위..

  • format_list_bulleted 알고리즘
  • · 2024. 5. 25.
  • textsms
[프로그래머스 kotlin] 보석 쇼핑

[프로그래머스 kotlin] 보석 쇼핑

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 모든 보석을 쇼핑하는 최단 부분수열을 구하는 문제이다.풀이해당 문제는 부분수열 문제와 비슷하기 때문에 투포인터를 이용하여 해결하였다.기본적인 해결 과정은 다음과 같다. 보석의 종류를 Set을 이용하여 중복되지 않게 저장한다. 보석의 이름과 개수를 담을 map을 선언한다. 반복문을 실행한다.저장된 map의 크기와 모든 보석의 종류의 크기가 같다면 가장 왼쪽에 저장된 보석을 한개 제거한다. 이 때 보석의 개수가 0이라면 보석자체를 map에서 제거한다.map에 저장된 보석종류와 전체 보석종류의 개수가 일치하지 않..

  • format_list_bulleted 알고리즘
  • · 2024. 5. 19.
  • textsms