본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 11562번 : 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 와샬 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n,m,k 입력후 m만큼 u,v정점을 입력받은 것을 토대로 인접 그래프 adj를 형성해줍니다. 인접그래프의 초기값은 INF이며 갈 수 없는 경로는 1 갈 수 있다면 0으로 만들어줍니다. 📔 풀이과정 기존에 갈 수 있는 곳이라면 비용이 들지 않으나 인접해있지만 갈 수 없는 길을 가려면 길을 만들어줘야 하므로 1의 비용이 든다고 생각할 수..
(C++) - 백준(BOJ) 2417번 : 정수 제곱근 https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 풀이과정 mid에 제곱을 한다면 long long범위를 초과할 수 있습니다. overflow발생을 막기 위해 num에 루트를 씌웁니다. sqrt(num)이상이 되는 mid를 찾는 것으로 해결할 수 있습니다. 이 mid는 이분탐색을 시행해 찾습니다. 📕 Code #include using namespace std; using ll = long long; ll num; ll binarySearch(){ ll l = 0; ll r = sqrt(num); while(l > num; c..
(C++) - 백준(BOJ) 14627번 : 파닭파닭 https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파 www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 s : 파의 개수 c : 주문된 파닭 수 ans : 정답(라면에 넣을 파의 양) greenOnion : 파의양을 입력받을 일차원 배열을 선언합니다. 📔 풀이과정 파닭에 넣을 파의 양을 mid로 두어 이분탐색을 시행합니다. 1. mid는 0 ~ s까지의 모든 i에 대해 greenOnion[i] / mid의 ..
(C++) - 백준(BOJ) 14676번 : 영우는 사기꾼? https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 위상정렬 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 일차원 배열 선언 : 건설여부를 저장할 buildCheck 진입차수를 저장할 indegree를 선언합니다. 입력받은 정보를 토대로 단방향 인접리스트 그래프 graph를 생성합니다 그리고 진입차수를 저장합니다. 치트를 썻는지의 여부 bool형 변수 isCheat를 선언합니다. 📔 풀이과정 x를 건설할 경우 x가 ..
(C++) - 백준(BOJ) 16206번 : 롤케이크 https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 개인적으로 어려웠던 분할 정복 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n만큼 롤케이크의 길이를 입력시 10으로 나눠떨어지는것은 ten에, 아닌 것은 notTen에 push_back했습니다. 📔 풀이과정 여러 경우를 나누어 생각해볼 수 있습니다. 1. 롤케이크 길이가 10인경우 : 자를 필요가 없습니다. ans를 더해줍니다. 2. 롤케이크 길이가 10보다 작은경우 : 이 또한 자..
(C++) - 백준(BOJ) 10546번 : 배부른 마라토너 https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net map을 이용하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 이름을 key, 이름이 나온 빈도 수를 value로 한 map변수 m을 선언한 뒤 n만큼 이름을 입력받을 때마다 해당하는 key의 value값을 1씩 증가시켜줍니다. 📔 풀이과정 1. n-1만큼 입력받으면서 해당 이름의 빈도수를 1씩 감소시켜줍니다. 2. 모두 입력 받은 뒤 m의 size만큼 loop를 돌면서 빈도수가 0이아..
(C++) - 백준(BOJ) 15486번 : 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp 문제였습니다. 📕 풀이방법 수행 시간이 n이 150만이므로 O(n)에 수행해야 합니다. 제한사항이 영향을 끼치지 않기 때문에 본질적으로 퇴사문제와 풀이 방법이 같습니다. 제 풀이는 해당 문제에 대한 설명을 포스팅 한 글로 대체합니다. https://codecollector.tistory.com/1113 (C++) - 백준(BOJ) 14501번 : 퇴사 https..
(C++) - 백준(BOJ) 15927번 : 회문은 회문아니야!! https://www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 문자열 다루는 문제였습니다. 📕 풀이방법 너무 깊게 생각하면 안됩니다. 약간의 직관이 필요합니다. 📔 입력 및 초기화 string 형 변수 s에 문자열을 입력받습니다. 📔 풀이과정 1. 모든 문자가 같다면 -1이 답입니다. 2. 모두 같은 문자인 것을 제외한 모든 펠린드롬은 양 옆에 있는 문자중 하나의 문자를 제거하면 펠린드롬이 아니게 됩니다. 따라서 펠린드롬인..

티스토리툴바