Baekjoon Online Judge
[BOJ] 28303: 자석 (C++)
https://www.acmicpc.net/problem/28303 28303번: 자석 예제 1의 경우 N극이 3번 칸에 놓이고 S극이 5번 칸에 놓이도록 자석을 설치할 때 1번 현상으로 $a_3=22$의 에너지가 충전되며, 2번 현상으로 $a_5=4$의 에너지가 소모되고, 3번 현상으로 $(5-3)\times 2=4$ www.acmicpc.net 걸린 시간 : 49분 11초 UCPC 2023 예선 문제다. 문제가 이상한 말을 많이 하지만 돌려돌려 생각해보면 문제 자체는 이해하기 쉽다. a[i] - a[j] - abs(i-j) * K 값을 구하라는 것이다. 단순히 생각해 봤을 때, 변수가 i, j 이므로 단순히 탐색을 한다면 O(N^2) 일 것이다. 하지만 N의 범위가 500000이다. 보통 몇천 단위를..
[BOJ] 1780 : 종이의 개수 (C++) with 분할 정복
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 걸린 시간 : 13분 10초 기본적인 분할 정복 문제이다. 분할 정복 문제는 어떤 알고리즘인지 알아차리기는 너무 쉽다. 분할정복은 누가 봐도 분할 정복이다. (어려운 분할 정복 문제들은 분할 정복만 쓰인 게 아니고 다른 알고리즘까지 쓰인 것 같다... 세그먼트 트리 같은) 키 포인트는 일반항 설정이다. 기본적으로 재귀함수를 통해 base case까지 모두 커버할 수 있는 함수를 만들어야..
[BOJ] 1874 : 스택 수열 (C++) with 스택
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 걸린 시간 : 30분 42초 if 문 안에 while 문을 중첩시키려고 해서 많은 오류를 겪었다. 처음부터 코드를 치려고 하지 말고 생각이 정리된 상태로 코드를 쳐야겠다. 알고리즘은 간단하다. 수를 입력받고, 2가지 행동 중 하나를 하면 된다. 만약 현재 수 (num) 보다 크다면 스택에 그때까지 계속 push 하면..
[BOJ] 1912: 연속합 (C++) with 누적합
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 걸린 시간 : 39분 34초 이 문제는 어떤 알고리즘 유형인지 모르고 시작했다. 역시나 알고리즘 유형을 알아채는 게 제일 어렵다. 처음에 부분합과 투 포인터 알고리즘의 결합으로 시작했다가, 그냥 부분합으로 했다가, 다시 부분합과 투 포인터로 했다가 시간초과와 틀렸습니다가 떴다.... ㅠㅠ 결국 다 치워버리고 종이에 어떻게 해야할 지 차근차근 생각해보니 기본적인 다이나믹 프로그래밍으로 해결할 수 있었다. 요즘..
[BOJ] 2644: 촌수계산 (C++)
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 걸린 시간 : 24분 30초 기본적인 그래프 순회 문제이다. 그래프 문제가 직사각형으로 주어지면, 다시 말해서 정점 위주로 주어지면 바로 인접 행렬 방식으로 그래프를 구현한다. 하지만 이렇게 간선 위주로 주어진다면 인접 리스트 방식으로 구현하는 게 좋다. 다시 말해서 입력이 인접 행렬과 같이 주어지거나, V(정점 개수)가 너무 작거나, 플로이드 알고리즘을 사용할 경우 인접 행렬..
[BOJ] 4963 : 섬의 개수 (C++) with DFS
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 걸린 시간 : 11분 3초 가장 기본적인 dfs 혹은 bfs 문제였다. "간단한 경우에는" 큐를 써야하는 bfs와 달리 재귀를 사용하는 dfs가 구현이 더 편해 dfs로 구현한다. 하지만 알고리즘이 복잡해지거나 최단 경로를 구하는 등의 많은 경우에 bfs를 더 많이 쓰는 것 같다. 이 문제는 dfs로 풀었다. board를 탐색하면서 섬이 발견되면 카운트해준다. 그리고 연결된 섬을 지워주는 d..
[BOJ] 10799 : 쇠막대기 (C++)
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 걸린 시간 : 6분 18초 어렵지 않았고, 발상도 쉬웠다. 문자열에서 문자를 처리하면서 발생할 수 있는 경우만 처리해주면 됐다. 스택을 사용할 수도 있지만, 그냥 변수를 사용해도 충분하다. 문자가 ( 이면 현재 막대기의 수를 나타내는 barnum을 증가시킨다. 문자가 ) 이면 다음 둘 중 하나이다. 직전 문자가 ( 이면 레이저를 나타낸다. 현재 막대기의 수만큼 잘린 막대기가 생길 것이다. 단, () 자체가 ..
[BOJ] 14500 : 테트로미노 (JAVA) with DFS
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 풀이 이 조각들을 좌표에 배치시켜, 해당 좌표에 쓰인 숫자들의 합의 최댓값을 구하는 문제이다. 발상은 어렵지 않았다. DFS로 발생하는 모든 4칸의 경우의 수를 세면 되는 문제였다. 그렇게 간단하게 생각하고 풀어갔다. DFS 함수에 cnt 변수를 전달해주면서 cnt가 4가 되면 그 상황에서의 숫자들의 합을 하나의 경우의 수로 보았다. 그들 중 최댓값을 구하면 된다. 하지만 이렇게 하면 위의 ..
[BOJ] 1941: 소문난 칠공주 (C++) with 조합
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 풀이 14500번 테트로미노가 떠오르는 문제였다. https://morenow.tistory.com/22 [BOJ] 14500: 테트로미노 (JAVA) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도 more..
[BOJ] 2170 : 선 긋기 (C++)
https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 풀이 입력된 선들을 그었을 때 나오는 선의 총 길이를 구하는 문제이다. x와 y의 범위가 작을 때는, 다른 방법을 써도 될 것이다. 예를 들어, 범위만큼의 bool 형 배열을 선언하고, 선이 그어진 부분은 true로 표시하는 방법이 있다. 하지만, 이 경우에는 그러려면 배열의 크기가 20억이 되고, 선도 100만번이나 그을 수 있기 때문에 이 방법은 안 된다...