Algorithm/백준 문제풀이

[백준] 12865번: 평범한 배낭 - 파이썬(Python)

https://www.acmicpc.net/problem/12865 해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다.  1. 문제 입력 & 목표해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다. 문제 입력 N: 물품의 수 (1 ≤ N ≤ 100)K: 버틸 수 있는 최대 무게 (1 ≤ K ≤ 100,000)w,v : 물건의 무게, 물건의 가치 (1 ≤ W ≤ 100,000 / 0 ≤ V ≤ 1,000)  문제 목표배낭이 버틸 수 있는 최대 무게인 K가 넘지 않는 선에서, 담을 수 있는 물건의 최대 가치를 구해라  2. 접근 방식문제의 첫 번째 예제를 시각화하면 다음과 같습니다.  편의상 물건의 인덱스를 1부터 시작한다고 할 때,왼쪽의 배열은 i번째 물건의 무게(w), 가치(v)이며, 오른쪽은 최대 배낭이..

[Python] BOJ 9663. N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net NxN 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력하는 문제로 N=4일때를 예시로 들면 다음과 같이 설명할 수 있다 4x4 체스판에 퀸 4개가 아래와 같이 있다 상태 공간 트리(State-Space Tree)로 1~4번 퀸의 위치를 표현할 수 있다 아래는 4개의 퀸들이 서로 공격할 수 없게 놓은 경우의 수 중 하나로, 상태 공간 트리로 표현했을 때는 다음과 같은 경로를 거치게 된다 - 퀸은 현..

[Python] BOJ 1300. k번째 수

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 예제 해석 A : 3x3 1 2 3 1 1 2 3 2 2 4 6 3 3 6 9 B : len(B) = 9 = 3x3 1 2 2 3 3 4 6 6 9 출력값 : B[7] = 6 - 임의의 숫자 m을 골라서 k번째 숫자인지 판단해보는 문제 - m을 이분 탐색으로 찾아보자 : m은 O(logK) - m보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있는가 - A[i][j]에서..

[C++] BOJ 1051. 숫자 정사각형

www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net #include #include #include #include using namespace std; int n,m; int rec[51][51]; vector square; vector column; vector tmp_square; int check_square(int start_row, int start_column);// 인덱스 별 가장 큰 정사각형 사이즈를 리턴해주는 함수 int main(void)..

[C++] BOJ 4386. 별자리 만들기

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일� www.acmicpc.net 크루스칼 알고리즘 이론 참고 codingsmu.tistory.com/11?category=871718 [Algorithm: 알고리즘] 05 Greedy Algorithm 목차 0. Basics: 그리디 알고리즘 기초 1. Minimum Spanning Trees : 최소 신장 트리 - 신장 트리 - 최소 비용 신장 트리 - Kruskal's Algorithm( Original ver.) : 크루스칼 알고리즘 -..

[C++] BOJ 7576. 토마토

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제 설명 : 예제가 아래와 같이 들어온다면 아래의 토마토 일 수 변화과정으로 6일이 결과값으로 도출됨을 확인할 수 있다 #include #include #include #include using namespace std; int dy[4] = {0,0,1,-1}; int dx[4] = {1,-1,0,0,}; int n,m; int box[1000][1000]; queue start_point..

[Kotlin] BOJ 7785. 회사에 있는 사람

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성 www.acmicpc.net