Doby's Lab

이번 문제는 DFS를 활용하여 풀려했었다. 하지만, DFS로 구현할 경우에는 TLE가 발생한다. 게시판에서는 BFS를 활용하여 풀어야 한다고 조언한다. 문제를 풀 때 어떤 포인트에서 DFS 혹은 BFS로 풀어야 하는지 알 수 있을까? 여러 블로그를 읽어보다가 감이 잡힌 듯하다. 최단 경로를 알아보아야 할 때, BFS BFS는 어떤 기준점으로부터 인접한 노드들을 차근차근 접근 해나가지만 DFS는 한 군데 길로 쭉 갔다가 조건을 만족하지 못하면 다시 돌아와 다른 노드들을 접근하기 때문에 시간적인 측면에서 BFS가 이런 부분에서는 효율적이다. 하지만, 경로에 대해 가중치(weight)가 붙을 때는 DFS를 활용해야 한다. 이동 과정에 있어서 여러 제약이 있을 때는 DFS (이 점에서 백트래킹과 유사한 거 같다..

이 문제는 논리를 쉽게 떠올릴 수 있었지만 그 논리를 구현하는 데에 있어서 많은 고민을 했다. 밭을 돌아다니는 게 한 사람이 아닌 두 사람이라 함수를 두 개 선언해야 할지 함수를 두 번 콜 해야 할지 혹은 함수 하나에 두 명을 돌아다니게 하는 방법이 있는지 고민을 하다가 모든 방법이 구현이 다 어렵게 느껴져서 논리를 찾아보았다. 논리를 보고서 그냥 말이 안 나왔다. 잠깐 멍 때렸던 거 같다. '왜 이런 생각을 못 했지'라는 말이 나왔다. 두 명을 돌아다니게 하는 것이 아니라 한 명이 모든 구역을 돌아다니게 하는 방법을 생각하면 되었었다. 문법도 알고리즘의 문제도 아닌 논리의 문제가 가끔 머리를 세게 친다. 점점 어려운 문제들을 풀어보면서 결국엔 다 알고리즘 문제가 아니라 논리의 문제 같다고 느껴진다. 생..

1838번 풀이 글과 이어진다. [이전 포스팅 링크] https://draw-code-boy.tistory.com/38 [알고리즘] 백준 1838번: 버블 정렬 (C++), 더 논리적인 감각을 만들어내야 한다 https://www.acmicpc.net/problem/1838 1838번: 버블 정렬 버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개 draw-code-boy.tistory.com [주소 연산자] 포인터에 바로 들어가기 전에 주소 연산자(&)를 알아보자 주소 연산자는 말 그대로 어떤 한 변수의 주소를 가져와주는 연산자이다. 예를 들어 #include int main() { char a = 'i';..

논리적으로는 쉬운 문제였다. 하지만, 내가 짜 놓은 논리와는 계속 엇나가는 출력이 나와서 1시간 동안 정렬할 때 쓴 compare 함수를 들여다보았지만 문제가 없는 듯했다. (일부는 내가 원하는 대로 정렬하지만 일부는 논리를 엇나갔었다.) #include #include #include using namespace std; bool cmp(vector& a, vector& b) { if (a[1] != b[1]) { return a[1] > b[1]; } else { if ((a[1] == b[1]) && (a[2] != b[2])) { return a[2] < b[2]; } else { if (((a[1] == b[1]) && (a[2] == b[2])) && (a[3] != b[3])) { retur..

기존의 큰 정수형 자료형이 필요할 때는 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..