본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 5676번 : 음주 코딩 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net segent tree를 이용해 구간곱을 O(logN)만에 구하는 문제였습니다. 📕 풀이방법 n이 10^5고 모든 원소가 범위의 최대인 100이라면 100^(10^5)이므로 단순 정수 자료형들로는 해결할 수 없습니다. 다행히 출력해야하는 것이 부호 또는 0이기 때문에 적절히 치환해준다면 범위 초과를 넘길 수 있습니다. 📔 입력 및 초기화 1. n만큼 원소를 vector 변수 v에 입력 받습니다...
(C++) - 백준(BOJ) 15661번 : 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net backtracking을 이용한 brute force였습니다. 📕 풀이방법 최대 20명입니다. 팀은 두 개로 나뉘므로 한쪽의 인원이 정해진다면 나머지는 자동으로 정해집니다. 따라서 20C1 ~ 20C10로 팀을 뽑아서 능력치를 확인하면 됩니다. 20C10는 184756이므로 시간제한 2억안에 수행가능합니다. 📔 입력 및 초기화 각 인원의 능력치 정보를 ..
(C++) - 백준(BOJ) 18428번 : 감시피하기 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net backtracking 이용한 brute force 문제였습니다. 📕 풀이방법 n과 m의 응용문제였습니다. 📔 입력 및 초기화 board라는 2차원 배열 변수에 적절히 입력받습니다. 입력 도중 'T', 'X', 'S'가 나온 곳의 행,열 좌표를 각자 다른 vector 변수에 저장합니다. 📔 풀이과정 1. dfs를 수행합니다. 3개의 장애물을 조합의 형태로 board를 바꿔줍니다. 순서 상..
(C++) - 백준(BOJ) 12518번 : Centauri Prime (Small2) https://www.acmicpc.net/problem/12518 12518번: Centauri Prime (Small2) Back in the old days before the creation of the mighty Centauri Republic, the planet Centauri Prime was split into several independent kingdoms. The kingdom of Mollaristan was ruled by king Loatold, while the kingdom of Auritania was under the rule of quee www.acmicpc.net 문자열 다루는 문제였습니다. * 나라이름이 최대 100글자이므로 1글자인 나라의 경우 대문자이자 마..
(C++) - 백준(BOJ) 12517번 : Centauri Prime (Small1) https://www.acmicpc.net/problem/12517 12517번: Centauri Prime (Small1) Back in the old days before the creation of the mighty Centauri Republic, the planet Centauri Prime was split into several independent kingdoms. The kingdom of Mollaristan was ruled by king Loatold, while the kingdom of Auritania was under the rule of quee www.acmicpc.net 단순 string 문제였습니다. * a 유무 조심 📕 Code #include using names..
(C++) - 백준(BOJ) 9328번 : 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 구현 + bfs문제였습니다. 📕 풀이방법 빌딩 끝에서 열쇠를 찾아 출발지점으로 돌아가 문을 열 수도 있습니다. 이 말은 왔다갔다 이동하면서 한 공간을 여러번 방문할 수 있다는 말입니다. 언제 훔친 문서를 갱신해야 하는지, 시점을 찾는 것이 중요합니다. 📔 입력 및 초기화 매 테스트 케이스마다 적절히 초기화 후 입력받습니다. 빌딩 정보를 입력 받은 후에는 열쇠 정보를 담고 있는 문자열을 입력받습니다. 이 문자열..
(C++) - 백준(BOJ) 11505번 : 구간 곱 구하기 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 기존 구간합을 구하는데 이용하는 segment tree를 약간 응용한 문제였습니다 📕 풀이방법 📔 입력 및 초기화 n까지 수들을 입력받습니다. 이후 각 구간곱들을 tree라는 long long형 배열에 저장합니다. 📔 풀이과정 1. a = 1일 때 : b-1이 가르키는 부분을 c로 갱신하며 구간곱들을 새로 바뀐 c에 맞춰 갱신 해줘야합..
(C++) - 백준(BOJ) 11608번 : Complexity https://www.acmicpc.net/problem/11608 11608번: Complexity Print, on a single line, the minimum number of times you need to use the eraser. www.acmicpc.net greedy문제였습니다. 📕 풀이방법 '최소'로 문자들을 지움으로써 알파벳의 종류가 2개 이하가 되게 하려면 말 그대로 빈도수가 많은 2종류를 제외한 나머지를 지우면 됩니다. 📔 입력 및 초기화 입력을 받습니다. 입력받은 문자열에 대해 나온 알파벳의 개수를 세줍니다. 📔 풀이과정 1. 나오지 않은 알파벳은 제외하고 나온 알파벳들의 빈도 수를 vector변수에 저장합니다. 그러면서 나온 알파벳의 종류 또한 세주어 변수 cnt에 저장합니..

티스토리툴바