본문 바로가기
반응형

전체 글

2252번 2252번 - 줄 세우기 위상 정렬에 대해서 알아보다가 예제로 풀어본 문제. 위상 정렬이 필요한 경우.. 게임에서 보면 스킬을 1번 찍고, 2번을 찍어야 3번을 찍을 수 있을 때와 같은 상황? 어떤 작업의 우선순위가 필요한 경우??에 사용된다. 주의할 점은 위상정렬은 DAG(Directed Acyclic Graph) 의 구조에서 사이클이 없을 때 사용가능. 싸이클이 발생하면 우선 순위가 흐려지기 때문 '위상 정렬'을 하는 방법은 2가지가 존재. 1. 한 정점에 들어오는 간선의 수가 0일 때, 큐에 넣음으로서 정렬을 할 수 있다. 2. DFS를 통해서 답을 구할 수 있다. 나는 1번 방법으로 문제를 풀었다. 우선 들어오는 간선의 수가 0인 값들을 큐에 넣어주었다. 그 뒤에 각 정점을 방문하면서 , 그 정점.. 더보기
11723번 11723번 - 집합 비트마스크를 공부하면서 기본적인 연습문제로 풀어보았다.. 풀면서 발생했던 문제 1. 시간초과-> cin,cout 을 모두 scanf,printf 로 바꾸면서 수정.2. 처음에 string쓰다보니까 cin, getline 썼을 때 공백으로 인한 문제점 -> char 로 바꾸고 모두 통일하면서 수정.3.원소 1이 비트마스크 0번째 수, 원소 2가 비트마스크 1번째 수... 이런거 헷갈렸음. S 집합에 p번째 원소 추가S |= (1 더보기
1373번 1373번 - 2진법을 8진법으로 이 문제는 푸는데 시간초과가 자꾸 나서 질문 게시판에 글을 올렸었다. 한 고수분께서 친절하게 답변해주셨다.. substr 이란 놈이 시간을 엄청 잡아먹는거였다.. 앞으로 조심해서 사용해야겠다.. 그래서 결국 substr 을 쓰지 않고 size란 변수를 만들어서 증가시켜주니까 AC를 받았다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include#include#include using namespace std; int main(){ string s; getline(cin, s); int size = 0; while (s.size()>size) .. 더보기
2745번 2745번 - 진법 변환 B진법 수 N을 10진법으로 바꾸는 방법. 예를 들면 2진법의 수 1011 => ( 1*2^3 )+( 0*2^2 ) + ( 1*2^1 ) + ( 1*2^0 ) 이런식으로 각 자리의 숫자와 변환할 자릿수의 거듭제곱으로 나타낼 수 있다. string 을 이용해서 맨 앞자리부터 substr 을 이용해서 줄여가면서 문제를 풀 수 있었다. (예를 들어 hello 라는 string 변수를 substr(1)을 하면 ello 라고 변하게 된다는 점을 이용했다.) size는 while 문 밖에서 선언하여 계속해서 줄여가면서 거듭제곱을 구했다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include#incl.. 더보기
11005번 11005번 - 진법 변환2 내가 약간 진법이 약해서 문제를 풀어보았다. 계속 나누고 몫과 나머지를 이용해서 진법을 변환시킨다. 문제에서 숫자와 문자를 모두 표현해야 했기에, char 형 배열에 숫자도 문자화해서 한꺼번에 처리했다. 그리고 stack 을 이용해서 가장 나중에 들어간 값이 가장 처음에 나오도록 해서 정답을 출력했다. 123456789101112131415161718192021222324252627282930313233#include#includeusing namespace std; int main(){ int N, B; char num[36] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I', 'J.. 더보기
9613번 9613번 - GCD 합 최대공약수 응용문제, 아마 유클리드 호제법이 아닌 방법으로 풀면 시간초과가 날 것 같다. 유클리드 호제법을 이용해서 문제를 풀었다. 정답은 int 형 범위를 넘을 수 있으므로 유의! 유클리드 호제법 - A,B 라는 숫자가 있을 때, GCD(A,B)=GCD(B,B%A) (단, B%A가 0 이면 B가 최대공약수가 된다.) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#include using namespace std; int gcd(int a,int b){ if (b == 0) { return a; } else { return gcd(b, a%b); }}i.. 더보기
1850번 1850번 - 최대공약수 한 1년전에 못 풀었던 문제를 풀어보았다. 처음에도 너무 큰 수라 당황했지만, 잘 살펴보니 쉬운 문제였다. 숫자에 집착을 버리고 문제를 봤더니 답이 보였다고나 할까?ㅋㅋㅋㅋ 아무튼 그냥 주어진 입력에 대해서 최대공약수를 구하는 문제였다, 그리고 그 만큼 1을 출력하면 끝. 쉬운 문제지만, 옛날 문제를 풀면서, 최대 공약수, 최소 공배수에 대해 다시 공부해보았다. 꼭 함수 인자를 무의식적으로 int를 써서 AC를 못받는 실수 고치기.... 최대 공약수 구하는 방법 - 2부터 두수의 미니멈까지 나누기. - 유클리드 호제법 ( 재귀, 비재귀) 최소 공배수 구하는 방법 - 최대공약수로부터 구하기. 12345678910111213141516171819202122232425262728293.. 더보기
2448번 2448번 - 별찍기 - 11 유사한 삼각형이 반복되고 있기 때문에, 분할정복 과 재귀를 이용해서 문제를 풀었다. makeTri 에서는 이 삼각형까지 최소로 찾아내고, makeSmallTri 에서는 이 삼각형을 그려내는 방식으로 문제를 풀었다. 분할을 두번 사용했는데... 사실 이렇게 까지 해서 푸는게 맞는 방식인지는 모르겠다. 내 판단대로 풀었다. 그런데 큰 삼각형 분할해서 재귀를 들어갈 때, 제일 작은 삼각형이랑 큰 삼각형이랑 재귀가 맞지 않다고 생각했다.( 합동이 아니다는 뜻) 왜냐하면 작은 삼각형은 맨 아랫줄은 꽉 차 있지만, 큰 삼각형은 한칸이 비어있기 때문에 재귀로 다시 더 들어갈 수 없다고 생각했다. 그래서 큰 삼각형까지 최대한 줄이고 (n ==6 이 될 때까지, n은 삼각형의 아랫변이 아닌.. 더보기
반응형

티스토리툴바