Doby's Lab

기존의 큰 정수형 자료형이 필요할 때는 long long 자료형을 사용했다. 하지만 long long을 사용하기에는 자료형이 너무 작아서 unsigned long long을 사용했다. 0보다 작을 일이 없기 때문에 가능하다. 그리고, 밑에 코드에서 n == 0일 때의 조건이 없을 때는 계속 98%에서 시간 초과가 났었다. 아무래도 반례를 처리하지 못하고 있는 느낌이라 n == 0일 때, 바로 0을 출력해주고 종료를 시켜주니 정답이 나왔다. (0으로 컴파일 실험을 해보다가 0을 넣으면 무한루프가 일어나는 것을 알 수 있었다.) 왜 0은 무한루프를 일으켰을까 (+추가 (궁금해져서)) 왜 0만 무한루프를 출력하는지 궁금해서 mid, low, high 순으로 while문 안에서 출력해보았다. 미해결 코드 #in..

https://www.acmicpc.net/problem/1838 1838번: 버블 정렬 버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개의 서로 다른 정수가 A[0], A[1], ..., A[N-1]의 정 www.acmicpc.net 이번 문제는 논리적인 접근이 꽤 어려웠던 문제다. 처음에는 저걸 어떻게 최적화시켜야 할까를 한참 고민하다가 버블 정렬 말고도 퀵 정렬 힙 정렬의 구현 코드를 가져와서 풀어봐야 할까 했지만 암만 생각해도 체계 자체가 다른데 i를 못 구할 거 같았다. 그래서 생각해냈던 건 '정렬 된 것과 정렬되지 않은 배열에서의 차이점에서 뭔가를 구할 수는 없을까?'가 핵심이었다. 논리 생각해냈..

논리 입력으로 4가 주어지면 4자리 수 중에 예를 들어 7331이면 맨 앞자리부터 7, 73, 733, 7331처럼 모두 소수가 되어 만족하는 수들을 구하는 문제였다. 논리를 이렇게 짜두고 코드는 반대로 7331, 733, 73, 7 순서로 소수인지 판별했다. 하지만, 이는 시간 초과를 유발한다. 그래서 반대로 맨 앞자리부터 소수 판정을 하는 코드를 짰다. 왜냐하면 극단적으로 8자리 수가 주어졌을 때, 8자리 수가 소수인지 판정을 하고 7자리 수가 소수인지 판정하는 것보다는 1자리 수가 소수인지 판정하고 그다음으로 넘어가는 형식이 더 빠르기 때문이다. 그래서 다음과 같이 코드를 짰다. (맨 처음의 수를 기억하고 있어야 하기 때문에 solution 함수에서 answer에 초기값을 넣어줬다.) #includ..

이번 문제는 처음으로 겪어보는 복합형(?) 문제였다. 여러 고난이 있었는데 고난을 겪었던 코드들을 읽어보면서 어떻게 정답에 도달했는지 알아보자. 논리를 어떻게 접근할까 (첫 번째 고난) 스타트팀 링크팀을 각각 나눠서 능력치를 더하고 비교해서 최솟값을 어떻게 구할지 논리에서 막혔었다. 1시간 정도 고민하다가 문제들을 분할시켜보았다. 1. 스타트 팀, 링크 팀 나누기 2. 각 팀 능력치 더하기 3. 각 팀 능력치의 차 값 구하기 4. 차 값의 최솟값 구하기 4개 정도로 분할시켜 하나씩 진행할 수 있었다. #include #include #include using namespace std; int n; bool visited[2001] = { 0, }; bool visited2[1001] = { 0, }; v..

이번 문제는 sort함수를 이용하며 compare에 더 깊게 파고들었다. sort 할 때 compare 함수를 다음 코드로 짜서 컴파일했지만 계속 어디서 나는지도 모를 오류 Invalid Comparator가 발생한다. (Comparator라서 비교 함수 쪽에 문제가 있구나는 인식할 수 있었다.) bool cmp(string a, string b) { if (a.size() = 0) { sumA += a[i]; } if (b[i] = 0) { sumB += b..

이번 문제는 50점과 100점으로 나뉘어 채점을 하게 되며 계속해도 100점이 나오지를 않았다. 해싱의 개념과 Mod의 연산을 알아보며 풀어보자. 개념 해싱(Hashing)이란 데이터를 관리하는 비법으로 이분 탐색 혹은 다른 탐색보다 시간 복잡도를 O(1) 안에서 해결할 수 있다. 어떠한 데이터를 저장하려 할 때 그 데이터를 보관하는 곳을 해시 테이블(Hash Table)이라고 한다. 그리고 각 버킷(bucket, 각 행)이 고유한 주소를 가지게 되는데 데이터를 해시 함수(Hash Function)를 통해 데이터를 주소 값으로 바꾸어서 해시 테이블에 저장한다. 각 버킷에 얼마큼 저장할 수 있는 지를 알 수 있는 곳이 슬롯(slot, 각 열)이다. 한 슬롯에 계속 데이터가 들어오면 이를 충돌(Hash Co..

드디어 백준 골드를 찍었다. 골드를 찍으면 블로그에다가 골드를 찍기까지 과정이나 이렇게 하면 좋을 거 같다는 생각들을 정리해두고 싶었다. 대단한 건 아니다. 말 그대로 대단한 게 아니다. 골드가 되었지만 내 실력은 골드가 아니라고 생각한다. 아직 그래프 이론, 해싱, 그리디 알고리즘 등 다른 기초 알고리즘은 건들지도 않았었다. 이분 탐색, 백트래킹 조금, Monotonic Stack 조금 이 종류들만 깊게 풀었었는데 골드에 금방 왔다. 이제 골드가 되었으니 다른 알고리즘들도 개념 공부하고, 문제로 깊게 들어가 보면서 백준을 풀어나가야 할 거 같다. 티어가 서열 척도가 될 수는 없다. 위에서 말한 거처럼 한 알고리즘을 깊게 파서 티어가 높아지는 경우가 있다. 이럴 경우 장점도 있지만 다른 알고리즘들을 모른..

이번 문제는 꽤나 건들기 싫었던 문제였다. 빡구현의 기미가 풀기 전부터 계속 느껴졌었다. 그래도 CLASS 2가 3문제 남은 시점에서 빨리 졸업하자라는 생각으로 문제에 임했다. 개념 이번 문제는 브루트 포스(Brute-Force) 알고리즘을 사용했다. 브루트 포스란 완전 탐색의 의미를 가지고 '모든 경우의 수를 다 확인해보자'라는 뜻이다. 'for문을 몇 개를 쓰거나 복잡해지든 말든 일단 모든 경우를 다 탐색해보자' 같은 주관적 느낌도 생겼다. 그렇다고 해서 브루트 포스가 무식한(?) 느낌의 알고리즘은 아니다. 오히려 컴퓨터의 장점(단시간 안에 수억 개의 연산을 처리한다는 점)을 잘 살리는 알고리즘이다. (책에서 그랬다..ㅎ) 고생했던 포인트 1. 8x8 사이즈의 체스판을 선언해둬야 했었다. 처음에는 문..