Priceless

3차원으로 접근하는 BFS 문제 3차원으로 접근해야 하므로 움직이는 방향 또한 x축, y축, z축에 맞게 설정한다 BFS를 진행한 후 모든 토마토를 검사했을 때 0이 있다면 -1을 출력하고 즉시 종료한다 테스트 케이스는 1회이므로 별도의 방문 여부 기록과 reset함수를 구현하지 않았다 크기의 제한이 있어서 그런가 생각보다 시간을 많이 소요되진 않았다 // baekjoon 7569 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[101][101][101]; //bool visited[..

그래프 탐색은 너무 가혹합니다.. 어제는 DFS를 통해서 문제를 풀었다면 오늘 문제는 BFS를 사용하여 푸는 문제다 BFS는 큐를 사용해야 하기 때문에 나이트의 이동이 저장된 배열, 방문 여부 배열, 방문할 큐, 방문 가능한 방향을 가진 배열 총 4가지 구조체를 사용하여 문제를 풀어야 한다 나이트의 이동이 저장된 배열에는 나이트가 가능한 방향 만큼 한 번씩 이동하고 이동한 자리에는 이동한 횟수가 저장된다 과정을 반복하여 목표 자리에 도착했을 때 도착할 때까지 이동한 횟수를 출력한다 큐에는 방문할 좌표가 저장되어 있으며 저장한 후에는 pop을 통해 빼는 방식이다 // baekjoon 7562 #include #include #include #include using namespace std; // code..

어제 코테 스터디에서 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점에서 시작하여 패널티를 주는 식으로 하니까 쉽..

아마 처음으로 성공한 백준 골드 문제가 아닐까 싶다! 문제 자체는 별로 어렵게 느껴지지 않았다 다만 입력이 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); ..