본문 바로가기

분류 전체보기

 (147)
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에 해당하는 단어를 넣는 함수 호출, 안넣는 함수 호출..
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..
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..
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..
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를 기준으로 왼쪽 오른쪽을 합치는 것들의..
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가 나머지..
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..
Baekjoon 1406. 에디터 / Python 1406. 에디터난이도 : 실버 2소요 시간 : 40분날짜 : 2025.01.08언어 : 파이썬알고리즘 유형 : 연결리스트, 스택설명 보기전에 문제 풀어보러 가기1. 문제 설명주어진 문자를 주어진 명령에 따라 실행한 뒤, 마지막 남은 문자열을 출력한다.명령어는 커서를 기준으로 시작하고, 시작할 때의 커서는 맨 뒤이다.L : 커서를 왼쪽으로 한 칸 (커서가 맨 앞이면 무시)D : 커서를 오른쪽으로 한 칸 (커서가 맨 뒤이면 무시)B : 커서 왼쪽 문자를 삭제 (커서가 맨 앞이면 무시)P # : 커서 왼쪽에 # 이라는 문자 추가2. 해결 방식연결리스트 연습을 위해 고른 문제인 만큼 연결리스트를 활용해서 풀이했다.(리스트에 insert를 하는 방법도 통과되는 듯....)연결리스트 기본 구조Node : data..
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..
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] : 가만히 있을 확률 *..

티스토리툴바