체유의 IT일지

수 정렬하기2 분류: 정렬 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 5 5 4 3 2 1 예제 출력 1 1 2 3 4 5 💡문제 해결 IDEA 1) 수는 중복되지 않기 때문에 계수 정렬은 x 2) 퀵 정렬로 시도 -> 메모리 초과 3) 삽입 정렬로 시도 -> 시간 초과 4) 계수 정렬로 시도 -> 걍 틀림.... 5) 퀵 정렬을 다시 정리 -> 약 25%까지 가다가..

영역 구하기 분류: 그래프 탐색 이론 (DFS/BFS) 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성..

동전0 분류: 그리디 알고리즘 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 #1차 시도 N,..

그리디 알고리즘 탐욕 알고리즘이라고도 부름 "현재 상황에서 지금 당장 좋은 것만 고른다" -> 최적의 해를 보장할 수 없을 때가 많음 ex. 거스름돈 문제 [500, 100, 50, 10] => 가장 큰 화폐단위부터 Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적해를 보장하는 이유? (정당성 분석) A. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기에 작은 단위의 동전을 종합해 다른해가 나올 수 없기 때문 그리디 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함 문제1. 곱하기 혹은 더하기 문제: 각 자리 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' ..

요약1단계 자의식 해체하기탐색: 자신의 기분 변화 등을 잘 관찰하고, 이 기분이 어디에서 오는지 확인한다.인정: 기분 변화의 이유를 객관적으로 잘 살펴보고, 현재 자신의 처지와 비교해서 인정할 것은 순순히 인정한다.전환: 인정을 통해 열등감을 해소하고, 이걸 변화의 계기로 삼기 위한 액션 플랜을 만든다. 2단계 정체성 만들기어떤 자질을 원한다면, 이미 그걸 갖고 있는 것처럼 행동하라by 윌리엄 제임스‘나는 어떤 사람이다’라는 정체성을 강제하는 환경을 갖추기로 결심했다. 성장을 위한 자기 강제이다.뭔가를 더 잘하고 싶으면 결심을 할 게 아니라 환경부터 만드는 것이다. 자동으로 움직일 수 밖에 없도록 세팅을 하면 나는 저절로 열심히 살게 된다. 나를 훈련시킬 운동장을 만들어 스스로를 밀어 넣는 게 핵심이다...