렝무식

BOJ - [10773] 제로 🖍 숫자를 저장하고 0을 부르면 이전 숫자를 지운다. 이후에 숫자들을 합한 값을 출력하는 문제 (link) 10773 제로 [풀이 과정] 스택을 사용하는 문제다. 스택은 대표적인 후입선출(LIFO) 자료구조이므로 해당 문제를 아주 쉽게 해결할 수 있다. 0이 아닌 수를 부르면 그대로 저장하고, 0을 부르면 저장하지 않고 스택 맨 위에 있는 값을 빼는 식으로 진행한다. 그렇게 수가 걸러지면 stack에는 유효한 숫자들만 남아있게 된다. 스택 최상단 값을 반환하는 peek와 스택 최상단 값을 삭제하는 pop 메소드로 차례차례 스택에서 값을 꺼내 값을 합하면 되겠다. [Pseudocode] 1. stack 선언 2. 테스트 케이스 개수 k 선언 3. stack에 저장할 정수형 변..

BOJ - [2581] 소수 🖍 M부터 N까지의 소수를 찾고, 그 소수들의 합과 그 중 최소값인 소수를 출력하는 문제 (link) 2581 소수 [풀이 과정] 소수를 판별하는 가장 효율적인 방법을 두고 다른 방법을 써서 풀었기 때문에... 나중에 수정해서 다시 풀어야 할 것 같다. 우선 개념 설명 먼저하겠다. 소수란 1과 자기 자신만을 약수로 가지는 자연수이다. 0과 1은 소수가 아니며, 2를 제외한 짝수들은 모두 약수로 2를 가지기 때문에 소수가 아니다. 소수를 판별하는 방법은 총 세 가지이다. 1부터 N까지 수 중에서 소수를 찾고 있다고 가정하고 이야기하겠다. 소수는 1과 자기 자신만을 약수로 가진다. 따라서 N보다 작은 자연수로 모두 나누어볼 때 나누어 떨어지는 경우가 있으면 N은 소수가 아니게 된..

BOJ - [17478] 재귀함수가 뭔가요? 🖍 챗봇의 응답을 재귀적으로 출력하는 문제 (link) 17478 재귀함수가 뭔가요? [풀이 과정] 정말.. 재밌는 문제같다. 근데 확실히 재귀라는 개념을 단번에 이해할 수 있는 문제이기도하다. 일단 함수안에 문장을 그대로 적으면 복잡해보일 것 같아서 문장들을 따로 String 변수에 저장했다. 이때 주의할 점은 출력에서 재귀 단계에 따라 언더바를 4개씩 추가하여 출력해주어야 하기 때문에 언더바가 시작하는 문장마다 따로 저장해야 한다. (이를테면 "잘 들어보게." 부터 "한 선비가 찾아와서 물었어." 까지는 한 문장 같지만 엔터처리되는 부분마다 언더바가 들어가므로 세 변수에 따로 저장한다) 물론 이렇게 하지 않아도 분명 다른 방법이 있긴 할 거다. 재귀함수에서..

BOJ - [10872] 팩토리얼 🖍 주어진 정수의 팩토리얼을 구하는 문제 (link) 10872 팩토리얼 [풀이 과정] 팩토리얼이라는 개념은 배운지 엄청 오래된 것같다. 중학교인지 고등학교인지 .. 아무튼 내가 CS공부한지 얼마 안됐을 때 솔직히 뭔지 기억안나서 찾아봤다. 팩토리얼도 재귀를 통해 구할 수 있다. 물론 재귀로 구할 수 있으면 반복문으로도 구할 수 있다. 그런데도 굳이나 어려운 재귀를 사용하는 이유는 직관적이고 구현이 간단하기 때문 n! = 1 * 2 * 3 * ... * n n을 1씩 더해주면서 곱하게하면 되겠다.. 싶겠지만 재귀를 사용할 것이기 때문에 거꾸로 n에서 1씩 뺀 값을 곱해줄 것이다. 종료 조건은 n이 1이 되었을 때이다. n이 1이 되면 1을 반환한다. else문에서는 별다..

BOJ - [10829] 이진수 변환 🖍 주어진 10진수를 2진수로 변환하여 출력하는 문제 (link) 10829 이진수 변환 [풀이 과정] 테스트 케이스 N의 최대값이 10조나 되는 문제다. 때문에 int타입으로 받으면 안되고, long 타입으로 입력을 받으면 된다. --참고-- int타입의 범위 : -2,147,483,648 ~ 2,147,483,647(약 21억) long타입의 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807(약 922경) 아무튼 2진수로 변환하는 문제는 재귀로 구현가능하다. 재귀 구현에 대하여 간단하게 설명하자면, 반환 값으로 메소드 자신을 호출하여 반복하게끔 하는 것이다. 때문에 무한 반복을 막기 위한 종료 조건이 꼭 필..

BOJ - [4153] 직각삼각형 🖍 입력으로 세 변의 길이가 주어지면 해당 변으로 이루어지는 삼각형이 직각삼각형인지 판별하는 문제 (link) 4153 직각삼각형 [풀이 과정] 중학교 수준의 수학 문제. 요즘은 초등학교 고학년들이 알지도 모른다. 내가 아무리 수포자라지만 피타고라스 정리를 모를 정도는 아니다. 지금 이 글을 보고 있는 사람이라면 이정도 수학 지식을 모를리가 없기 때문에 바로 코드로 구현해보겠다. 우선 세 변의 길이를 저장하기 위해 크기 3의 배열을 선언한다. 그리고 이 문제에서는 테스트 케이스 개수가 주어지지 않았기 때문에 while문을 이용하여 0 0 0 이 주어질 때까지 반복하게끔 한다. (do while문을 써도 괜찮을까? 일단 나는 while문의 조건을 true로 설정한 뒤 wh..

BOJ - [3009] 네 번째 점 🖍 점 세개의 좌표가 입력되었을 때, 축에 평행한 직사각형을 만들기 위한 마지막 점의 좌표를 출력하게 하는 문제 (link) 3009 네 번째 점 [풀이 과정] 직사각형의 좌표 특징을 우선 살펴본다. 여러가지 풀이 방법이 있겠지만, 내가 찾은 규칙은 다음과 같다. 좌표 네 개가 주어지고, 각각 x와 y좌표를 나누어 봤을 때 같은 숫자가 두 번 씩 나오면 직사각형을 이룬다. 무슨 말인지 자세히 알아보기 위해 테스트케이스 하나를 예시로 들어보겠다. (5, 5) (5, 7) (7, 5)라는 테스트 케이스가 주어졌다고 가정한다. 4분면 위에 점을 찍어보면 나머지 점 하나의 좌표는 (7, 7)이라는 것을 금방 알 수 있다. 우선 세 좌표를 x와 y로 나누어서 써보면 x = 5,..

BOJ - [2869] 달팽이는 올라가고 싶다 🖍 A미터 올라가고, B미터 미끄러지는 달팽이가 V미터의 나무 막대를 올라가는데 며칠이 걸리는지 구하는 문제 (link) 2869 달팽이는 올라가고 싶다 [풀이 과정] 시간 제한이 0.15초인 문제이다. 한마디로 노가다로 구하는 알고리즘은 소용 없고, 공식을 구해서 풀라는 의미 처음에 반복문으로 A올리고 B내리고 해서 구했다가 시간 초과 당했다. 그리고 이 문제는 제대로된 식을 구해도 시간 초과가 뜨는데, 언어를 java 11이 아니라 java 8로 설정해야 풀린다. 아무튼 공식 먼저 이야기 하자면 (V-A)/(A-B)+1 이라고 쓸 수 있다. 우선 총 거리인 V에서 올라갈 수 있는 거리 A를 빼준다. (마지막 날에 A만큼 한 번 올라간다면 무조건 도착할 수..

BOJ - [1316] 그룹 단어 체커 🖍 각 문자가 연속해서 나타나는 단어인 '그룹 단어'의 개수를 출력하는 문제 (link) 1316 그룹 단어 체커 [풀이 과정] 그룹단어가 무엇인지는 문제에 잘 나와있으니 설명은 생략하겠다. 이 문제는 이전에 풀었던 1157번 문제인 단어 공부 문제의 풀이를 응용할 수 있다. 단어 공부 문제를 풀 때 알파벳을 아스키 코드 값으로 변환하여 배열에 넣어주는 방식을 사용했고, 여기서도 그 방식을 사용할 것이다. (여기서는 입력 형태가 소문자로 주어지기 때문에 소문자 a의 아스키 코드 값인 97의 뺄셈 연산을 이용한다) 그룹 단어가 몇 개인지 체크하기 위해 그룹 단어가 '아닌' 단어의 개수를 저장할 정수형 변수 count를 선언한다. (연산의 편의를 위하여 그룹 단어가 아..

BOJ - [2775] 부녀회장이 될테야 🖍 주어진 조건에 맞게 입력된 k층 n호에 사는 인원을 구한 뒤 출력하는 문제 (link) 2775 부녀회장이 될테야 [풀이 과정] 배열을 사용한 다이나믹 프로그래밍(DP) 문제. 다이나믹 프로그래밍이 뭔지 간단하게 설명하자면, 이전에 구해두었던 값은 다시 계산할 필요 없이 이전의 값을 활용할 수 있게끔 하는 기법이다. 일단.. 문제를 읽으니 단번에 이해가 안된다. 무슨 내용인지 먼저 설명하겠다. 0층부터 14층, 1호부터 14호까지 있는 아파트다. 0층에 사는 사람은 1호에 1명, 2호에 2명.... 14호에 14명이 산다. 1층 부터는 아래 층 호수까지의 사람들을 합산한 인원이 해당 호수에 살아야 한다. 말로 설명하면 무슨 말인지 이해가 잘 안되는데 순서대로 ..