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

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

이 문제 같은 경우 단순히 합산 점수가 높아서 풀 수 있는 문제가 아니였다 테스트 케이스, 지원자 수, 지원자의 서류 순위와 면접 순위가 입력된다 C++로 풀 경우 stl의 pair를 활용하면 쉽게 풀 수 있는 문제 배열 두 개를 사용할 경우 한 배열을 나머지 배열을 같은 순서로 정렬해야 하지만 pair로 두 값을 하나로 저장하면서 원활하게 구현할 수 있었다 우선 서류 순위를 정렬한다 서류 순위는 비교할 필요가 없으므로 순차적으로 면접 순위를 비교하여 다른 면접자들의 점수보다 높을 때 count를 늘리고 최고 값을 갱신한다 // baekjoon 1946 #include #include #include using namespace std; // codes for fast I/O void init(){ ci..

그리디 알고리즘 문제는 코드 자체가 길진 않았다 다만 어떻게 구현해서 정확한 값을 도출할 지가 관건이다 DFS, BFS 에 대한 스터디를 진행하지 않아 조금 찾아보고 풀어 본 문제 두 수를 입력 받고 n을 m으로 바꾸기 위해 가능한 연산은 두 가지 2를 곱하거나 ,1을 수의 가장 오른 쪽에 추가한다 이 말은 즉 곱하기 10 더하기 1이다 처음에는 n을 m으로 바꿀 방법을 모색하다가 경우의 수를 둬서 풀었을 때 while 문 두 번에 시간 초과가 뜰 것 같아 m에서 n을 접근하는 방법으로 변경했다 위 두 가지 연산을 반대로 하면 2를 나누거나, 10을 나누는 것이다 10을 먼저 나누는 것이 변경 횟수가 줄어드므로 10을 먼저 나눈 후, 2를 나눌 수 있는지 여부를 확인한다 만약 두 수로 나눌 수 없거나 애..