Algorithm
-
2/16기록 - 백준 1018Algorithm 2022. 2. 16. 09:57
체스판 문제 시리즈로 백준 1018문제를 이어서 포스팅 해보려 한다. 솔직히 엄청 쉬울 줄 알았는데, 이전 1100번 문제는 8*8 배열만으로 해결이 되는 문제였던 반면, 이 문제는 입력 사이즈의 배열에서 8*8배열을 만들고 그 안에서 잘못 놓여진 문자의 최소 개수를 찾아내어야 해서 제법 까다로웠다. 일단 경우의 수를 생각할 수 있어야 하는데, 10*10 의 경우를 생각해 보자, 여기서 생길 수 있는 8*8 정사각형 개수를 세어보면 9가지가 나오는 것을 알 수 있다. 9*9는 4가지가 나온다. 이를 토대로 공식을 세워 볼 수 있는데, 입력할 수를 N, M이라고 했을 때, 총 (N-7) * (M-7)의 경우의 수가 나오는 것을 알 수 있다. B와 W가 1100번 문제와는 다르게 지정된 값이 없으므로 교차될..
-
2/16기록 - 백준 1100Algorithm 2022. 2. 16. 09:24
며칠간 스키장을 다녀오면서 코딩 공부를 못했다. 그래서 오늘은 꼭 해야지라는 생각으로 알고리즘 문제를 풀어보았다. 체스 문제를 2개 풀어보았는데, 백준 1100문제부터 포스팅 해보려 한다. 체스판 8*8 안에서 하얀칸과 검정칸을 구분하고 하얀칸에 F가 있으면 카운팅해주면 되는 문제이다. 체스판이 (0,0)에서 하얀판으로 시작한다고 문제에서 조건을 주었으므로, 다음줄 (1,0)은 검정판부터 시작하게 된다. 이러한 원리를 따라 가보면 (0,0),(0,2),(0,4) ... (1,1),(1,3),(1,5) ... (8,8) 이런식으로 (x,y)의 경우 x+y가 짝수의 경우만 하얀칸이 위치하게 된다는것을 알수 있다. 알고리즘 생각 1. 체스판을 선언하기 위해 8*8 이차원 배열을 String type으로 선언한..
-
2/11기록 - 백준 2581Algorithm 2022. 2. 11. 10:03
오늘의 문제는 백준 2581번 소수 문제이다. 소수 문제는 기본적인 알고리즘을 에라토스테네스의 체 라는 수학적 알고리즘을 가지고 있는 것을 전공자라면 학교 과제를 통해서 알고 있는 사람들이 많을 것 같다. 각설하고 문제로 들어가 보자. 문제는 간단하다. M과 N 사이의 소수의 합과 최솟값을 출력하면 되는 문제이다. 알고리즘 생각 1. 소수는 에라토스테네스의 체로 구하면 되는데, 이 때 M과 N 사이의 값이므로 for문을 한 번 더 걸어주어야 함 2. 소수 prime 변수가 true일 때(소수 일 때) sum 변수에 반복문안에서 합을 구해준다. 3. List 안에 구해진 소수를 담아주고 min 변수에 list의 제일 처음 값을 담아준다. 그게 최솟값이다. 4. 만약 소수가 없을 때(합이 0이거나 최솟값이 ..
-
2/10 기록 - 프로그래머스 2020 Kakao 인턴쉽 level3 보석쇼핑Algorithm 2022. 2. 10. 10:11
알고리즘 스터디원들과 진행한 어젯밤 스터디에서 풀어본 문제인데, 어젯밤에 해결하기 힘들어서 오늘 다시 진행해 보았다. 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매 예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다. ..
-
2/9기록 - 백준 1934Algorithm 2022. 2. 9. 10:17
오늘은 교육이 있어서 아침에 급하게 문제를 하나 풀어보기 위해서 그래도 익숙한 문제를 하나 선정했다. 오늘의 문제는 최소공배수 문제이다. 최소공배수는 해당 두개의 값을 곱하고 최대공약수로 나누어 주면 간단히 해결할 수 있다. 하지만 최대공약수를 구할 때 알고리즘을 생각하지 않으면 굉장히 험난한 길을 갈 수도 있다. 중딩때 경시대회 준비를 하면서 배웠던 유클리드 호제법을 아직도 최대공약수 구할 때 익숙하게 사용했었는데, 유클리드 호제법을 사용하면 최대공약수를 컴퓨터 언어로도 굉장히 쉽게 풀어낼 수 있다. 출처 : 위키백과 위키 백과에 유클리드 호제법을 잘 설명해 두어서 가져와 보았다. a와 b의 최대공약수를 (a,b)라 하면 (a,b) = (b,r) 로 표현하여 r 나머지가 0이 될 때까지 계속 나누어 준..
-
2/7기록 - 백준 2941Algorithm 2022. 2. 7. 17:19
요즘 Kotlin기반의 Android Studio 프로그래밍과 앱인벤터를 활용한 앱 제작을 공부중이라 상당히 빠듯하지만 이건 좀 갖추어졌다 할 때 포스팅 하기로 하고 짬을 내어 푼 문제를 포스팅 하려 한다. 오늘의 문제는 백준 2941 크로아티아 알파벳 문제이다. 문제는 이러하다. 처음 문제를 읽으면 외계문자같은 것들에 당황하여 가독성이 상당히 떨어진다. 나도 세번 정도 반복해서 읽으니 무슨 말인지 알 것 같았다. 따지고 보면 상당히 쉬운데, 표 안의 크로아티아 문자들을 다른 문자로 나타내어 총 크로아티아 문자가 몇개나 사용되었는지 체크하는 프로그램을 구현하는 것이다. 알고리즘 생각 1. c=, c-, dz=, d- 등을 통해 "=","-" 일 때를 chatAt()과 equals 메소드를 사용하여 다 나..
-
2/6기록 - 백준 7568Algorithm 2022. 2. 6. 11:58
오늘은 실버 5단계의 백준 7568번 덩치 문제를 풀어보았다. 문제는 이러하다. 몸무게와 키를 입력받아 비교하여 몸무게와 키가 더 큰 사람만 덩치가 크다고 간주한다. 그리고 덩치가큰 사람이 자신 보다 몇명있는지를 계산하여 등수로 인식한다. 문제를 보고 처음에 key-value쌍인가 하여 Map? 이라고 생각을 잠시 하였는데, 다 읽고 보니 그냥 브루트 포스법으로 완전탐색을 해주면 되는 문제였다. Map은 너무 간것 같다. ㅋㅋㅋ 알고리즘 생각 1. 키와 몸무게를 담을 이차원배열을 선언하고, 모두 입력을 받는다. 2. 0열에는 몸무게, 1열에는 키를 담는다. 3 이중 for문 안에서 result 변수를 1로 초기화 해두고 해당 행과 다음 행을 비교하는데 만약 키와 몸무게가 모두 크다면 result 변수를 ..
-
2/4기록 - 프로그래머스 두 개 뽑아서 더하기Algorithm 2022. 2. 4. 09:40
오늘은 카카오 2019 블라인드 테스트 level4의 무지의 먹방 라이브를 풀다가 뇌정지가 와버려서 잠시 두고 다른 문제를 풀어보았다. 문제 설명 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 입출력 예numbersresult [2,1,3,4,1] [2,3,4,5,6,7] [5,0,2,7] [2,5,7,9,12] 입출력 예 설명 입출력 예 #1 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.) 3 = 2..