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..

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

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

이번 문제가 어려웠던 이유는 무엇을 이분 탐색해야 하는지도 정확히 파악하고 있고, 논리까지 짰었지만 센스(?)가 없어서 풀지 못하던 문제이다. (알고리즘은 이분 탐색을 사용했기에 이분 탐색 카테고리에 넣어둔다.) 우선 블루레이의 크기를 탐색하기 때문에 1을 low로 두고, 모든 강의 길이의 합을 high로 두고, 나오게 된 mid에 맞춰서 sum변수를 선언하고, 강의의 길이를 하나씩 더해가며 sum이 mid를 넘을 때마다 블루레이 하나 더 써야겠다 라는 논리로 접근하면 된다. 이번 문제에서 해결하지 못하는 포인트가 2가지였다. sum이 mid를 넘어갈 때, sum을 0으로 초기화해버리면 넘어갈 때 순간의 원소(강의의 길이)는 어떻게 해결하나 mid로써 주어진 길이가 7이라고 치면 한 강의의 길이가 8일 ..