티스토리

Jo_Wick

검색하기

블로그 홈

Jo_Wick

go-jowick.tistory.com/m

go-jowick.tistory.com

구독자: 0

방명록 방문하기

주요 글 목록

백준 11727번 (2xn 타일링 2) c++ https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제풀이 이전에 풀이했던 2xn 타일링을 보고 오면 훨씬 쉽게 이해할 수 있다. 이 문제는 DP를 이용하여 푸는 문제이다. 다른 많은 풀이 사이트에서는 단순히 DP[i] = DP[i-1] + (DP[i-2]*2) 라는 이유를 N에 따라 세어보았을 때 이게 말이 된다라는 식으로 많이 적어놓았다. 하지만 밑에 적어 놓은 것을 보면 제대로 된 규칙을 알 수 있다. DP[i-2] 에는 1x2인 2개의 타일과 2x2인 1개의 타일이 붙.. 공감수 0 댓글수 0 2023. 6. 28.
백준 11726번 (2xn 타일링) c++ https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 다른 많은 풀이 사이트에서는 단순히 DP[i] = DP[i-1] + DP[i-2] 라는 이유를 N에 따라 세어보았을 때 이게 말이 된다라는 식으로 많이 적어놓았다. 하지만 밑에 적어 놓은 것을 보면 제대로 된 규칙을 알 수 있다. DP[i-2] 에는 1x2인 2개의 타일이 붙고, DP[i-1] 에는 2x1인 1개의 타일이 붙은 두가지 경우의 수를 합치면 DP[i]가.. 공감수 0 댓글수 0 2023. 6. 28.
백준 1158(요세푸스) c++ 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 풀이 문제를 큐를 이용하여 생각을 해보면, N만큼 오름차순으로 큐에 숫자가 들어가 있다. 그리고 K 번째의 숫자를 제거하는게 문제이다. 그러면 K만큼 큐에서 pop을 함과 동시에 push를 해주면 문제가 해결이 된다. 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int N, K; cin >> N >> K; queue input; for(register int i .. 공감수 0 댓글수 0 2023. 4. 21.
백준 1874번(스택 수열) c++ 문제 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 문제 풀이 문제 자체가 조금 이해하기 난해할 수 있다. 예제 1번을 풀이를 하자면 [4, 3, 6, 8, 7, 5, 2, 1] 최종적으로 이러한 수열을 만들어야 한다. 그러면서 오름차순으로 1~8까지 stack에 쌓아야 하는데 push는 어느 때에나 해도 상관없지만 pop은 반드시 저 수열에 맞춰 pop을 해야.. 공감수 0 댓글수 1 2023. 4. 18.
백준 에디터 (1406번) c++ 문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 풀이 처음 문제를 보고 나는 vector로 풀까 하고 생각을 했다. 하지만 시간 제한이 0.3초 인걸 확인하고 vector.erase와 vector.insert가 시간초과에 걸릴거 같아 연결리스트로 생각을 바꿨다. vector로 구현한 소스이다. #include #include #include using namespace std; int main(){ ios_base::sync_with_.. 공감수 0 댓글수 0 2023. 4. 18.
백준 9012번(괄호) 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀이 스택 개념을 이용하여 풀면 된다. 나는 여기서 스택을 이용하진 않고 단순히 result 변수를 통해 숫자를 세어줌으로써 해결하였다. 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; for(register.. 공감수 0 댓글수 0 2023. 4. 17.
백준 9093번 (단어 뒤집기) 문제 https://www.acmicpc.net/problem/9093 문제 풀이 이 문제는 스택을 사용하여 푸는 문제이다. 하지만 입출력 또한 중요한 문제이다. string 변수와 cin을 통해 'I am happy today'를 받으려고 하면 'I'만을 저장하게 된다. 왜냐하면 공백을 만나면 문자열의 끝으로 인식하여 'I' 만을 저장하게 된다. 그래서 다른 방법이 필요하다. 바로 getline을 이용하는 것이다. getline은 두가지 종류가 존재한다. istream라이브러리의 cin.getline(), string 라이브러리의 istream& getline()이 존재한다. cin.getline cin.getline (char* s, streamsize n, char delim); 첫번째 인자는 ch.. 공감수 0 댓글수 0 2023. 4. 17.
백준 1620번(나는야 포켓몬 마스터 이다솜) c++ 문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 풀이 이 문제는 Map 혹은 Hash로 아주 쉽게 풀 수 있다. C++ Map 사용법 https://go-jowick.tistory.com/15 C++ STL Map 사용법 Map이란? map은 각 노드가 key와 value로 이루어진 트리이다. 중복을 허용하지 않는게 특징이다. 그리고 map은 검색, 삽입, 삭제 등이 O(logn)인 레드블랙트리로 구성되어.. 공감수 0 댓글수 0 2023. 4. 16.
PS 팁 2 코딩 팁 1 https://go-jowick.tistory.com/16 입출력 함수 속도 비교 링크입니다. https://www.acmicpc.net/blog/view/56 전역변수, 지역변수 사이즈 차이 main 함수 내에서 배열의 크기를 크게 잡았을때 Stack Overflow가 나지만 전역변수에서 배열의 크기를 크게 잡아도 오류가 나지 않는 이유 지역변수는 스택(Stack)영역에 저장되기 때문에 크기가 너무 커지면 오버플로우(Stack overflow)가 발생합니다. 윈도우의 프로세스당 기본 스택사이즈(1MB) or 리눅스의 프로세스당 기본 스택사이즈(8MB)가 그래서 저 사이즈보다 크게 사용하면 오류가 나는 것입니다. 기본적으로 저희가 문제를 풀때는 프로세스를 하나만 쓴다고 생각하시면 됩니다. 프.. 공감수 0 댓글수 0 2023. 4. 16.
PS 팁 1 1. sagment fault, 틀렸습니다 의 경우 생각해 볼 수 있는 경우의 수 혹시 배열의 사이즈를 넉넉히 잡아 주었는지? 배열의 마지막엔 null이 오는 경우까지 생각해 주어야 하므로 input이 1,000,000 인 경우배열의 사이즈를 int input[1000001]로 잡아 주어야합니다. 추가적으로 sagment fault의 대부분의 경우에는 잘못된 주소값에 접근하려 해서 생기는 오류입니다. 배열의 index가 맞는지 포인터를 현재 잘 쓰고 있는지에 대한 부분을 확인하면 됩니다. 2. 초기화를 잘하자 처음 변수를 선언할 경우 쓰레기값이 들어가게 됩니다. 그래서 항상 0으로 초기화를 시켜주시는게 좋습니다! 3. 맞왜틀을 외치기 전에 다시 한번 코드를 보자 맞왜틀을 하는 대부분의 경우 자신의 논리가.. 공감수 0 댓글수 0 2023. 4. 16.
C++ STL Map 사용법 Map이란? map은 각 노드가 key와 value로 이루어진 트리이다. 중복을 허용하지 않는게 특징이다. 그리고 map은 검색, 삽입, 삭제 등이 O(logn)인 레드블랙트리로 구성되어 있다. map map1; map은 기본적으로 key를 기준으로 오름차순으로 정렬을 한다. 만약 내림차순으로 사용하고 싶다면 map map1;로 사용하면 된다. Map 삽입 그리고 map을 삽입할 때 가장 중요한 점은 pair 객체로 넣어야 한다는 것이다. map1.insert(pair(1, 2)); Map 검색 map은 기본적으로 데이터를 찾을 때 iterator를 사용한다. 그래서 map의 멤버함수인 find를 사용했을 때 만약 찾는 값이 존재하면 그 값의 주소를 반환하고 그렇지 않다면 map.end()를 반환한다. .. 공감수 0 댓글수 0 2023. 4. 14.
Hash c++ 개념 정리 Hash Hash는 기본적으로 임의의 길이의 문자열을 받아 고유한 key값을 생성한다. 그리고 그 key값에 value를 저장한다. 이렇게 저장을 할 때 같은 key값이 나올 수도 있다. 그래서 그러한 경우에는 Chaning 방법을 써서 해결하면 된다. Chaning이란 연결리스트를 통해 바로 뒤로 이어서 저장을 한다. 해싱함수 #define MAX_TABLE 10000 // 내가 필요한 만큼의 테이블 크기로 잡아주면 된다. int hashing(string input){ // 정수로 바꿔 주는 함수이다. int div = 401; // 이렇게 정수로 바꿀때 특정한 소수들을 이용하면 최대한 key값이 겹치지 않게 만들 수 있다. int i = 0; int len = input.length(); while.. 공감수 0 댓글수 0 2023. 4. 14.
백준 1269번 (대칭 차집합) c++ 문제 문제 풀이 두 가지 방법으로 이 문제를 풀 수 있다. 1. Map을 사용하는 방법 2. Hash를 사용하는 방법 Map이란? map은 각 노드가 key와 value로 이루어진 트리이다. 중복을 허용하지 않는게 특징이다. 그리고 map은 검색, 삽입, 삭제 등이 O(logn)인 레드블랙트리로 구성되어 있다. map map1; map은 기본적으로 key를 기준으로 오름차순으로 정렬을 한다. 만약 내림차순으로 사용하고 싶다면 map map1;로 사용하면 된다. Map 삽입 그리고 map을 삽입할 때 가장 중요한 점은 pair 객체로 넣어야 한다는 것이다. map1.insert(pair(1, 2)); Map 검색 map은 기본적으로 데이터를 찾을 때 iterator를 사용한다. 그래서 map의 멤버함수인 .. 공감수 0 댓글수 0 2023. 4. 14.
백준 1065번(한수) c++ 문제 문제풀이 문제에서 N은 1000 이하의 자연수이다. 그러면 총 세가지의 경우로 나눠 생각할 수 있다. 1 ~ 9 / 10 ~ 99 / 100 ~ 999 로 나눌 수 있다. 그런데 1 ~ 9는 하나의 숫자 밖에 없기 때문에 자동적으로 한수가 된다. 그리고 10 ~ 99 또한 두가지 숫자 밖에 없기 때문에 무조건 등차수열이 될 수 밖에 없다. 그러면 우리는 100 ~ 999의 경우만 생각을 하면 된다. hun = i / 100; ten = (i % 100) / 10; one = i % 10; int fir = hun - ten; int sen = ten - one; if (fir == sen) { stan++; } 이렇게 각 자리의 수를 구한 뒤, 각 자리 끼리 차이를 구하여 만약 차이가 같다면 cou.. 공감수 0 댓글수 0 2023. 4. 9.
백준 1018번 (체스판 다시 칠하기) c++ 문제 브루트포스를 통해 이문제를 해결하면 된다. 먼저, 이렇게 W와 B로 시작하는 체스판을 만들어놓고 string w_start[8] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" }; string b_start[8] = { "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB" }; W와 B로 시작하는 것 중 어떤 것이 더 유리한지 count를 센다. int w_check(int col, int row){ int count = 0; int w_col = 0; i.. 공감수 0 댓글수 0 2023. 4. 9.
백준 11866번 (요세푸스 문제 0) c++ 문제 문제 풀이 1. 큐를 이용한다. 큐는 FIFO(First In First Out)으로 선입선출 즉, 먼저 들어온 얘를 먼저 빼주는 방식이다. 그래서 Enqueue를 하면 맨 뒤에 들어가고 Dequeue를 하면 맨 앞 원소가 나오게 된다. 문제에서 N은 1000개이다. 그래서 그냥 선형 queue를 구현하여 사이즈를 잘못 잡으면 못 맞출 가능성이 있다. 이럴 때는 원형 queue를 쓴다면 메모리를 훨씬 절약하여 풀 수 있다. 선형 queue는 포화 상태가 아니여도 만약 큐의 rear가 배열의 마지막 인덱스와 같다면 포화 상태로 인식하여 더 이상 삽입 할 수 없다. 하지만 원형 queue는 선형 queue와 다르게 만약 큐의 rear가 배열의 마지막 인덱스이면서 포화 상태가 아니라면 rear를 queu.. 공감수 0 댓글수 1 2023. 2. 16.
백준 11723번 (집합) c++ 문제 문제풀이 1. 비트마스킹을 이용해야 한다. 비트마스킹이란? 컴퓨터는 모든 데이터를 이진수로 표현한다. 그래서 이진수 표현을 자료구조로 쓰는 기법을 비트마스킹이라고 한다. 비트마스킹을 이용하면, 더 적은 메모리, 더 적은 시간을 사용하여 효율적으로 구현할 수 있다. ex) a = 9, b = 7 1. a & b (AND) a = 1001 b = 0111 a & b = 0001 = 1 2. a | b (OR) a = 1001 b = 0111 a | b = 1111 = 15 3. a ^ b (XOR) 같은 비트라면 0으로, 틀리다면 1로 바꾼다. a = 1001 b = 0111 a ^ b = 1110 = 14 4. ~a (NOT) a = 1001 ~a = 0110 = 6 5. (SHIFT) a = 100.. 공감수 0 댓글수 0 2023. 2. 15.
백준 9655번 (돌 게임) c++ 문제 문제 풀이 문제의 조건을 제대로 파악해야 한다. 1. 둘 다 각각의 차례에 1개 또는 3개를 가져갈 수 있다. 2. 두 사람이 완벽하게 게임을 플레이 한다. 3. 게임은 상근이가 먼저 시작한다. N = 1 N = 2 N = 3 N = 4 N = 5 N = 6 SK CY SK CY SK CY 이렇게 각 N에 따라 답은 정해져 있다. 규칙을 보자면 짝수일 때, 홀수일 때 각각 답이 같은 것을 알 수 있다. 그래서 단순히 홀수, 짝수를 판별해 답을 도출할 수 있다. 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; if(N & 1){ cout N; bool .. 공감수 0 댓글수 0 2022. 12. 27.
백준 2740번 (행렬 곱셈) c++ 문제 문제 풀이 행렬 곱셈을 할 줄 안다면 정말 쉽게 풀 수 있다. 행렬 곱셈은 기본적으로 왼쪽 행렬의 행과 오른쪽 행렬의 열을 곱하고 더하는 것이다. 그래서 1행 1열 = 1행 X 1열 1행 2열 = 1행 X 2열 2행 1열 = 2행 X 1열 2행 2열 = 2행 X 2열 이런식으로 계산한다. 예제를 직접 손으로 풀어본다면 이러한 형태가 된다. 이러한 풀이방식 그대로 코딩을 하면 된다. 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N, M, K; int input_1[101][101] = {0,}; int input_2[101][101] = {0,}; cin >> N >> M.. 공감수 0 댓글수 0 2022. 12. 25.
백준 2581번 (소수) c++ 문제 문제풀이 이 문제는 에라토스테네스의 체만 안다면 쉽게 풀 수 있는 문제다. 에라토스테네스의 체는 1 ~ 120 까지 나열을 한뒤 1. 1은 소수가 아니기 때문에 제외한다. 2. 2의 배수 중 2는 소수이기 때문에 남기고 나머지는 제외한다. (빨간색) 3. 3의 배수 중 3은 소수이기 때문에 남기고 나머지는 제외한다. (초록색) 4. 5의 배수 중 5는 소수이기 때문에 남기고 나머지는 제외한다. (파란색) 5. 7의 배수 중 7은 소수이기 때문에 남기고 나머지는 제외한다. (노란색) 6. 위 과정을 반복한다. 이렇게 먼저 N까지 소수를 판별한뒤 답을 출력하면 된다. 전체 코드 #include using namespace std; int prime[10001]; int main(){ ios_base::.. 공감수 0 댓글수 0 2022. 12. 25.
백준 1676번 (팩토리얼 0의 개수) c++ 문제 문제풀이 팩토리얼은 1부터 N까지 곱하는 것을 뜻한다. 그러면 10이나 100을 곱할때 끝에 0이 생기는 것을 알 수 있다. 하지만 단순히 10이나 100의 갯수를 센다고 해서 해결이 되지 않는다. 5!의 경우를 생각해보자. 1 X 2 X 3 X 4 X 5 = 120 10을 곱하지 않았는데도 0이 생긴것을 알 수 있다. 2 X 5 가 존재할 때 0이 붙는 것을 생각할 수 있다. 그러면 2의 배수와 5의 배수를 각각 짝지어 세어주면 문제가 풀릴거 같다. 2의 배수가 5의 배수보다 숫자가 훨씬 많기 때문에 5의 배수만 세주면 될거 같지만, 아직 더 생각해야할 조건이 남아 있다. 만약 25의 경우는 어떨까? 25 = 5 X 5 이기 때문에 5가 2개가 필요하다 그러면 0도 2개가 필요하다는 걸 우리는 알.. 공감수 0 댓글수 0 2022. 12. 25.
백준 1427번 (소트인사이드) c++ 문제 문제풀이 단순히 수를 받아 내림차순으로 자릿수를 바꿔줘야 한다. N의 조건이 1,000,000,000 이기 때문에 char 형식으로 바꿔 문자열로 받는다고 생각을 바꿔보자. 그러면 char input[11] 선언해줘도 무방하다. 그렇게 문자열을 받아 sort 함수를 쓰면 된다. 하지만 sort 함수의 기본 정렬은 오름차순이다. 그래서 우리는 sort(input, input + N, greater()) greater를 써야 한다. 오름차순 less() 내림차순 greater() 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); char input[11] = {0,}; cin >> in.. 공감수 0 댓글수 0 2022. 12. 24.
백준 1181번 (단어 정렬) c++ 문제 문제풀이 이 문제는 구조체, 정렬과 문자열에 대해 잘 알고 있다면 쉽게 풀 수 있다. struct Input{ char word[51]; int len; }; 먼저 단어와 단어의 길이를 저장하는 구조체를 선언해준다. for(register int i = 0; i > in_temp; int exist = 0; for(register int j = 0; j < input_cnt; j++){ if(!strcmp(input[j].word, in_temp)){ exist = 1; break; } } if(!exist){ strcpy(input[input_cnt].word, in_temp); int temp = 0; while(input.. 공감수 0 댓글수 0 2022. 12. 24.
백준 1010번 (다리놓기) c++ 문제 문제풀이 이 문제는 두가지 방식으로 풀 수 있다. 1. 조합 2. DP 1. 조합 nCr 서로 다른 n개 중 r개를 뽑는 경우의 수를 조합 예를 들어 A, B, C, D, E 5명의 후보가 존재할 경우, 2명의 대표를 뽑는 경우의 수는? (A, B), (A, C), (A, D), (A, E) (B, C), (B, D), (B, E) (C, D), (C, E) (D, E) 답은 10이 된다. 현재 문제에 적용을 시켜보면 n = C, r = N가 된다. 코드 #include using namespace std; unsigned long long dp[101]; unsigned long long fact(int n){ if(dp[n]){ return dp[n]; } else{ dp[n] = n * fac.. 공감수 0 댓글수 0 2022. 12. 24.

문의안내

티스토리
로그인
고객센터

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