티스토리

Developer-TraXer

검색하기

블로그 홈

Developer-TraXer

developer-traxer.tistory.com/m

TraXer 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

Baekjoon 9997. 폰트 / Python 9997. 폰트난이도 : 골드 3소요 시간 : 30분날짜 : 2025.01.10언어 : 파이썬알고리즘 유형 : 비트마스킹, 완전탐색, 재설명 보기전에 문제 풀어보러 가기1. 문제 설명단어들이 주어진다.단어들을 조합해서 문장을 만든다.(중복X, 순서X)모든 알파벳이 포함되는 문장의 개수를 구한다.2. 해결 방식단어를 비트로 바꾸어 저장한다.목표 goal = (1 재귀함수 + 완전탐색 : sol(bit, idx)idx를 0부터 시작해서 하나씩 늘려가면서 확인한다.종료조건 1 : 현재 bit가 goal에 도달하면 남은 단어들의 모든 경우의 수 $2^(n - idx)$ 를 반환하고 종료종료조건 2 : idx가 n이 되면 0을 반환하고 종료재귀 : 현재 idx에 해당하는 단어를 넣는 함수 호출, 안넣는 함수 호출.. 공감수 0 댓글수 0 2025. 1. 10.
Baekjoon 1520. 내리막 길 / Python 1520. 내리막 길난이도 : 골드 3소요 시간 : 20분날짜 : 2025.01.09언어 : 파이썬알고리즘 유형 : dp, bfs설명 보기전에 문제 풀어보러 가기1. 문제 설명높이가 담겨있는 그래프가 주어진다.내리막길로만 이동해서 1,1부터 m,n까지 이동하는 경우의 수를 구하기2. 해결 방식dp[i][j] : i,j에서의 이동가능한 경우의 수거꾸로 탐색하여 dp값을 채운다.재귀함수 : sol(x,y)x,y : 현재 위치x,y가 -1이 아니면 방문한 경우이므로, 종료dp의 값을 0으로 초기화 시킨 후, 다음 방문 가능지역의 dp값을 더해준다.결과적으로 재귀함수의 특성때문에, 끝점부터 세는 구현방식이 된다.3. 정답 코드import sys;input=sys.stdin.readlinesys.setrecurs.. 공감수 1 댓글수 0 2025. 1. 9.
Baekjoon 2629. 양팔저울 / Python 2629. 양팔저울난이도 : 골드 3소요 시간 : 25분날짜 : 2025.01.09언어 : 파이썬알고리즘 유형 : dp, 배낭문제(napsack)설명 보기전에 문제 풀어보러 가기1. 문제 설명양팔저울이 있고, 가진 추의 무게들이 주어진다.무게를 확인할 구슬들이 주어진다.구슬의 무게를 확인가능한지 여부를 출력한다.2. 해결 방식dp[i][j] : i개의 구슬을 사용, j의 무게를 잴수 있는 지 여부dp의 크기 $x*y$ : x는 개수이므로 n$ + 1$, y는 무게이므로 구슬들의 최대 무게인 sum(weights)재귀함수 구현 sol(cnt, cost)cnt : 현재 구슬의 인덱스, 방문한 구슬의 개수를 나타내기도 한다.cost : 확인한 현재 무게종료조건 : cnt가 n 인 경우 종료, dp[cnt][c.. 공감수 0 댓글수 1 2025. 1. 9.
Baekjoon 2293. 동전 1 / Python 2293. 동전 1난이도 : 골드 4소요 시간 : 10분날짜 : 2025.01.09언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명동전의 종류가 주어진다.적당히 조합해서(중복가능, 순서없음) k원을 만드는 가지수를 구한다.2. 해결 방식dp[i] = i원을 만드는 경우의 수점화식동전 c에 대해서 dp[i] += dp[i-c]이다.이 때, i는 c~k 사이여야 한다.3. 정답 코드import sys;input = sys.stdin.readlinen, k = map(int, input().split())dp = [1] + [0] * k # dp[i] : i원을 만드는 경우의 수for coin in [int(input()) for _ in range(n)]: for i.. 공감수 0 댓글수 0 2025. 1. 9.
Baekjoon 11066. 파일 합치기 / Python 11066. 파일 합치기난이도 : 골드 3소요 시간 : 30분날짜 : 2025.01.09언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명파일 크기 배열이 주어진다.파일을 두 개씩 골라서 합칠 수 있다.두 파일은 합쳐지면 크기가 더해지며 하나가 되고, 합치는데에는 두 파일의 크기의 합이 비용으로 든다.최소 비용으로 파일을 하나로 합치기2. 해결 방식DP배열 : dp[i][j] = i부터 j까지 합치는데 필요한 최소 비용prefix_sum(누적합)을 이용해서 좀 더 효율적인 구현을 했다.점화식dp[i][i] 는 0이다.dp[i][i+1] 은 두 파일 크기의 합이다.dp[i][j] 는 i~j 사이에 어떤 수 p가 있다고 가정했을 때, p를 기준으로 왼쪽 오른쪽을 합치는 것들의.. 공감수 0 댓글수 0 2025. 1. 9.
Baekjoon 10986. 나머지 합 / Python 10986. 나머지 합난이도 : 골드 3소요 시간 : 10분날짜 : 2025.01.08언어 : 파이썬알고리즘 유형 : 누적 설명 보기전에 문제 풀어보러 가기1. 문제 설명숫자 배열이 주어진다.연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구한다.2. 해결 방식나머지의 개념두 수 A, B가 있다고 할 때, 두 수의 나머지를 a, b라고 하자.A + B의 나머지는 a + b의 나머지와 같고, A - B의 나머지는a - b의 나머지와 같다.구간 합구간 합을 따로 배열로 저장하지 않는다.0번부터 n-1번 배열을 순차적으로 돌아서 그 나머지를 x라고 했을 때, cnt[x] 에 하나씩 더해준다.결과값구간의 나머지 합을 구할 때, 나머지가 같은 구간들을 구해주면 된다. 예를 들어, 1 ~ 9가 나머지.. 공감수 1 댓글수 0 2025. 1. 8.
Baekjoon 1275. 커피숍2 / Python 1275. 커피숍2난이도 : 골드 1소요 시간 : 15분날짜 : 2025.01.08언어 : 파이썬알고리즘 유형 : 세그먼트 트리설명 보기전에 문제 풀어보러 가기1. 문제 설명정수배열이 주어진다.x, y, a, b의 쿼리가 주어진다.x~y의 합을 출력하고,a번째 수를 b로 바꾼다.2. 해결 방식세그먼트트리 자료구조의 기본적인 문제이다.세그먼트트리의 생성세그먼트 트리 누적 합 구하기세그먼트 트리 갱신3. 정답 코드import sys;input = sys.stdin.readlinedef make_seg(n, arr): seg = [0] * (4 * n) def make(node, s, e): if s == e: seg[node] = arr[s] r.. 공감수 0 댓글수 0 2025. 1. 8.
Baekjoon 1406. 에디터 / Python 1406. 에디터난이도 : 실버 2소요 시간 : 40분날짜 : 2025.01.08언어 : 파이썬알고리즘 유형 : 연결리스트, 스택설명 보기전에 문제 풀어보러 가기1. 문제 설명주어진 문자를 주어진 명령에 따라 실행한 뒤, 마지막 남은 문자열을 출력한다.명령어는 커서를 기준으로 시작하고, 시작할 때의 커서는 맨 뒤이다.L : 커서를 왼쪽으로 한 칸 (커서가 맨 앞이면 무시)D : 커서를 오른쪽으로 한 칸 (커서가 맨 뒤이면 무시)B : 커서 왼쪽 문자를 삭제 (커서가 맨 앞이면 무시)P # : 커서 왼쪽에 # 이라는 문자 추가2. 해결 방식연결리스트 연습을 위해 고른 문제인 만큼 연결리스트를 활용해서 풀이했다.(리스트에 insert를 하는 방법도 통과되는 듯....)연결리스트 기본 구조Node : data.. 공감수 1 댓글수 0 2025. 1. 8.
Baekjoon 25682. 체스판 다시 칠하기 2 / Python 25682. 체스판 다시 칠하기 2난이도 : 골드 4소요 시간 : 20분날짜 : 2025.01.06언어 : 파이썬알고리즘 유형 : 누적 합설명 보기전에 문제 풀어보러 가기1. 문제 설명아무렇게나 칠해져있는 n * m 의 판이 있음.체스판은 검은색, 흰색이 번갈아 칠해져야함.k * k를 잘라서 체스판으로 만드려고 함, 칠해야하는 최소 개수는?2. 해결 방식미리 완벽한 체스판을 만들어놓기, (두개 : 왼쪽상단이 검은색, 흰색)틀린개수의 누적합을 구하기현재의 틀린개수 = 왼쪽의 틀린개수 + 위쪽의 틀린개수 - 왼쪽 위의 틀린개수 + 현재칸의 틀린지 여부전체 돌면서 최솟값 확인하기3. 정답 코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().spl.. 공감수 0 댓글수 0 2025. 1. 6.
Baekjoon 3946. 랜덤 걷기 / Python 3946. 랜덤 걷기난이도 : 플래티넘 3소요 시간 : 1시간날짜 : 2025.01.05언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명동전 던지는 횟수 N, 앞면이 나올 확률(왼쪽으로 갈 확률)L, 뒷면이 나올 확률(오른쪽으로 갈 확률)R 이 주어진다.N번 동전을 던졌을 때, '전체 이동경로의 가장 오른쪽 위치'의 기댓값을 구하기옆면이 나올 수도 있고, 가만히 있는다.2. 해결 방식2차원 dpdp[i][j] = i개의 동전을 던졌을 때, 시작 위치가 j인 경우 가장 오른쪽 위치의 기댓값점화식 설명l * (dp[i-1][j+1] - 1) : 왼쪽으로 이동할 확률 * (그 전 dp의 오른쪽 위치의 기댓값 - 1)(1-l-r) * dp[i-1][j] : 가만히 있을 확률 *.. 공감수 0 댓글수 0 2025. 1. 6.
Baekjoon 6549. 히스토그램에서 가장 큰 정사각형 / Python 6549. 히스토그램에서 가장 큰 정사각난이도 : 플래티넘 5소요 시간 : 35분날짜 : 2025.01.05언어 : 파이썬알고리즘 유형 : 분할정복, 세그머트트리, 스택설명 보기전에 문제 풀어보러 가기1. 문제 설명히스토그램의 내부의 직사각형들 중 가장 넓이가 큰 직사각형을 구하기2. 해결 방식스택 활용히스토그램을 순회하면서 현재 높이보다 낮은 높이를 만날 때마다 직사각형 넓이를 계산한다.0을 만난다면 스택을 초기화한다.시간복잡도 : O(n)세그먼트트리각 구간의 최소 높이를 세그먼트 트리로 저장한다.구간의 최소높이 * 구간의 크기 = 넓이전체 시간복잡도: O(nlongn)분할정복(사용하지 않았지만, 가능한 방법)(히스토그램에서 가장 낮은 높이를 기준으로 좌우로 분할)을 반복하는 방식시간 복잡도 : O(n.. 공감수 0 댓글수 0 2025. 1. 6.
Baekjoon 2156. 포도주 시식 / Python 2156. 포도주 시식난이도 : 실버 1소요 시간 : 15분날짜 : 2025.01.05언어 : 파이알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명포도주를 선택하면 모두 마셔야 하고, 제자리에 놓아야 한다.연속으로 3잔을 마실 수 없다.마실 수 있는 포도주 양의 최댓값을 구하기2. 해결 방식dp 사용 : dp[i][j] = i번 포도주를 j잔째 마시고 있는 경우 포도주양의 최댓값.0잔, 즉 i번 포도주를 안먹는다면, dp[i-1]의 값들 중 최댓값이 dp값이다.i번 포도주가 연속된 첫번째 잔이라면, dp[i-1][0]의 값과 dp[i-2]값들 중 최댓값에 현재 포도주 양을 더한 값이 dp 값이다.두번째 잔인 경우, dp[i -1][1]의 값에 현재 포도주 양을 더해주면 된다.3. 정답.. 공감수 0 댓글수 0 2025. 1. 6.
Baekjoon 32034. 동전 쌍 뒤집기 / Python 32034. 동전 쌍 뒤집기난이도 : 플래티넘 5소요 시간 : 25분날짜 : 2025.01.02언어 : 파이썬알고리즘 유형 : 스택, 그리디설명 보기전에 문제 풀어보러 가기1. 문제 설명N개의 동전이 일렬로 놓여있다.조작을 원하는대로 할 수 있다.서로 이웃하고, 같은 면인, 두 개의 동전을 둘 다 뒤집기모든 동전이 앞면이 보이게 할 수 있는가? 가능하다면 최소 조작횟수를 구하라.2. 해결 방식자료구조 : 스택을 활용한다.먼저 뒷면의 위치를 저장하고 개수를 센다.뒷면의 개수가 2로 나누어지지 않으면 불가능, 0이면 답이 0뒷면인 동전들을 돌면서 스택을 활용한다.스택이 비어있다면 스택에 넣기스택의 마지막 요소와 현재 요소의 인덱스 차이가 짝수라면, 가운데의 앞면을 다 뒤집고 다시 뒷면으로 다 뒤집으면 모두 .. 공감수 0 댓글수 0 2025. 1. 2.
Bakejoon 17471. 게리맨더링 / Python 17471. 게리맨더링난이도 : 골드 3소요 시간 : 20분날짜 : 2024.01.02언어 : 파이썬알고리즘 유형 : 그래프이론, bfs, dfs, 조합설명 보기전에 문제 풀어보러 가기1. 문제 설명각각의 인구가 있는 구역이 있음.구역을 두 선거구로 나누어야 함.같은 선거구에 속한 구역은 항상 연결되어있어야 함.한 선거구에는 최소 1개 이상의 구역이 있어야 함.각 선거구의 인구의 차이를 최소로 하기2. 해결 방식구역의 개수가 최대 10밖에 안되어서 그냥 완전탐색을 하기로 했다.가능한 모든 선거구의 조합을 구해서 확인한다.먼저 선거구가 연결되어있는지 확인 : 기본적인 bfs로 해결연결되어있다면 최소값 갱신3. 정답 코드import sys;input = sys.stdin.readlinefrom itertoo.. 공감수 0 댓글수 0 2025. 1. 2.
Baekjoon 23250. 하노이 탑 K / Python 23250. 하노이 탑 K난이도 : 골드 4소요 시간 : 30분날짜 : 2025.01.02언어 : 파이썬알고리즘 유형 : 재귀, 이분탐색설명 보기전에 문제 풀어보러 가기1. 문제 설명n개의 원판이 있는 하노이탑에서 k 번째 이동을 구하시오2. 해결 방식이분탐색 + 재귀일반적인 하노이 탑의 재귀함수를 사용한다.바뀌는 점전체경로를 구하는게 아니므로, 하노이탑 전체 크기를 계속 하나씩 줄여나갈 수 있다.만약 중앙을 옮기는 경우라면 바로 출력하면 되고,중앙 이후의 경우라면, k값을 갱신해주면서 재귀함수를 돌리면 된다.3. 정답 코드n, k = map(int, input().split())def hanoi(x:int=n, now:int=k, a:int=1, b:int=3, c:int=2): if x == 1.. 공감수 0 댓글수 0 2025. 1. 2.
Baekjoon 1038. 감소하는 수 / Python 1038. 감소하는 수난이도 : 골드 5소요 시간 : 20분날짜 : 2025.01.02언어 : 파이썬알고리즘 유형 : 완전탐색, 백트래설명 보기전에 문제 풀어보러 가기1. 문제 설명음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다.n번째 감소하는 수를 출력하라 없다면 -1을 출력하라.2. 해결 방식감소하는 수를 다 구해놓고, 출력한다.감소하는 수 구하기9876543210 에서 완전탐색으로 하나씩 빼면서 집합에 집어넣는다.그 후 정렬한다.3. 정답 코드import sys# input = sys.stdin.readlinesys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")sys.s.. 공감수 1 댓글수 0 2025. 1. 2.
Baekjoon 2042. 구간 합 구하기 / Python 2042. 구간 합 구하기난이도 : 골드 1소요 시간 : 40분날짜 : 2025.01.01언어 : 파이썬알고리즘 유형 : 세그먼트 트리설명 보기전에 문제 풀어보러 가기1. 문제 설명숫자배열이 주어진다.커맨드들이 두 종류로 주어진다.a가 1이면 b번째 숫자를 c로 바꾼다.a가 2이면 b 부터 c까지의 합을 출력한다.2. 해결 방식우선 주어진 숫자 배열에 맞게 세그먼트 트리를 만들어준다.누적 합 : 세그먼트 트리의 누적 합 구하는 알고리즘을 사용숫자 변경 : 자식 노드를 찾아 들어가면서, 변경할 인덱스가 나오면 숫자를 바꾸어 준다.이 때, 재귀함수(자식노드를 찾는)가 종료되면 그 부모 노드에서의 세그트리의 값을 갱신해주어야 한다.3. 정답 코드import sys; input = sys.stdin.readli.. 공감수 0 댓글수 0 2025. 1. 1.
Baekjoon 1019. 책 페이지 / Python 1019. 책 페이지난이도 : 플래티넘 5소요 시간 : 20분날짜 : 2024.12.31언어 : 파이썬알고리즘 유형 : 구현, 수학설명 보기전에 문제 풀어보러 가기1. 문제 설명1부터 n까지 [0, 1 ,2, ,,, 9]가 각각 몇 번 나오는지 구하기1 2. 해결 방식자리수 별로 반복하기. (최대 9번)factor = 1 ($10^0$)부터 시작해서 10씩 곱해가며 반복한다.현재 자리를 기준으로, 현재자리 숫자와 더 높은 자리 숫자, 더 낮은 자리 숫자로 구분한다.0부터 9까지 확인하여 결과값에 더해준다.현재자리수보다 작은 수 : (높은자리 숫자 + 1) * factor를 더 해준다.현재자리 수 : 높은자리 숫자 * factor + 낮은자리 숫자 + 1을 더 해준다.현재자리 수보다 큰 수 : 높은자리 숫.. 공감수 0 댓글수 0 2024. 12. 31.
Baekjoon 2263. 트리의 순회 / Python 2263. 트리의 순회난이도 : 골드 1소요 시간 : 10분날짜 : 2024.12.30언어 : 파이썬알고리즘 유형 : 재귀, 트리, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명트리의 크기 n이 주어짐중위순회(inorder)와 후위순회(postorder)가 주어짐전위순회(preorder)결과를 구하기.2. 해결 방식중위순회는 왼쪽부터 하위트리를 우선으로 트리를 방문 후 루트를 방문하는 방식후위순회는 왼쪽부터 "하위트리를 모두 방문한 후" 루트를 방문하는 방식전위순회는 루트노드부터 시작하여 왼쪽 자식먼저 방문하는 방식재귀함수의 원리 및 사용후위순회의 마지막 요소는 현재 서브트리의 루트 노드이다.중위순회에서의 루트를 기준으로 왼쪽, 오른쪽으로 서브트리를 나눈다.루트 노드를 출력한다.(전위순회)3... 공감수 0 댓글수 0 2024. 12. 30.
Baekjoon 12850. 본대 산책 2 / Python 12850. 본대 산책 2난이도 : 골드 1소요 시간 : 15분날짜 : 2024.12.29언어 : 파이썬알고리즘 유형 : 행렬, 그래프, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명그래프가 주어진다. 만들어야 한다. 귀찮다....d분동안 산책한다.정보과학관을 돌아오는 경로의 경우의 수를 구한다.2. 해결 방식행렬에 대한 이해를 필요로 하는 문제이다.i분 산책한 경로 배열 * j분 산책한 경로 배열 을 하면 i+j분 산책을 한 경로를 구할 수 있다.이를 활용하면 시간복잡도를 log2(d)로 해결가능.3. 정답 코드# 숭실대 지도 그리기arr = [[0] * 8 for _ in range(8)]arr[0][1], arr[1][0] = 1, 1arr[0][2], arr[2][0] = 1, 1arr.. 공감수 0 댓글수 0 2024. 12. 29.
Baekjoon 28707. 배열 정렬 / Python 28707. 배열 정렬난이도 : 골드 1소요 시간 : 20분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 다익스트라, 그래프, 해시, 트리, 최단 경설명 보기전에 문제 풀어보러 가기1. 문제 설명배열 A가 주어진다.커맨드 l, r, c가 주어진다 : l과 r을 바꾼다. c의 비용이 든다.커맨드들을 이용해서 최소비용으로 정렬하라.2. 해결 방식배열을 문자열로 저장한다.배열을 목표배열까지 가는 최소경로를 구하면 된다.다익스트라를 활용하여 최소비용을 구한다.3. 정답 코드import sysinput = sys.stdin.readlinefrom heapq import heappop, heappushfrom collections import defaultdictn = int(input()) # .. 공감수 1 댓글수 1 2024. 12. 28.
Baekjoon 10775. 공항 / Python 10775. 공항난이도 : 골드 2소요 시간 : 15분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 그리디, 분리집합설명 보기전에 문제 풀어보러 가기1. 문제 설명G개의 게이트와 P개의 비행기가 있다.비행기를 게이트에 도킹해야 한다.$g_i$가 입력으로 주어지고, 1 ~ $g_i$ 의 게이트에 i번 게이트를 도킹해야한다.게이트에 도킹을 할 수 없으면 끝도킹 수의 최댓값을 구하자.2. 해결 방식union-find 알고리즘을 사용한다. - 게이트에 각자의 게이트 번호를 부여한다. - 비행기번호를 union-find를 통해 게이트 집합을 만들어 관리한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.. 공감수 1 댓글수 0 2024. 12. 28.
알고리즘 유형공부 - 우선순위 큐 (Priority Queue) 우선순위 큐 (Priority Queue)1. 개요우선순위 큐는 각 원소에 우선순위를 부여하여, 우선순위가 높은 원소가 먼저 처리되도록 하는 데이터 구조일반적인 큐는 FIFO(First In, First Out) 방식이지만, 우선순위 큐는 우선순위를 기준으로 순서가 정해짐. 주로 힙을 사용하여 구현되며, 배열이나 연결 리스트를 통해서도 만들 수 있음.2. 우선순위 큐의 특성1. 원소의 입, 출삽입: 새로운 원소를 큐에 추가삭제: 가장 높은 우선순위를 가진 원소를 큐에서 제거조회: 현재 가장 높은 우선순위를 가진 원소를 반환2. 배열, 연결리스트, 힙을 통한 우선순위 큐구현 방식삽입 시간복잡도삭제 시간복잡도공간복잡도특징배열 (정렬X)O(1)O(N)O(N)삽입은 빠르지만 삭제 시 전체를 탐색해야 함.배열 .. 공감수 0 댓글수 0 2024. 12. 27.
Baekjoon 19236. 청소년 상어 / Python 19236. 청소년 상어난이도 : 골드 2소요 시간 : 35분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 백트래킹, 구현, 시뮬레이션설명 보기전에 문제 풀어보러 가기1. 문제 설명상어 이동, 물고기 이동 을 반복함.상어 이동경계 안에서만 이동물고기가 있는 곳으로만 이동여러 칸 이동 가능물고기의 방향을 흡수?함이동 불가 : 집으로 감물고기 이동번호 작은 물고기부터 순서대로 이동경계 안에서만 이동한 칸만 이동상어 있는 곳으로 이동 불가다른 물고기가 있다면 자리 교체이동 불가 : 이동 안함"잡아먹은 물고기 번호의 합"의 최댓값을 구하라.2. 해결 방식dfs + 백트래킹상어 이동방향에 맞게 이동시키고 해당 자리의 물고기를 배열에서 없앤다.이동할 때마다 res를 max 값으로 갱신했다.물고기 이동각.. 공감수 0 댓글수 0 2024. 12. 27.
Baekjoon 9527. 1의 개수 세기 9527. 1의 개수 세기난이도 : 골드 2소요 시간 : 25분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 수학, 비트마스킹, 누적 합설명 보기전에 문제 풀어보러 가기1. 문제 설명$(x)$는 $x$를 이진수로 표현했을 때에 1의 개수를 의미 한다.$a, b$가 주어지면 $$\sum_{x=a}^{b} f(x)$$ 를 구한다.2. 해결 방식음 나는 그냥 재귀함수와 수학으로 풀었는데. 알고리즘 유형은 비트마스킹과 누적 합이라고 한다.내가 사용한 비트마스킹은 연산을 전혀 사용하지 않고 2 ** index를 left shift를 이용해서 표현한 것 뿐..$c = 2 ^ n$ 일 때, $$\sum_{x=0}^{c} f(x) = \frac{n * c}{2} + 1$$ 이다.따라서, $x$ 보다 작은 .. 공감수 0 댓글수 0 2024. 12. 27.
Every CS - Hardware 01 - 컴퓨터 구조 Hardware 01 - 컴퓨터 구조1. 컴퓨터가 이해하는 정보컴퓨터는 사람이 이해하는 방식과는 다르게 정보를 처리한다.컴퓨터는 모든 데이터를 이진수로 변환하여 처리한다.이진수는 0과 1로 이루어진 수로, 전기 신호의 ON(1)과 OFF(0) 상태를 나타내는 방법이다.따라서, 컴퓨터는 모든 정보를 이진수로 변환하고, 연산과 저장을 이진수 형태로 수행한다.이진수는 비트(bit) 단위로 표현되며, 여러 비트들이 모여 바이트(byte)가 된다.1 바이트는 8 비트로 구성되며, 컴퓨터는 이 바이트를 단위로 데이터를 다룬다.예를 들어, 1 바이트는 256가지의 서로 다른 값을 표현할 수 있다.컴퓨터는 텍스트, 이미지, 비디오 등 다양한 정보를 모두 이진수로 바꿔 처리한다.2. 컴퓨터의 핵심 부품컴퓨터의 핵심 부품.. 공감수 1 댓글수 0 2024. 12. 26.
알고리즘 유형공부 - 다익스트라 (Dijkstra) 다익스트라 (Dijkstra)1. 개요다익스트라 알고리즘은 가중치가 양수인 그래프에서 특정 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 2. 알고리즘의 원리시작 정점을 기준으로 초기 거리를 설정하며, 시작 정점의 거리는 0으로 설정한다.방문하지 않은 정점 중에서 가장 가까운 정점을 선택한다.선택한 정점을 기준으로 인접한 정점들의 거리를 갱신한다.모든 정점이 반복될 때까지 반복한다.3. 구현3-1. 구현 1 - 인접 행렬 방식설명동작 방식그래프를 인접 행렬로 표현하며, 각 정점 간의 연결 여부와 가중치를 행렬로 나타냄방문 여부를 저장하는 배열과 현재까지의 최소 서리를 저장하는 배열 사용모든 정점을 순회하며, 최소 거리를 갱신시간복잡도시간복잡도는 O(V ^ 2)이다.코드파이썬 코드im.. 공감수 1 댓글수 0 2024. 12. 26.
Baekjoon 17143. 낚시왕 / Python 17143. 낚시왕난이도 : 골드 1소요 시간 : 50분날짜 : 2024.12.26언어 : 파이썬알고리즘 유형 : 구현, 시뮬레이션설명 보기전에 문제 풀어보러 가기1. 문제 설명낚시왕이 오른쪽으로 한 칸 이동한다.낚시왕이 있는 열에 있는 상어 중 제일 가까운 상어를 잡는다.잡힌 상어는 사라진다.상어가 이동한다.상어진 주어진 속도로 이동하고, 경계와 만나면 방향을 반대방향으로 바꾸어 이동한다.방향이 바뀌어도 속력은 유지한다.상어가 이동을 마친 후에, 한 칸에 상어가 두 마리 이상 있다면, 크기가 큰 상어가 작은 상어를 모두 잡아먹는다.낚시왕이 잡은 상어의 크기의 합을 구한다.2. 해결 방식입력격자판의 크기 R, C, 상어의 수 MM개의 줄에 입력상어의 위치 r,c, 속력 s, 이동방향 d, 크기 z해결상어.. 공감수 1 댓글수 0 2024. 12. 26.
Baekjoon 1766. 문제집 / Python 1766. 문제집난이도 : 골드 2소요 시간 : 20분날짜 : 2024.12.26언어 : 파이썬알고리즘 유형 : 위상정렬, 방향 비순환 그래프, 우선순위 큐, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명n개의 문제를 모두 풀어야 한다.문제 번호가 낮으면 더 쉬운 문제이다.쉬운 문제를 먼저 풀어야 한다.먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.2. 해결 방식위상정렬과 우선순위큐를 활용하여 해결한다.먼저 해결해야하는 문제가 주어졌다 == 위상정렬쉬운문제(번호가 낮은 문제)를 먼저 풀어야 한다 == 우선순위 큐그냥 큐를 사용해서 푸는 위상정렬 문제에서 큐를 우선순위 큐로 바꾸면 해결된다.문제 번호 낮은게 먼저 풀어야 하기 때문에, 그냥 우선순위 .. 공감수 0 댓글수 0 2024. 12. 26.
Baekjoon 1509. 팰린드롬 분할 / Python 1509. 팰린드롬 분할난이도 : 골드 1소요 시간 : 40분날짜 : 2024.12.25언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명문자열이 주어진다 (길이 문자열을 팰린드롬으로 분할한다.분할 개수의 최솟값을 구한다.2. 해결 방식dp를 두개 활용했다.팰린드롬 dp : dp_pldm[i][j] = i인덱스부터 j인덱스까지 팰린드롬인가?의 여부길이 1, 길이 2인 팰린드롬을 먼저 저장한다.길이 3이상인 경우 dp 알고리즘을 활용한다. -> 시작, 끝이 같고, 내부가 팰린드롬이면 팰린드롬이렇게 하면 모든 경우의 수를 찾을 수 있음.분할수 dp : dp_res[i] = 0번 부터 i번 까지 팰린드롬 최소 분할 수dp값을 모두 0으로 해준다.끝점(j)의 인덱스를 0부터 문자.. 공감수 0 댓글수 0 2024. 12. 25.

문의안내

티스토리
로그인
고객센터

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