본문 바로가기

알고리즘54

[백준] 17478번 문제출처: https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀함수가 뭐냐고 묻는 횟수만큼 이야기 보따리 하나를 풀며 마지막에 답변해주는 재귀함수 자동봇(?)이다. 함수 내에서 자기 자신을 호출하는 함수(횟수+1)을 하면 반복문 i++의 효과를 낼 수 있다. 그리고 재귀함수를 종료할 때는 최종으로 출력된 재귀함수부터 역순으로 종료한다. ​ 어디서 많이 본 구조같은 이야기다. 선입후출(FILO)이다. FILO의 대표적인 자료구조는 stack! .. 2022. 6. 15.
[백준] 17298번 문제출처: https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수는 선택중인 숫자 X보다 오른쪽에 있으면서 X보다 큰 수 중 가장 왼쪽에 있는 수를 의미한다. 그런 수가 존재하지 않을 때는 -1을 출력한다. ​ -1을 출력하게 되는 경우는 두 가지다. 1) 맨 오른쪽의 숫자(마지막 번째 숫자)일 때 2) 오른쪽에 있는 숫자중에 X보다 큰 숫자가 없을 때 말을 따지고보면 1이 2에 포함되는 것처럼 보일 수 있다. 하지만 i와 i+1을 비교한다는 점에서 i+.. 2022. 6. 15.
[백준] 2460번 문제풀이: https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 브론드 단계지만 초짜 시절의 나였다면 대강 표 자체를 보고 지레 겁먹으며 뒤로가기를 누를 수도 있었을 문제다. 하지만 정해진 규칙이 매우 많기 때문에 쉽게 풀 수 있다. ​ 기차가 10 정거장에서 멈추는데, 그 사이 승객이 내리고 타는 숫자를 알려준다. 승객이 가장 많이 탄 순간의 승객 수를 출력해주면 된다. 10 정거장이라고 했으므로 for문에서 10번 반복해주면 뚝딱! ​ 처음.. 2022. 6. 15.
[백준] 25191번 문제출처: https://www.acmicpc.net/problem/25191 25191번: 치킨댄스를 추는 곰곰이를 본 임스 콜라 $4$개, 맥주 $2$개로 치킨을 $4$마리까지 먹을 수 있지만, 치킨집에 치킨이 $3$마리밖에 없으므로 임스도 $3$마리까지만 먹을 수 있다. www.acmicpc.net 문제 내용은 대략 이렇다. 치킨집에서 시킬 수 있는 치킨 수 N이 주어지고, 집에 있는 콜라와 맥주의 개수가 각각 A,B로 주어진다. ​ 치킨을 먹기 위해서는 두 가지 조건 중 적어도 한 조건을 만족해야 한다. 첫째, 치킨 한 마리당 콜라 두 개를 마실 것. 둘째, 치킨 한 마리당 맥주 한 캔을 마실 것. ​ or이기 때문에 두 조건을 더하기를 하면 된다. 만약 콜라가 4개, 맥주가 2개 있으면 콜라 2.. 2022. 6. 15.
[프로그래머스] 59413번 문제출처: https://programmers.co.kr/learn/courses/30/lessons/59413 코딩테스트 연습 - 입양 시각 구하기(2) ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 programmers.co.kr 입양 보낸 동물들의 정보를 담은 테이블 'ANIMAL_OUTS' 내에서 HOUR(1시간 간격)에 따라 입양된 동물의 수를 count하는 문제다. 하지만 테이블 구조 내에는 HOUR이 없다. 대신 연도, 월, 일, 시, 분이 기입된 DATETIME이 있.. 2022. 6. 15.
[백준] 1463번 문제출처: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 주어진 숫자 X를 1로 만드는 데 연산을 사용하는 횟수의 최솟값을 출력하는 문제다. 연산은 세 가지만 사용할 수 있다. 1) X가 3의 배수면 3으로 나눈다. 2) X가 2의 배수면 2로 나눈다. 3) 1을 뺀다. ​ 처음에는 우선순위를 두고 그리디 방법으로 풀었더니 오답이 나왔다. 질문란에 가니 나같은 사람이 많았다 ^_ㅠ... 반례에 대한 질문의 답을 보니 3k+1 꼴일 때, 1을 빼고 3으로 나누는데 2로 나누는 것보다 항상 적게 걸린다고 할 수 없기 때문이라는 듯하다. 반례가 참 많았다.. 따.. 2022. 6. 15.

티스토리툴바