Algorithm
-
3/2기록 - 백준 9655Algorithm 2022. 3. 2. 15:20
오늘의 문제는 돌 게임 문제이다. 문제를 처음 읽어보았을때 돌을 1개 or 3개 가져갈 수 있으면 그 경우를 나누어서 따지고 경우에 맞게 해결을 해야 하는 건가 하면서 굉장히 복잡할 것 같다는 생각을 했다. 문제를 경우를 따지면서 풀다보니 문득 든 생각이 1개 or 3개라면 그냥 홀수인 경우 전부를 조사하면 된다는 생각이 들었다. 알고리즘 생각 1 or 3은 N%2 == 1인 경우이므로 이렇게 홀수가 나오게 되는 경우 먼저 게임을 시작한 상근이 승리, 짝수라면 창영이 승리 이렇게 해결을 할 수 있었다. 홀, 짝 눈치만 챌 수 있었다면 정말 간단하게 문제를 해결할 수 있는 문제였다. 너무 쉽게 문제를 해결한 지라 한 문제를 더 풀어보았다. -->>> 이어서...
-
2/28 기록 - 백준 9237Algorithm 2022. 2. 28. 11:25
개강을 앞두고 앞으로 꾸준히 문제풀이를 할 수 있을지 모르겠지만, 오늘은 문제를 하나 풀어보았다. 백준 9237번 이장님 초대 문제이다. 문제를 처음에 이해하기가 꽤 어려웠다. 예제 입력2에서 특히 헷갈렸는데, 어디서 갑자기 42일이 나온건지 의문이 들었다. 최대한 이장님을 빨리 초대해야 하지만, 모두 다 심어 져야 하기 때문에, 정렬 후 MAX값을 구하는 문제로 받아들이면 된다. 문제부터 이해를 해보자. 예제 입력2에서 가장 빨리 이장님을 부르기 위해서는 오래 걸리는 묘목을 먼저 심어야 한다. 그렇다면 1일 2일 3일 4일 5일 6일 39 39 38 35 20 9 이런식으로 되면, 39일 걸리는 묘목을 1일째에 심고, 사는데 1일을 더하면 41일이 걸린다. 두번째 날 : 39일 + 2일 + 1일 = 4..
-
2/24기록 - 백준 7785Algorithm 2022. 2. 24. 09:27
오늘의 문제는 백준 7785문제 회사에 있는 사람이다. 그냥 문제는 간단하다. enter면 회사로 들어가고, leave면 회사로 나오게 되는데 회사로 들어가서 안나온 사람을 찾아서 이름을 사전순의 역순으로 출력시키면 된다. 이 문제의 핵심은 문제에 써진 "동명이인이 없으며" 라는 문구이다. 이 문구에서 Set이나 Map을 사용하면 되는것을 빠르게 캐치하는 것이 문제의 가장 큰 keyPoint라고 할 수 있다. 알고리즘 생각 1. Set 안에서 enter라면 add, leave라면 remove 시킨다. 2. Set은 정렬이 안되므로 List에 담아서 Collections.sort를 이용하여 정렬시킨다. 3. 개선된 for문을 사용하여 value값으로 List를 담아서 출력시킨다. 이렇게 해결할 수 있었다...
-
2/23기록 - 백준 4796Algorithm 2022. 2. 23. 12:53
코로나 시국으로 인해 캠핑도 애매해진 상황에 제목이 캠핑이라는 문제가 하나 있길래 풀어보았다. 백준 4796번 캠핑 문제이다. 처음에 문제가 무슨 소리를 하는 건지 잘 이해를 하지 못했다. 그래서 입력 예시를 가지고 하나하나 분석해 보았다. L=5, P=8, V=20 예시를 가지고 문제를 분석해 보자. 20일짜리 휴가를 8일로 나누면 총 2번하고 4일이 나오게 된다. 그렇다면 한번에 5일씩 캠핑을 갈 수 있으니 2번*5일 + 4일 = 14일이 된다. 이것을 식의 형태로 나타내 보면, (V/P) * L + V%P 로 나타낼 수 있다. 여기서 주의할 점이 한가지 있는데, 뒤에 남는 4일이 한 번에 갈 수 있는 일수인 5일 보다 작은 경우와 큰 경우로 나뉠 수 있다. 만약 V=22라면 뒤에 남는 일수는 6일이..
-
2/22기록 - 백준 1476Algorithm 2022. 2. 22. 08:59
오늘은 백준 1476번 날짜 계산 문제이다. 문제 이해는 굉장히 간단한데, 그냥 E,S,M의 범위를 넘어서면 다시 1로 바뀌어 나타나게 되는데 연도는 누적이 되어 몇년을 구하는 프로그램인지를 출력하면 된다. 문제를 이해는 했는데, 알고리즘이 바로 떠오르지는 않았다. 연도가 넘어가면 다시 e,s,m에 1을 넣어주자. 이것만 생각이 나서 한동안 고민을 했다. 알고리즘 생각 1. E,S,M을 입력받는다. 2. 초깃값이 1인 e,s,m을 선언해준다.(e,s,m으로 모두 컨트롤할 것) -> 이 부분에서 시간이 좀 걸렸다. 3. while(true) 문으로 반복문을 만들어준다. 4. 계속, e++, s++, m++ 시켜주다가 e=16, s=29, m=20이 되는 지점에서 다시 e,s,m에 각각 1을 대입시켜 바꿔준..
-
2/21기록 - 백준 1969Algorithm 2022. 2. 21. 10:16
주말 내내 바쁜일들이 많아서 쿨하게 알고리즘 문제풀이를 패스했다... 이러면 안되는데 ㅠㅠ 곧 개강이라 더 바쁠텐데... 휴~ 각설하고 오늘의 문제는 백준 1969번 DNA문제이다. 문제를 이해하기 어려울 수 있는데, N개의 M개 뉴클레오타이드로 구성된 DNA구조를 입력받는다. 그리고 각 인덱스마다 비교하여 가장 많이 나온 문자가 기준 문자가 된다. 이렇게 했을 때 사실상 대부분 기준문자로 이루어진 DNA구조가 Hamming Distance가 가장 작은 DNA가 될 것이므로, max값을 구해야함을 알 수 있다. 그리고 마지막에 모든 DNA의 Hamming Distance의 합을 구하면 된다. 구하는 것이 두 개 이므로 두 구역으로 나누어 생각하면 조금 더 간단할 수 있을것이다. 나는 구역을 총 3개로 끊..
-
2/18기록 - 백준 1316Algorithm 2022. 2. 18. 09:36
오늘은 어제 공부한 알고리즘이 좀 어려웠기 때문에 기분 좋게 백준 실버 5문제를 풀어 보았다. 백준 1316번 그룹 단어 체커 문제이다. 문제를 이해하기는 쉽다. 문자열에서 이전 문자와 같은 문자가 이어서 나오면 그룹을 형성할 수 있고, 다른 문자가 나왔을 때 이전에 해당 문자가 나오지 않았다면 문자 하나라도 그룹으로 체크할 수 있다. 이렇게 문자열 하나를 모두 조사해서 그룹으로만 형성 되었다면 해당 단어를 그룹 단어로 판단 가능하다. 그런 문자가 몇 개 인지를 파악하는 문제이다. 알고리즘 생각 사실상 문제를 설명 하면서 거의 문제의 핵심을 말했다고 해도 과언이 아니다. 1. 단어를 체크할 boolean 함수를 하나 만들고, 해당 함수가 true이면 count++ 시켜준다. 2. 함수 안에서 문자열을 입..
-
2/17기록 - Programmers 타겟넘버(dfs문제)Algorithm 2022. 2. 17. 09:29
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 ..