본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 21737번 : SMUPC 계산기 https://www.acmicpc.net/problem/21737 21737번: SMUPC 계산기 SMUPC를 기념하기 위해 ALGOS와 DSC Sookmyung에서는 SMUPC의 각 글자로 계산이 이루어지는 계산기를 만들었다. 가은이와 혜민이는 이 계산기와 같은 방식으로 작동하는 프로그램을 만들고자 한다. 가은 www.acmicpc.net 문자열 parsing 후 구현 문제였습니다. 풀이방법 1. 숫자는 숫자끼리, 계산명령어는 명령어끼리 parsing해 각각의 vector에 저장했습니다. 2. 명령어의 size만큼 확인하면서 계산을 수행합니다. Code #include using namespace std; using ll = long long; ll n, cFlag, output, idx; strin..
(C++) - 백준(BOJ) 21736번 : 헌내기는 친구가 필요해 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net bfs문제였습니다. 풀이방법 어떤식으로 풀었는지 알고리즘 작성 1. 도연이가 한 명임이 보장되므로 입력시 'I'가 나온다면 해당 행,열 좌표를 저장합니다. 2. 도연이의 위치를 출발점으로 bfs를 수행, 한 영역에서 P의 개수를 반환합니다. Code #include using namespace std; using pii = pair; int n,m, startRow, startCol,..
(C++) - 백준(BOJ) 21734번 : SMUPC의 등장 https://www.acmicpc.net/problem/21734 21734번: SMUPC의 등장 2021년 5월 8일 SMUPC 대회의 첫 개최에 신이 난 화은이는 SMUPC를 기념하기 위해 "SMUPC"를 예술적으로 출력하는 프로그램을 작성하고자 했다. 화은이는 각 알파벳에 해당하는 아스키코드 값을 10진 www.acmicpc.net 아스키 코드를 이용해보는 문자열 문제였습니다. Code #include using namespace std; string s; int getSum(int ascii){ int tmp = ascii; int sum = 0; while(tmp){ sum += tmp%10; tmp /= 10; } return sum; } int main(){ cin >> s; for(int..
(C++) - 백준(BOJ) 21735번 : 눈덩이 굴리기 https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 백트래킹 문제였습니다. 풀이방법 1. idx번째 눈덩이를 골랐을 때 대회시간과 고르기 직전의 size를 dfs함수의 인자로 설정합니다. 2. idx번째 위치에서 다음 위치는 idx+1 또는 idx+2이므로 max(idx + 1, cnt + 1, size + idx+1번째 눈덩이 크기, idx + 2, cnt + 1, size + idx+2번째 눈덩이 크기)가 idx번째 위치에서..
(C++) - 프로그래머스(2017 카카오코드 예선) : 보행자 천국 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr dp문제였습니다. 풀이방법 1. 0,0에서 출발해서 현재좌표 (i, j)에 따라 다음 행선지를 정합니다. 2. 현재 표지판이 0이라면 우측 또는 아래로 갈 수 있습니다. 현재 표지판이 1이라면 더 이상 갈 수 없으므로 0을 반환합니다. 현재 표지판이 2고 이전 방향이 오른쪽(dir == 1)이라면 오른쪽으로만 갈 수 있고 아래쪽이라면(dir == 2) 아..
(C++) - 백준(BOJ) 1837번 : 암호제작 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 큰 수와 소수를 다루는 문제였습니다. 풀이방법 1. 2 ~ 100만까지의 소수를 prime배열 변수에 저장합니다. 2. 2 ~ k까지의 소수들 중 하나를 골라 p의 약수인지를 확인합니다. 입력받은 p의 경우에는 수의 범위를 초과하므로 string으로 입력받습니다. p의 첫번째 자리부터 하나씩 자리수를 붙여가며 확인합니다. 해당 수가 i에 나누어 떨어지는지 확인합니다. 3. 모든 자리수에 대해 자리..
(C++) - 백준(BOJ) 14923번 : 미로탈출 https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net bfs문제였습니다. 풀이방법 벽 부수고 이동하기와 같은 문제였습니다. 1. bfs를 수행할 때 거리를 벽을 이미 부쉈을 때의 거리와 벽을 부수지 않았을 때의 거리를 구합니다. dist[x][y][w]로 각 상태에 따른 거리를 구할 수 있습니다. x행 ,y열의 벽의 상태 w에 대한 거리가 저장됩니다. w가 0일 때는 벽을 부수지 않은 상태, w가 1일 때는 벽을 부순상태가 됩니다...
(C++) - 백준(BOJ) 14728번 : 벼락치기 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net dp문제였습니다. 풀이방법 1. d[i][j] = i시간동안 n번 챕터를 풀었을 때 얻을 수 있는 점수의 최댓값입니다. 2. 점화식으로 나타내면 d[i][j] = 점수max(현재 챕터를 골랐을 때, 현재 챕터를 고르지 않았을 때) 입니다. 현재 챕터를 고르게 되면 현재 점수를 고른뒤 공부하는데 걸리는 시간을 빼주게 됩니다. 남은시간이 음수가 된다면 해당..

티스토리툴바