Priceless

어제 코테 스터디에서 DFS와 BFS에 대해 공부한 후 혼자서 풀어보는 첫 문제 DFS 와 BFS 너무 어렵습니다.. 개념은 이해가 가지만 정작 코드로 짤 때 빼먹는 부분도 많고, 변수도 신중히 써야하고 아직 코딩 경험이 부족한가 봅니다 제 부족한 지식을 채워준 아래 블로그를 참고 했습니다 [백준] 1012. 유기농 배추 풀이 (C++) (tistory.com) 테스트 케이스가 한 번인 경우에는 상관 없지만 테스트 케이스가 두 번 이상일 때는 입력 매핑 값도 두 번 받지만 방문 여부를 나타내는 배열도 전부 false로 바꿔놓아야 하는 것을 잊으면 안된다! 그리고 dfs는 일단 재귀로 구현하는 것이 아직까진 쉽다 물론 재귀 자체도 익숙하지 않아 애를 많이 먹긴 하지만.. 그리고 2차원 이상의 배열을 사용해..

입력 횟수 만큼 거리와 비용을 입력 받은 후 가장 적은 거리거나 가장 적은 비용일 때의 경우의 수를 구한다 처음에는 단순히 합을 구한 후 최소 값이 몇 개인지 확인하면 될 줄 알았다 그 결과 바로 실패.. 사실 아직도 왜 틀렸는지 완전히 이해하진 못했다 아마 예시에서는 100의 배수로만 되어 있어서 단순하지 않은 조건이 있는 듯하다 int main(){ init(); int n ; cin >> n; int c, d; int min = 20000; int count = 0; for(int i = 0; i > c >> d; if(min > c + d){ min = c + d; count = 1; } else if (min == c + d){ count++; } } cout > n..

문자열의 대문자와 소문자 상관 없이 사전적으로 가장 앞에 있는 단어를 출력하는 문제다 C++이라 문자열을 일일이 비교해야 할 줄 알았지만 부등호 하나로 쉽게 비교할 수 있어서 생각보다 어렵지 않았다 입력 값과 현재까지의 가장 앞의 값을 대문자 혹은 소문자로 통일한 후 비교하여 대문자 혹은 소문자로 통일되지 않은 문자를 출력하도록 문제를 풀었다 처음에는 아스키 코드로 접근하려다가 임시 변수를 설정하고 대문자나 소문자로 통일하는 것이 훨씬 속 편한 방법이다 // baekjoon 2204 #include #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base..

개미끼리 만나면 방향을 바꾼다고? 처음에는 개미 마다의 위치를 저장하는 배열과 개미의 방향을 저장하는 배열을 사용하여 각 조건마다 시뮬레이션을 돌리는 방식으로 진행하려고 했다 시간이 많이 소요될 것이고 무엇보다 구현하는 데에도 시간이 많이 걸릴 것 같았다 그래서 찾아보던 중 같은 속도로 이동한 개미가 만나면 서로 반대 방향으로 돌아보니 결국 같은 개미들이 서로 스쳐지나가는 것과 시간이 똑같이 않겠나! 무슨 뜻인지 이해가 잘 가지 않을 수 있다 아래 사이트의 그림과 함께 본다면 더욱 이해가 잘 될 것이다 [백준 4307번] 개미 풀이 (tistory.com) [백준 4307번] 개미 풀이 4307번: 개미 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수..

설명에도 나와있다시피 prioriy queue를 사용을 권장한다 하지만 나는 우선 배열 후 정렬로 해보고 안되면 우선순위 큐를 사용하려고 했다 배열을 순차대로 입력 받고 하위 두 값을 합하여 저장하는 방식으로 코드를 작성했다 이 과정에서 배열에 큰 값을 입력 받을 수 있도록 long long int 타입을 사용해야 했다 난 아직 백준의 이러한 부분이 낯설다 그래도 타입형에 대해 한 번 더 신경 쓸 수 있다는 점은 좋은 것 같다 // baekjoon 15903 #include #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_st..

조합과 중복의 개념이 오랜만이라 아래 사이트를 참고하여 내용을 복기시켰다 조합이 사용되므로 가장 간단한 공식은 다음과 같다 조합/중복 조합 계산기 | OurCalc 조합을 구현하기 위해 재귀 함수를 많이 사용하는 것 같지만 나는 반복문으로 시작한 김에 시간초과가 뜨더라도 답이 맞고 싶었다 하지만 마지막 예제에서 답이 계속 5가 곱해져서 나왔고 단순한 문제인 만큼 재귀 복습하는 셈치고 빨리 넘어갔다 반복문으로 시도한 코드는 다음과 같다 int main(){ init(); int t; cin >> t; int n, m; long long ans = 1; for(int i = 0; i > n >> m; int m_temp = m; int n_temp = 1; for(int j = ..

키와 몸무게를 입력 받아 누가 제일 덩치가 큰 지 알아내는 문제다 나보다 키와 몸무게가 큰 사람이 없으면 그 사람이 제일 덩치가 큰 사람이고 비교하는 사람보다 키는 크지만 몸무게가 작거나 그 반대인 경우 비교하는 사람과 같은 순위이다 몸무게와 키를 저장하는 각 배열에 입력 받고 순위를 담당하는 배열을 추가한다 본인이 키와 몸무게 둘 다 한 번이라도 밀린다면 점수를 올린다(올릴 수록 순위가 낮아짐) 그런 식으로 전수 조사를 하면 구할 수 있는 간단한 문제다 처음에는 순위를 담당하는 배열을 배열 크기만큼 초기화하여 조사하는 사람의 키와 몸무게가 둘 중 하나라도 크면 점수를 빼는 식으로 구현했다 제공되는 예제에서는 잘 작동됐지만 다른 예제에서 잘 작동하지 않아 1점에서 시작하여 패널티를 주는 식으로 하니까 쉽..

Ch.6 비지도 학습6-1. 군집 알고리즘비지도 학습비지도 학습: 타킷을 모르는 데이터를 예측하는 알고리즘흑백 샘플이미지의 경우 높은 값을 낮은 값으로 만들고 낮은 값을 높은 값으로 만든다 비지도 학습을 통한 이미지 분류이미지outline으로 나누어진 이미지의 픽셀만 남게 한다평균을 내어 데이터 개수 별로 구간을 나누어 확인하는 방법이 방법의 경우 평균이 비슷한 데이터끼리 솎아낼 수 없다 대신 각 픽셀 별로 평균을 내는 경우 그만큼 특징이 많아져서 구별하기 수월하다 평균값을 각 이미지에서 뺀 후 차이가 적은 순으로 해당 이미지 인것을 확인할 수 있다 군집: 비슷한 샘플끼리 그룹을 모으는 작업클러스터: 군집을 통해 생성된 그룹 비슷한 샘플끼리 모으기 6-2. k-평균k-평균 알고리즘k-평균 알고리즘: 평균..

Ch.5 트리 알고리즘 5-1. 결정 트리 결정 트리 결정 트리: 데이터를 잘 나눌 수 있는 질문을 통해 분류 정확도를 높인 자료 구조 각 질문은 특성을 이분할 수 있는 질문이다 불순도: 지니 불순도: 결정 트리 모델은 부모 노드와 자식 노드의 불순도 차이가 가능한 크도록 트리를 성장시킨다 정보 이득: 부모 노드와 자식 노드의 불순도 차이 클래스의 표준을 criterion = 'entropy'를 지정하여 엔트로피 불순도를 사용할 수 있다 가지치기를 통해 최대 깊이를 지정하여 루트 노드 아래로 성장할 수 있는 노드를 제한한다 max_depth = 매개 변수를 설정하여 제한할 수 있다 특성 중요도: 어떤 특성이 가장 유용한지 나타내는 정도 결정 트리에 사용된 특성이 불순도를 감소하는데 기여한 정도를 나타내..

아마 처음으로 성공한 백준 골드 문제가 아닐까 싶다! 문제 자체는 별로 어렵게 느껴지지 않았다 다만 입력이 A~J 인 것이 아니라 A~Z 영어 대문자를 다 받는 것으로 고려해야 했다 처음에 아스키 코드를 찾아보기 귀찮아서 A~J는 10개니까 if 문으로 때우려고 했다(다음부터 그러지 않겠습니다..) 그러니 계속 오류도 나고 코드가 너무 길어졌다 그래서 바로 아스키 코드 값으로 배열에 저장하고 알파벳 마다 수가 얼마나 곱해져있는지 계산한다 큰 순서대로 9를 할당하고 곱해진 수들을 합하면 된다 // baekjoon 1339 #include #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); ..