티스토리

sxunea
검색하기

블로그 홈

sxunea

sxunea.tistory.com/m

sxunea 님의 블로그입니다.

구독자
1
방명록 방문하기

주요 글 목록

  • [Algorithm] 백준 11660, 15724, 1749 : DP 누적합 이번주에는 dp + 누적합을 위주로 풀고 있는데, dp는 뭐 ... 점화식이 8할이라 따로 전략을 기록해 놓을 건 없다. 하지만 누적합은 문제 풀이 방법이 대부분 비슷하니 이 참에 정리해놓자.   누적합이란누적합(구간 합)은 배열에서 특정 범위의 합을 빠르게 계산하기 위해 사용하는 기법이다. 배열의 각 위치까지의 값을 미리 더해두고, 필요한 구간의 합을 빠르게 계산하는 방식으로, 주로 1차원 혹은 2차원 배열에서 사용된다.  주로 특정한 구간을 주고 합 / 최대 합을 구하는 문제가 자주 나오는데, 반복문을 계속 돌려서 모든 경우의 수를 계산해 합을 구하는 것보다 누적합 알고리즘을 떠올리면 훨씬 빠르게 풀 수 있음을 기억하자.    1차원 배열의 누적합1차원 배열의 경우, 누적합을 구하려면 arr[i]까지.. 공감수 5 댓글수 3 2024. 10. 17.
  • [Algorithm] 백준 16508 : 비트마스크, 백트래킹 가볍게 풀고 자려고 했는데 ....... 블로그까지 쓰게 만든 이 녀석 누가 실버3래 대체 누가 .... 라고 분노했지만 백트래킹으로 푸니까 알겠더만요  거두절미하고 문제 보시죠   문제는 길지만 결국 원하는 글자를 만들기 위해 책 표지를 오린다. 그리고 원하는 글자를 만들기 위해 사용한 책 조합이 가장 저렴한 경우의 값을 구하는 문제이다. 이 문제는 두가지 방식으로 보통 풀이를 많이 하는 듯 하다. 특히 비트마스킹은 처음 접하는 거라 기록해놓고자 한다.   비트마스킹 비트마스크는 정수의 이진수 표현을 활용해 집합이나 상태를 간단하게 표현하는 기법이다.  예를 들어 책이 3권 있을 때 비트마스크는 다음을 의미한다. 비트마스크 000은 아무 책도 선택하지 않은 경우비트마스크 001은 1번째 책만 선택한 경.. 공감수 1 댓글수 0 2024. 10. 8.
  • [Algorithm] 백준 15655 : 백트래킹 백트래킹 알고리즘 백트래킹 알고리즘은 조합, 순열, 부분집합, 경로 탐색 등과 같은 문제를 해결하는 데 유용한 기법이다. 이 알고리즘은 깊이 우선 탐색(DFS)을 기반으로 하며, 가능한 모든 경우의 수를 탐색하면서 조건에 맞지 않는 경우를 조기에 차단하는 방식으로 작동한다. 사실 개인적으로 어려워하는 알고리즘 유형이기도 해서, 못푼 문제를 만난 김에 정리해놓자. 백트래킹의 풀이방식은 결국 이렇게 귀결된다.  상태 선택: 가능한 선택지 중 하나를 선택한다.유효성 검증: 현재 상태가 문제의 조건을 만족하는지 검증한다.완전 탐색: 모든 선택지를 시도하여 최종 해를 찾는다.되돌리기: 조건을 만족하지 않는 경우, 선택한 요소를 제거하고 다른 선택지를 탐색한다.가장 포인트는 되돌리기로, 쉽게 말하면 되나 일단 해보.. 공감수 3 댓글수 1 2024. 10. 7.
  • [Algorithm] 백준 30804 : 슬라이딩 윈도우, 투 포인터 알고리즘 슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트와 같은 연속된 데이터 구조에서 특정 구간 내의 요소들을 효율적으로 처리하기 위한 기법으로, 코딩테스트 빈출 유형은 아니지만 풀이 기법을 알아야 빠르게 해결할 수 있기 때문에 블로그에 따로 정리해 업데이트 하고자 한다.  슬라이딩 윈도우 알고리즘슬라이딩 윈도우는 일정한 크기의 창(window)을 배열 위에 설정하고, 그 창을 배열 위에서 이동(slide)시키면서 문제를 해결한다. 예를 들어, [1,2,3,4,5,6] 이라는 배열에서 연속적인 세개의 숫자의 합의 최댓값을 구하고자 한다고 하자.그렇다면 [1,2,3], [2,3,4], ... ,[4,5,6]의 순으로 부분배열을 찾아나가고 최댓값을 구할 것이다. 이 과정에서 [2,3,4]는 .. 공감수 0 댓글수 0 2024. 8. 18.
  • [Algorithm][문법] 반복문 알고리즘 풀이 언어를 코틀린으로 바꾸면서, 자주 사용되는 문법과 함수들을 정리해보고자 한다. 평소 개발을 하면서 다 익혀두긴 했지만 참고해보자 ~ 일반적인 반복문fun main(args:Array) { for(i: Int in 1..10) print(i) // 1, 2, 3, 4, 5 ... 10 val len: Int = 7 for(i in 1..7) print(i) // 1, 2, 3, 4, 5, 6, 7 for(i in 1 until len) print(i) // 1, 2, 3, 4} fun main(args:Array) { for(i: Int in 1..10 step(2)) print(i) // 1,.. 공감수 0 댓글수 1 2024. 7. 23.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.