BAEKJOON

[BOJ] 1012 - 유기농 배추 (C++)

1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제에서는 밭의 가로, 세로 크기와 심어진 배추의 개수, 각 배추의 위치가 주어진다. 이때 배추들을 건강하게 키우기 위한 최소 배추흰지렁이 개수를 구하면 되는 문제이다. 2. 해결 아이디어 dfs, bfs 등을 이용하여 쉽게 해결할 수 있는 문제이다. 다만 이번 문제를 해결하면서 작은 문제를 마주쳐 그것에 대해 기록하려고 글을 쓴다... 3. 개선할 점 코드에서 전역으로 밭(field), visit..

[Baekjoon] 2479 - 경로 찾기 (C++)

1. 문제 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다. 우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다. A=000 B=111 C=010 D=110 E=001 두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다. 우리는 이진 코드들에..

[Baekjoon] 1167 - 트리의 지름(C++)

1. 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 2. 해결 아이디어 1) 각 노드마다 갈 수 있는 최대 cost를 2개까지 저장한 뒤(재귀 방식이라 시간 복잡도 O(n)), 모든 노드의 최대 cost값 2개의 합을 비교하면서 가장 큰 최대 cost의 합을 출력한다. (= 트리의 지름) 한 노드에..

[Baekjoon] 1019 책 페이지 - C++

> 문제 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. > 풀이 문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에 n 0은 100~109, 200~209, .., 54200~542..

[Baekjoon] 3273 - 두 수의 합 (C++)

> 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 풀이 idea 1) m..

[Baekjoon] 2156 - 포도주 시식 / C++

> 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효..

[Baekjoon] 21921 블로그 - C++

> 문제 문제 링크 : https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라. > 풀이들 첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*..

[Baekjoon] 9461 파도반 수열, 10844 계단 수, 1924 2007년

백준 9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선을 따라 가며 n번째의 삼각형의 변의 길이를 찾는 문제이다. 삼각형의 변의 길이는 이전 삼각형과 5번째 전 삼각형의 변의 길이를 더한 것과 같다는 점을 이용해 문제를 해결할 수 있다. 정삼각형의 한 각의 크기는 60도이므로, 이 점을 이용해 5번째 전의 삼각형을 추론할 수도 있을 것이다. 코드는 다음과 같다. t = int(input()) for i in range(t):..

[Baekjoon] 9663_N-Queen #3

N - Queen 문제 중 한 종류인 8-Queen 문제이다. N - Queen 문제는 결국 n을 입력받아 n * n 사이즈 보드 안에 n개의 퀸을 겹치지 않고 배열할 수 있는 경우의 수가 얼마나 되는지를 세는 알고리즘이다. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예시 입력과 출력은 다음과 같다. 이외에도 표로 나머지 경우를 정리하면 다음과 같다. n 1 2 3 4 5 6 7 8 경우의 수 1 0 0 2 10 4 40 92 이외에도 9..

[Baekjoon] 7576 토마토

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 ..

[Algorithm] Dynamic Programming에 관해

소마 13기 코테를 준비하며, dp문제를 많이 풀 기회를 접하였다. 그래봤자 난이도가 실버급에 있는 문제들이긴 하지만, 그래도 일단 내가 풀면서 느낀 점들을 정리하려 한다. 먼저 DP, Dynamic Programming은 문제풀이 알고리즘의 한 종류로, DFS나 그리디, 백트래킹과는 또다른 성격의 문제풀이법이다. 풀면서 수학적 귀납법과 비슷하다는 느낌을 받았다. 먼저, 속도에 관해 말해 보자면 DFS는 시간이 엄청 걸리고, 백트래킹은 그걸 조금 줄여주지만 DP는 확실히 줄여 주는 것을 느꼈다. 여기서 한 가지 느낀 점은 "DP는 시간과 공간을 trade해서 효율성을 올린 알고리즘" 이다. DP문제를 풀다 보면 점화식 형태의 풀이법이 많다. 대부분 배열이나 리스트를 이용하여 점화식을 세워 문제를 푸는데,..

[Python] 스도쿠 풀이 프로그램 #3

저번 글에 이어 이 글에서는 어려운 스도쿠를 풀 수 있는 프로그램을 설명한다. 백트래킹을 이용해 이를 구현했고, 생각보다 정말 간단하게 구현이 되었다. 먼저 사용된 함수는 다음과 같다. def possibilities(i, j): global sudoku exist = [] for k in range(9): if sudoku[k][j] != 0: exist.append(sudoku[k][j]) if sudoku[i][k] != 0: exist.append(sudoku[i][k]) if sudoku[i//3*3 + k//3][j//3*3 + k%3] != 0: exist.append(sudoku[i//3*3 + k//3][j//3*3 + k%3]) unexist = [i for i in range(1, 1..

[Baekjoon] 9663_N-Queen #1

출처 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 먼저 이 문제를 해결하기 위해 필자는 이전 문제에서 배웠던 구조를 가져왔다. 함수 안에 반복문을 ..