알고리즘 공부

링크 : https://www.acmicpc.net/problem/1002 테스트 케이스의 분류를 잘했어야 하는 문제였다. 거리를 구하고 반지름1과 반지름2의 합과 차 range로 case를 분류하자 라는 생각을 시작으로 접근하였다. sqrt와 pow함수를 이용

링크 : https://algospot.com/judge/problem/read/FESTIVAL 간만에 vector을 이용해봤다. 자료구조 공부했을 때, 교수님이 벡터 못쓰게해서 매우 힘들었는데 지금 쓰니까 겁나 편하다. 소수점 몇번째 자리까지 나오게 하기 위해서 precision을 사용하였다. 이렇게 설정하니까 아래의 for문에서는 모두 소수점 10...

링크 : http://acmicpc.net/problem/1010 바로 조합 사용하면 될 것 같아서 자료구조 때 배웠던 재귀함수를 이용한 조합을 사용했다. 문제는 컴파일 시간. 처음에는 case의 크기만큼의 새로운 동적 할당하여 cout 하였는데 이러니까 시간 초과

링크 : https://www.acmicpc.net/problem/1015 문제 이해하는데 좀 애먹었다. 결론적으로 P는 A 수열의 숫자들이 몇번째로 작은지 저장해놓은 index table인 것이었다. 벡터 전체 복사하는데 assign 함수 이용하는 것. 벡터 안

링크 : https://www.acmicpc.net/problem/1018 2차원 배열 초기화하는 방법을 몰랐다. 1차원 배열 초기화하듯이 = { 'W' } 해도 문제 없다. like char arr 50={ 'W' }; 체스판이므로 행과 열을 더한 값이 짝수와 홀

링크 : https://www.acmicpc.net/problem/1021 queue 라이브러리를 사용하자. 자료구조때 많이 만들어 썼다. 그런데 쓰면서 array를 부모 클래스로 받은 queue를 만들껄이라는 후회를 했다. queue가 인덱스 접근에 최악이다. 참

링크 : https://www.acmicpc.net/problem/1026 벡터를 사용하는게 다 좋은 것은 아니라는 걸 오늘 다시 깨닫는다. 인덱스로 값 insert하려면 iterator을 사용해야 한다는 점이 꽤 큰 penalty로 다가온다. 이거 근데 할 말이

링크 : https://www.acmicpc.net/problem/1822 복습할 게 많은 문제다. 이렇게 하니까 시간 초과가 걸린다. .size() 이런 것도 다 변수로 정리했음에도 불구하고 계속 시간 초과가 나왔다. 그래서 검색해 봤는데 set library를

링크 : https://www.acmicpc.net/problem/2003 아 진짜 마음에 안든다. 계속 쉽게 생각하려고 하니까 for문을 많이 쓰게 되고, 자연스럽게 연산 시간은 늘어나고, 시간이 늘어나니 틀리고, 이게 계속되니까 답답하다. 이 알고리즘은 망했다.

링크 : https://www.acmicpc.net/problem/1463 int dp[1000000]; 이걸 int main() 밖으로 빼야 한다. 경고가 뜨는데 이유는 모르겠다. dp 배열을 생성하여 인덱스의 숫자가 어떻게 구해졌는지 계산하고 최솟값을 저장해놓는

링크 : https://www.acmicpc.net/problem/1049 찝찝하다. 왜 이렇게는 되는데 저렇게는 안되는거지의 전형적인 답답함. 한번 살펴보자. 비교해야 할 대상이 총 3개다. 6개가 담긴 package의 가격이 (1개당 가격 X 6) 보다 클 경

링크 : https://www.acmicpc.net/problem/9095 분석 정수 n이 주어졌을 때 1, 2, 3의 합으로 나타내야 한다. 3은 1, 2로, 2는 1로 표현할 수 있으므로 3이 들어가는 수는 (3), (1+1+1), (1+2), (2+1) 의 총

링크 : https://www.acmicpc.net/problem/1065 한수 자체 의미를 이해 못했다. 1의 자리수일 경우 : 모두 한수이다. 10의 자리수일 경우 : 모두 한수이다. 십의 자리에서 일의 자리로 d만큼 등차되었다고 본다. 100의 자리수일 경우

링크 : https://algospot.com/judge/problem/read/BOGGLE 상하좌우, 대각선으로 접근할 수 있다. 게다가 중복해서 가져올 수 있다는 점도 잊으면 안된다. 게다가 지금 배우는 6장의 코드는 너무 느리다고 사이트에 언급이 되어있다. 가장 간단한 방법은 완전 탐색을 통해 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 ...

링크 : https://www.acmicpc.net/problem/9012 자료구조 수업 들을 때 큐랑 스택 이용해서 푼 적이 있는 문제다.

앗 이것도 자료구조 수업 때 풀었던 문제.. 쉽게 패스한다.그래도 양심 챙기고 stack으로 구현..

왜 계속 쉬운거 해요?\-> 피곤해서.. 빨리.. 해결할 수 있는 거 하고 있습니다..왜 switch문으로 안했나요? 그게 더 깔끔한데 코알못이네요?\-> 그 컴퓨터 구조에서 switch문을 컴파일러가 if문으로 일일이 푼다고 배웠습니다. 그래서 컴퓨터 생각해서 if문

소수 찾기.소수 찾는 알고리즘을 살펴보자.자연수 1보다 큰 수를 기준으로 소수를 판별하므로 1 이하인 수는 return false를 한다.2부터 시작하여 sqrt(n)까지 진행한다. sqrt(n)까지 진행하는 이유는 다음과 같다. 예를 들어 15의 경우 (1x15),

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.왜 조건을 안읽는거야? 제발 읽자. 40보다 작거나 같다는 조건을 안지켜서 계속 틀렸다^~^ 좋겠다 정말 눈알 없어서그래도 꽤 고생했던 만큼 분석해보자.우선 재귀

링크 : https://www.acmicpc.net/problem/14501 찾다보니 15486번 문제는 조건만 바뀐 것이었다. 15486번 문제까지 해결하려 했다면 정말로 이 문제의 핵심 $O(N)$안에 해결하는 것이 중요했다. 15486번 문제 링크 : http

링크 : https://algospot.com/judge/problem/read/PICNIC 문제읽기 n은 친구 수, m은 쌍의 수 코드 6.4의 문제는 중복된 요소들도 같이 센 다는 것이다. 따라서 사전순으로 나열하여 경우의 수를 세보도록 하자. 코드 분석

링크 : https://algospot.com/judge/problem/read/BOARDCOVER자유롭게 회전 가능.겹치거나 검은 칸을 덮거나 게임판 밖으로 나가서는 안된다.게임판이 주어졌을 때 덮을 수 있는 경우의 수.흰 칸이 3의 배수여야 겹치지 않고 덮

링크 : https://algospot.com/judge/problem/read/CLOCKSYNC 문제읽기 스위치를 누르면 바뀌는 시계들이 정해져있다. 재귀를 이용해서 최소 스위치 클릭 수를 찾아야겠다. 코드 코드는 책의 코드를 분석하는 것으로 끝내겠다. 책에서 너

정수를 저장하는 큐. 입력으로 주어지는 명령을 처리해야 하니까 switch문 쓰면 좋겠다. 가자.그러한 인식. push만 숫자를 입력받아야 할 경우 애초에 num까지 받지 말고 push 명령어가 들어왔을 때만 num을 받아야 겠다는 인식. 그러한 인식이 가장 중요하다.

링크 : https://algospot.com/judge/problem/read/QUADTREE 문제읽기 흰색과 검은 색으로 그림을 압축하는 것. 주어진 공간을 항상 4개로 분할하여 재귀적으로 풀어야 한다. 게다가 심지어 상하로 뒤집은 것을 결과로 내놔야 하는데 이

링크 : https://algospot.com/judge/problem/read/FENCE판자의 높이를 배열로 받아서 h\[] 로 처리하고 l번 판자부터 r 번 판자까지 잘라내서 사각형을 만든다고 하면 $(l-r+1)\\times{min\_{i=l}^{r}}

링크 : https://algospot.com/judge/problem/read/FANMEETING팬의 수는 항상 멤버의 수 이상이다. 남성 멤버와 남성 팬은 포옹하지 않는다.여기서 모든 멤버가 동시에 포옹하는 일이 몇 번 있을지 보여라.남성을 1로, 여성을

링크 : https://www.acmicpc.net/problem/11726단순하다. 2×n 크기의 직사각형이 존재하고 이를 1×2 또는 2×1 타일로 채워야 한다.다이나믹 프로그래밍으로 잡혀있고 brute-force로 잡힌 것이 아닌 것으로 보아 단순한 알고

링크 : https://www.acmicpc.net/problem/1120맙소사. 이어폰을 안가져왔다. 하지만 굴하지 않고 오늘은 speedy하게 접근하겠다.길이는 같게 주어지고 문자열의 차이를 알아야 한다. 두 문자열 X와 Y의 차이는 X\[i]≠Y\[i]인

링크 : https://www.acmicpc.net/problem/11399정렬. 그리티 탐색 문제.작은 순서대로 배열해야 최솟값이 나올 것 같다. 시작해보자. 그럼 이걸 어떻게해야 작은 순서대로 정렬할 수 있을까? 자료구조 문제이다.Ver 1.Ver 2.so

링크 : https://www.acmicpc.net/problem/2579 문제읽기 다이나믹 프로그래밍이다. 한번에 1 계단 또는 2 계단을 오를 수 있다. 하지만 연속 3개의 계단을 모두 밟

링크 : https://www.acmicpc.net/problem/1920N까지의 배열이 주어져 있다. X라는 정수가 존재하는지 찾아야 한다.애초에 배열에 넣을 때 이분트리로 넣고 탐색하면 딱 좋을 것 같다.Out Of Bounds : 만약 계속 오른쪽 노드로

링크 : https://www.acmicpc.net/problem/10866deque 자료구조 확인하는 문제. 복습하는 차원으로 빠르게 접근하자.출력 형식을 잘못 맞춰서 겁나 틀렸다. 다음에는 차분히 맞추길... 그냥 문제 번호를 외워서 이러한 경우에는 이 문

링크 : https://www.acmicpc.net/problem/11653 문제읽기 소인수분해. 2,3을 따로 나눠주면 빨르게 처리 가능했던 것을 기억하며 진행하자. 코드 분석 다음 블로그를 참고하였다. 링크 : https://aossuper8.tistory.c

링크 : https://www.acmicpc.net/problem/2606 문제읽기 노드 연결이 하고 싶다!! 포인터를 사용하고 싶다!! 포인터는 1을 가리키는 포인터 1이 아닌 포인터 1이 아닌 원소를 가리키는 포인터. 만약 연결되었다면 이 포인터는 지워진다.

링크 : https://www.acmicpc.net/problem/2193다이나믹 프로그래밍. 우선 시작해보자.0과 1로만 이루어진 수를 이진수라고 한다. 이진수 중 특별한 성질을 갖는 것들이 있는데 이들을 이친수, pinary number이라고 한다. 처음

링크 : https://www.acmicpc.net/problem/11727앗 저번 문제 2xn 타일링에서 발전한 문제다. 2x2 타일링이 추가되었다. 한번 살펴보자.

링크 : https://www.acmicpc.net/problem/9461파도반 수열이라는 것이 있다고 한다. 앗 수열을 나누어 봤더니 규칙이 보인다. dp\[i] = dp\[i-2] + dp\[i-3] 이렇게 된다.근데 그림을 보자. 그림이 왜 있겠냐. 삼각

링크 : https://www.acmicpc.net/problem/15649 문제읽기 길이가 M인 수열. 1부터 N까지의 자연수를 나열하고, 출력은 공백으로 구분. 증가하는 것은 사전 순으로! 코드 분석

링크 : https://www.acmicpc.net/problem/2164 그.. 사실 개강하고 수업 들은 것 정리해야 하는데.. 하기 싫어서.. 알고리즘을 푸려고(?????) 잠시 들렀습니다.. 시작하겠습니다.. 빨리 끝나고 12시 전에 자야지.. 문제 읽기 N장의 카드가 순서대로 위에서부터 있고. 한 장 남을 때까지 반복한다. 맨 위에 있는 것 버리...

링크 : https://www.acmicpc.net/problem/1149여유있을 때, 어려운 문제 풀어보도록 하자.연속되게 색깔이 칠해져서는 안된다. 이번 문제는 RGB 총 3가지의 경우가 있으므로 int ans = min(c1, min(c2,c3)) 이런

링크 : https://www.acmicpc.net/problem/1676팩토리얼 계산하고 뒤의 0을 계산하자팩토리얼을 계산하고 string으로 바꿔서 string의 size-1 위치부터 접근해서 0과 비교하자 -> string을 index로 접근하여 비교할