SW

0. 제목 백준 11053 가장 긴 증가하는 부분 수열 BOJ 11053 가장 긴 증가하는 부분 수열 파이썬 11053 가장 긴 증가하는 부분 수열 Python 11053 가장 긴 증가하는 부분 수열 1. 문제 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 dp[i] : i 번째 원소까지의 가장 긴 증가하는 부분 수열의 길이 가장 먼저 dp의 원소들을 1로 초기화 시켜..

0. 제목 백준 12865 평범한 배낭 BOJ 12865 평범한 배낭 파이썬 12865 평범한 배낭 Python 12865 평범한 배낭 1. 문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 dp[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치 각 물품의 번호 i에 따라서 dp[i][j]를 갱신한다. 1부터 k까지 증가하는 변수 j가 입력된 무게보다..

0. 제목 백준 1325 효율적인 해킹 BOJ 1325 효율적인 해킹 파이썬 1325 효율적인 해킹 Python 1325 효율적인 해킹 1. 문제 www.acmicpc.net/problem/1325 max_value: result = [i] max_value = c elif c == max_value: result.append(i) max_value = c for e in result: print(e, end=" ")

0. 제목 백준 1012 유기농 배추 BOJ 1012 유기농 배추 파이썬 1012 유기농 배추 Python 1012 유기농 배추 1. 문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 2. 풀이 2차원 배열 형태의 문제에서 좌표 입력을 받을 때 (x, y)를 arr[y][x] 로 표현하는 것을 항상 생각하며 푼다. 파이썬에서 setrecursionlimit으로 재귀 허용 깊이를 늘려주지 않으면 런타임 오류가 뜨는 경우가 있어, 재귀 허용 깊이를 수동으로 늘려주는 ..

0. 제목 백준 2606 바이러스 BOJ 2606 바이러스 파이썬 2606 바이러스 Python 2606 바이러스 1. 문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 2. 풀이 adj라는 2차원 배열 형태를 선언한 후, 각 점의 연결 상태를 표시한다. adj[2] = [1, 3, 4] 라면 2번에 1번, 3번, 4번이 연결되어 있다는 것이다. visited라는 1차원 배열을 선언한 후, 각 점에 대한 방문 여부를 표시한다. visited[3] = Tru..

0. 제목 백준 1697 숨바꼭질 BOJ 1697 숨바꼭질 파이썬 1697 숨바꼭질 Python 1697 숨바꼭질 1. 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 2. 풀이 현재 위치가 N이라고 할 때 이동가능한 지점은 N + 1, N - 1, 2*N 이다. 가장 빠른 시간을 찾기위해 bfs를 사용한다. 가장 먼저 현재 위치 좌표를 deque(덱, 큐의 앞과 뒤에서 삽입과 삭제가 가능한 큐)에 넣는다...

0. 제목 백준 1260 DFS와 BFS BOJ 1260 DFS와 BFS Python 1260 DFS와 BFS 1. 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 풀이 dfs의 경우 인접한 정점들을 차례로 탐색할 수 있도록 재귀를 사용한다. bfs의 경우 deque를 사용한다. 탐색을 마치면 pop을 하고 인접한 정점 중 방문하지 않았던 점은 append로 deque에 추가해줌으로써 deque가..

0. 제목 백준 2110 공유기 설치 BOJ 2110 공유기 설치 Python 2110 공유기 설치 1. 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 2. 풀이 이진탐색을 사용하는 문제이다. 두 공유기 사이 거리의 최대값과 최소값을 가장 먼저 구하고 중간값을 구해가며 정답을 구한다. 중간값을 구할 때마다 설치 가능한 공유기 개수를 구한다. 설치 가능한 공유기 개수와 입력받은 공유기..

0. 제목 백준 1874 스택 수열 BOJ 1874 스택 수열 Python 1874 스택 수열 1. 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 풀이 스택에 원소를 삽입할 때는, 단순히 특정 수에 도달할 때까지 삽입하면 된다. 스택에서 원소를 연달아 빼낼 때 내림차순을 유지할 수 있는지 확인한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11..

0. 제목 백준 1302 베스트 셀러 BOJ 1302 베스트 셀러 Python 1302 베스트 셀러 1. 문제 https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 2. 풀이 등장 횟수를 계산할 때는 Dictionary 자료형을 이용하면 효과적이다. books라는 Dictionary를 선언하고, book을 입력 갯수만큼 입력받는다. 입력받으면서 딕셔너리에 저장하고 갯수를 1 증가시킨다. Dictionary에 이미 있는 이름이면 1 증가시켜주고..