합과 bitwise or연산이 같게되는 조건

1322번: X와 K  x+y = x | y를 만족하는 k번째로 작은 자연수 y를 구하는 문제 합과 or 연산이 서로 같게되는 조건을 먼저 생각해본다 or연산은 두 bit가 1이면 1이고 두 bit가 0이면 0이고 두 bit가 1,0으로 서로 다르면 1인 연산 두 수를 합하는 것은 어떤 의미인지 생각해본다 x,y를 2진수로 바꿔서 예를 들어 5 = 101이고 12 = 1100인데 이진수끼리 서로 덧셈은 어떻게 하는가? $101 = 0 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0}$ $1100 = 1*2^{3} + 1 * 2^{2} + 0 * 2^{1} + 0 * 2^{0}$ 우측에 2의 거듭제곱으로 바꾼 것끼리 더한다고 생각해보면,  $(0 + 1)*2^{3} + (1+1..

• format_list_bulleted 비트마스킹
• · 2025. 1. 9.
• textsms

(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩  n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제 [1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다 투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데 기존에 알던 투 포인터 풀이는 안먹히니 답이 없다 인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데 근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데 그래도 어떻게 해야하는지 고민되더라고 A[i], A[i+1], A[i+2], A[i+3], ...., A[j] i번과 j번을 가리키고..

• format_list_bulleted 투 포인터 알고리즘
• · 2025. 1. 7.
• textsms

플로이드 워셜로 구하는 그래프의 사이클의 길이

1956번: 운동   시작점에서 다시 시작점으로 돌아오는 사이클을 찾고자 하는데, 이때 길이 합이 가장 작은 사이클을 찾는 문제 사이클을 찾아야하나?  dfs로 돌려서 사이클 찾고 해야하나.. 생각했는데 꼭짓점이 최대 400개이기도 하고 플로이드 워셜로 i번에서 시작해서 i번으로 돌아오는 최단 거리 dp[i][i]를 구하면 될것 같다 사이클이라는게 결국 i번에서 시작해서 i번으로 돌아오는거니까 일반적인 경우와 다르게 dp[i][i] = 0으로 하지말고 dp[i][i] = INF로 초기화함  꼭짓점이 1~V번이니까 1번부터 V번 돌아야하는거 실수하지말고 마지막에 dp[i][i]돌아서 최솟값을 찾으면 그것이 길이가 최소인 사이클의 길이 answer = INF로 변화없으면 사이클이 없는거고 from sys i..

• format_list_bulleted 최단거리 알고리즘
• · 2025. 1. 5.
• textsms

무게가 실수 float인 배낭 문제에 필요한 테크닉

4781번: 사탕 가게  가지고 있는 돈이 있고 사탕의 가격과 칼로리가 주어질때, 주어진 돈으로 얻을 수 있는 최대 칼로리를 구하는 문제 각 사탕은 중복해서 구매할 수 있다 무한 배낭 문제인데 특이한 점은 무게가 소수점 둘째자리까지 주어진다는 점 배낭 문제로 해결하고 싶어도 배열의 크기는 실수로 만들수 없다 그러면 어떻게 해야할까? 소수점 둘째자리까지 주어지기 때문에, 실수인 가격을 모두 100을 곱해서 정수로 만들면 모두 동등하게 100을 곱했기 때문에 아무 문제가 없다 그리고 무한 배낭 문제이기 때문에 무게를 순회할때는 정방향으로 순회하도록 for i in range(p,m+1): 이렇게 from sys import stdinwhile 1: n,m = stdin.readline().rstrip(..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 4.
• textsms

무한 배낭 문제 unbounded knapsack에 대한 또 다른 핵심 고찰(dp[i] = min(dp[i], dp[i-k*w[j]] + k*v[j]) = min(dp[i], dp[i-w[j]] + v[j]))

1. 무한 배낭 문제(unbounded knapsack) 일반적인 배낭 문제는 무게가 제한된 배낭에 특정 물건을 최대 가치로 담는 방법을 찾는 문제인데, 각각의 물건은 최대 하나씩만 담을 수 있다 https://deepdata.tistory.com/474 배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건deepdata.tistory.com   근데 각 물건을 무한히 담을 수 있는 경우, 그러한 문제를 unbounded knapsack 무한 배낭 문제라고 부른다  알고보니 이미 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 27.
• textsms

최소 편집 거리(edit distance)를 구하는 알고리즘

1. 문제 두 문자열 S1, S2가 주어질때, 다음과 같은 3가지 연산을 임의의 횟수만큼 실행할 수 있다. 1) 임의의 위치에 원하는 문자 하나를 삽입 예: banana >>> banacna 2) 임의의 위치에 있는 문자 하나를 삭제 예: banana >>> banna 3) 임의의 위치에 있는 문자 하나를 원하는 문자로 대체 예: banana >>> canana  2. 재귀를 이용한 해법 문자열의 왼쪽이나 오른쪽 끝에서부터 한문자씩 처리한다. 왼쪽부터 처리해서, 첫번째 문자가 서로 일치하는 경우, 나머지 문자에 대해 재귀적으로 처리 첫번째 문자가 서로 일치하지 않는다면, 여기에 3가지 작업으로 삽입, 제거, 대체 작업을 수행할 수 있다. 그리고 나머지 부분에 대해 재귀적으로 계산  첫번째 문자가 일치하면..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 11.
• textsms