티스토리

크롱의 Dev Log

검색하기

블로그 홈

크롱의 Dev Log

crong-dev.tistory.com/m

이것저것 해보고 싶은 크롱의 개발 블로그

구독자: 18

방명록 방문하기

주요 글 목록

백준 1016: 제곱 ㄴㄴ수 (C++) 문제 링크: www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 풀이 방법 [min, max] 구간의 최대 원소 개수는 1000001이므로 bool arr[1000001]을 선언하고 여기에 min~max구간의 수가 제곱ㄴㄴ수인지 아닌지 저장해줬다. arr[0]: min이 제곱ㄴㄴ수인지, arr[1]: min + 1이 제곱ㄴㄴ수인지 ... 일단 모두 제곱ㄴㄴ수라고 가정하고 시작한다. (memset을 통해 모두 true로 초기화한다.) 그다음 2부터.. 공감수 0 댓글수 2 2021. 1. 24.
백준 2213: 트리의 독립집합 (C++) 문제 링크: www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 새로 알게 된 것 int& result = cache[stage][idx]; 는 cache[stage][idx]라는 변수에 result 라는 별명을 붙여주는 개념.(같은 주소를 참조함) 즉, 두 개는 이름만 다르지 같은 변수이다. result의 값을 변경하면 cache[stage][idx]의 값도 같이 바뀐다. 소스 코드 #include #include #includ.. 공감수 1 댓글수 1 2020. 12. 30.
백준 2146: 다리 만들기 (C++) 문제 링크: www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net #include #include #include #include #include #define MAX 100 #define INF 10000 using namespace std; int n, islandNum, answer; int map[MAX][MAX]; // 입력 받아 지도 값 저장(0:바다/1:육지) >> 이후 섬 번호 붙여줌 bool visit[MAX][MAX]; // BFS탐색 시, 방문 여부.. 공감수 0 댓글수 0 2020. 11. 25.
백준 2098: 외판원 순회 (C++) 문제 링크: www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 방법 int W[16][16]; //도시 i에서 j로 가기 위한 비용(갈 수 없는 경우는 0) int dp[16][1 공감수 0 댓글수 0 2020. 11. 25.
백준 1662: 압축 (C++) 문제 링크: www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net #include #include #include using namespace std; string s; int visited[50]; int ans; //바깥쪽에서 안쪽으로 계산해 나감 int calc(int start, int end) { int result = 0; for (int i = start; i < end; i++) { if (s[i] == '(') { int k = s[i - 1.. 공감수 0 댓글수 0 2020. 11. 25.
백준 1463: 1로 만들기 (C++) 문제 링크: www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2~1000000까지 1로 만드는 최소 연산 횟수를 먼저 계산한다. 작은 수에 대해서 먼저 계산하고 그 값을 저장해 재활용함으로써 불필요한 연산을 줄일 수 있다. #include #include using namespace std; #define MAX 1000001 int arr[MAX]; //1로 만드는 연산 횟수 저장 void count() { for (int i = 2; i 공감수 0 댓글수 0 2020. 11. 25.
백준 1398: 동전 문제 (C++) 문제 링크: www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 화폐단위가 100씩 곱한 값으로 끊어진다는 것을 캐치하면 쉽게 풀리는 문제이다. 현재 지불해야하는 금액 중 100으로 나눈 나머지는 어차피 100 이하의 금액인 동전(1, 10, 25)로만 지불할 수 밖에 없다. 따라서 1~99 금액에 대한 필요한 동전 개수를 계산해 dp.. 공감수 0 댓글수 0 2020. 11. 25.
백준 1918: 후위 표기식 (C++) 문제 링크: www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 후위 표기식과 후위 표기식 변환 알고리즘에 대한 자세한 설명은 아래 포스트에서 확인할 수 있다. 후위 표기식과 변환 알고리즘에 대한 자세한 설명 후위 표기식 변환 및 계산 알고리즘 수식 표기 방법 수식 표기 방법에는 전위, 중위, 후위 표기법이 있다. 우리가 일반적으로 사용하는 표기법은 중위 표기법이다. 중위 표기법: 연산자가 피연산자 가운데 위치. 전위 표기법: 연산 crong-dev.t.. 공감수 0 댓글수 0 2020. 11. 22.
백준 4949: 균형잡힌 세상 (C++) 문제 링크: www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 스택을 활용한 문제이다. 여는 괄호가 나왔을 때 스택에 넣어주고, 닫는 괄호가 나왔을 때 스택의 top(제일 최근에 들어간 여는 괄호)와 짝이 맞는지 확인한다. 짝이 맞지 않으면 flag를 false로 바꾸고 반복문을 탈출한다. 짝이 맞지 않는 경우가 없었어도 마지막에 여는 괄호만 나오고 닫는 괄호가 나오지 않았으면 올바른 문자열이 아니다. 이 경우 스택에 원소가 남아있다. flag가.. 공감수 0 댓글수 0 2020. 11. 21.
백준 2164: 카드2 (C++) 문제 링크: www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 코드 설명은 주석 처리함. #include #include using namespace std; int main() { int n; queue q; scanf("%d", &n); // 1~n번 카드를 큐에 넣어준다 for (int i = 1; i 1) { // 제일 위에 있는 카드.. 공감수 0 댓글수 0 2020. 11. 21.
백준 1966: 프린터 큐 (C++) 문제 링크: www.acmicpc.net/problem/1966 1966번: 프린터 큐 첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음 www.acmicpc.net 큐와 우선순위 큐를 활용해 해결하는 문제다. 입력받을 때 큐에 {문서의 순서, 중요도}를 pair를 활용해 저장했고, 우선순위큐에 중요도를 넣어주었다. 이후 큐에 있는 모든 문서가 처리될 때까지 while문으로 반복한다. 맨 앞에 있는 문서를 꺼낸 다음(q.pop()) 해당 문서의 중요도가 남아있는 모든 문서 중 가장 높은 중요도와 일치하면(현재 문서의 중요도가 가장.. 공감수 0 댓글수 0 2020. 11. 21.
백준 10828: 스택 (C++) 문제 링크: www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net C++의 스택 STL을 사용해 문제를 해결했다. 아래 포스트 참고 : crong-dev.tistory.com/13 [자료구조] 스택(stack) / 백준 10828 (C++) 지난 포스트에서 스택에 대해 알아보았다. 이전 포스트: https://crong-dev.tistory.com/10 [자료구조] 스택(stack) / 백준 10828 (C) 스택이란? 삽입과 제거가 한쪽 끝에서.. 공감수 0 댓글수 0 2020. 11. 21.
백준(Baekjoon, BOJ) 온라인 저지에서 "컴파일 에러"가 뜨는 경우 백준에서 소스 코드 채점했을 때 컴파일 에러가 뜨는 경우가 있습니다. "컴파일 에러" 문구를 클릭하면 에러 로그를 보여줍니다. 컴파일 에러 문구를 클릭하면 아래와 같은 에러 로그를 볼 수 있습니다. 확인하시고 디버깅해보세요! 개인 IDE에서는 잘 돌아가는데 백준에서는 안 된다면? 1. 언어 설정을 잘못한 경우 제대로 언어 설정을 했는지 확인해보세요. 2. 제대로 import/include를 안 해준 경우 IDE에서는 명시적으로 import/include하지 않아도 알아서 해당하는 헤더 혹은 라이브러리 등을 찾아 사용하는 경우가 있습니다. 그럴 때는 아래와 같은 온라인 IDE에서 확인해봅시다. ideone.com/ Ideone.com Ideone is something more than a pastebin.. 공감수 0 댓글수 2 2020. 11. 19.
백준 10828: 스택 (C) 문제 링크: www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 소스 코드: #include #include #define MAX_STACK_SIZE 10000 int stack[MAX_STACK_SIZE]; // 스택 배열 int topIndex = -1; // 스택의 top의 인덱스 // push X: 정수 X를 스택에 넣는 연산이다. void push(int x) { stack[++topIndex] = x; } // pop: 스택에서 가장.. 공감수 0 댓글수 0 2020. 11. 19.
백준 1202: 보석 도둑 (C++) 문제 링크: www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 한번에 짠 아래 코드. 테스트케이스는 문제 없이 동작했는데 채점 돌리니까 7%에서 시간 초과 났다. 고민하다가 결국 우선순위 큐 써서 해결했다. #include #include #include #define MAX 300000 using namespace std; long long ans = 0; int n, k; pair jewelry[.. 공감수 0 댓글수 0 2020. 11. 19.
백준 1065: 한수 (C++) 문제 링크: www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 설명: 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 문제 접근 방법: N은 1000이하의 자연수이므로 init()함수를 통해 1~1000까지 한수인지 아닌지를 배열 hansoo에 저장해뒀다. ha.. 공감수 0 댓글수 0 2020. 11. 19.
백준 1003: 피보나치 함수 (C++) 문제 링크: www.acmicpc.net/problem/1003 피보나치 함수를 구현하는 여러 방법이(재귀 함수 등)있지만 기존의 값을 저장하지 않고 새로운 숫자의 피보나치 값을 구하려면 이전 값까지 계속 다시 연산해야 한다. 예를 들어, 새롭게 숫자 5의 피보나치 결과를 구하려면 이전에 피보나치 4, 3, 2, 1을 구했더라도 새롭게 다시 연산해야 한다. 다른 숫자에 대해서도 기존에 연산한 결과를 활용하지 못하고 새롭게 연산해야하므로 답은 제대로 나오겠지만 시간이 많이 걸리게 된다. 이 문제는 제한시간이 0.25초로 위 방법을 사용하면 시간 초과가 뜬다. 그럼 어떻게 시간 초과를 피할 수 있을까? 답은 다이나믹 프로그래밍(동적 계획법)이다. 다이나믹 프로그래밍(동적 계획법)이란? 기존의 연산 결과를 저.. 공감수 0 댓글수 0 2020. 11. 19.
백준 11000: 강의실 배정 (C++) 문제 링크: https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si b; } }; // 강의 끝나는 시간 저장(빨리 끝날 수록 우선순위 높음) // pq 원소 값 : 해당 인덱스의 강의실에서 가.. 공감수 0 댓글수 0 2020. 11. 19.
백준 1041: 주사위 (C++) 문제 링크: https://www.acmicpc.net/problem/10411041번: 주사위첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수www.acmicpc.net 주사위로 N*N*N크기의 정육면체를 만들었을 때 3면이 보이는 주사위, 2면이 보이는 주사위, 1면이 보이는 주사위의 개수를 구해서 각 개수를 3면이 보였을 때 최소 조합, 2면이 보였을 때 최소 조합, 주사위의 적힌 최소 숫자(1면이 보였을 때 최소 조합)에 곱해주면 된다.즉 (3면 최소조합)*(3면 보이는 주사위 개수) + (2면 최소조합)*(2면 보이는 주사위 .. 공감수 1 댓글수 0 2020. 11. 17.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.