본문 바로가기
반응형

컴퓨터/알고리즘26

[Java] 백준 1253 좋다 (자료구조1,투포인터) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net [문제분석] 주어진 연속된 수를 더하며 문제를 풀어야 하므로 투포인터 사용 + 입력값(도달해야 할 값) 이 계속 변하는 문제 [진행순서] 1. 투포인터 로직 작성 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeniz.. 2023. 10. 2.
[Java] 백준 2810 수들의 합 5 (자료구조1,투포인터) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한www.acmicpc.net [문제분석]연속된 수를 더해야 하므로 합배열을 이용할 수도 있지만입력값이 1~10,000,000 이므로 시간초과 될 수도 있음.따라서 시간복잡도를 줄일 수 있는 투포인터를 사용 [진행순서]1. 투포인터 로직 작성    1-1 연속합, 시작index, 끝index, 정답 선언    1-2 연속합이 입력값 N 과 같으면 정답+1, 연속합, 끝index 변경    1-3 연속합이 입력.. 2023. 9. 27.
[Java] 백준 11660 구간 합 구하기 5 (자료구조1,구간합/합배열) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [문제분석] 특정 인덱스 구간의 2차원 배열 데이터들을 전부 더해야 하므로 합배열을 이용한 구간 합 알고리즘을 사용해야 한다. [진행순서] 1. 배열크기, 문제개수 입력받기 2. 입력받았던 배열 크기만큼 2차원 배열 데이터 입력하기 3. 입력한 배열로 2차원 합 배열 구하기 3. 입력받았던 문제 개수만큼 2차원 구간합 출력 import java.io.Bu.. 2023. 9. 22.
[Java] 백준 11659 구간 합 구하기 4 (자료구조1,구간합/합배열) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [문제분석] 특정 인덱스 구간의 배열 데이터들을 전부 더해야 하므로 합배열을 이용한 구간 합 알고리즘을 사용해야 한다. [진행순서] 1. 데이터개수, 문제개수 입력받기 2. 입력받았던 데이터 개수만큼 합배열 선언 3. 입력받았던 문제 개수만큼 구간합 출력 import java.io.BufferedReader; import java.io.IOException; import j.. 2023. 9. 1.
[Java] 백준 11720 숫자의 합 (자료구조1) https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net [문제분석] - 입력 중심으로 분석한다. 숫자 개수가 1부터 100개이기 때문에 숫자형 자료형 사용 불가. [진행순서] 1. 첫번째 숫자개수 입력받기 2. 두번째 숫자 String 으로 입력받기 3. 두번째 숫자를 char[] 에 넣기 -> int[] 안쓰는 이유는 toCharArray 쓰려구.. 4. [] 길이만큼 반복해서 더하고 출력하기 [문제풀이] import java.util.Scanner; public class Main { /* * [백준 11720] * 문제: N개의.. 2023. 8. 31.
[Java] 선형검색 보초법 자바 코드 예시 알고리즘 보초법(Sentinel Search) 보초(sentinel)라는 특별한 값을 사용하여 검색 성능을 개선하는 방법. 보초값 찾아야 하는 값 보초법 구현 방법 배열의 마지막 요소에 임시로 보초값을 추가하고 검색을 마친 후에 배열을 원래 값으로 복원하는 방식으로 이루어짐 + 자바같은 경우는 배열 길이를 늘릴 수 없기 때문에 (ArrayList 로 구현하는 방식 제외) 기존 끝 값을 보초값으로 변경 -> 탐색 -> 다시 원래 배열로 돌리는 방식으로 탐색 보초법 구현 순서 1. 보초값 설정 (찐배열 > 짭배열) 2. 짭배열에서 찾을 값 찾아서 위치 저장 3. 찾을 값 찾으면 배열 돌려놓기 (짭배열 > 찐배열) 4. 위치 찾았는지 판단 코드 예시 import java.util.Scanner; public .. 2023. 8. 12.
[Java] 선형 검색 알고리즘 예시 코드(linear search) import java.util.ArrayList; import java.util.Scanner; public class LinearSearch { public int 인덱스알려줌(ArrayList 배열, int 찾을값){ for (int i = 0; i 2023. 8. 12.
[백준] 17478번 재귀함수가 뭔가요? 문제풀이 (python) 문제 링크 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net python 풀이 def 재귀가모임(m): print("_" * (4 * (a - m)) + '"재귀함수가 뭔가요?"') # if not m: if m == 0: print("_" * (4 * (a - m)) + '"재귀함수는 자기 자신을 호출하는 함수라네"') print("_" * (4 * (a - m)) + "라고 답변하였지.") return print("_" * (4 * (a -.. 2022. 8. 6.
[재귀함수] 재귀함수 뜻과 python예시, maximum recursion depth 스택 구현 (1) 재귀함수 Recursion Function 재귀함수가 모냐면은 자기 자신을 다시 호출하는거에여 재귀함수 예시 이게 대표적인 재귀함수에여 def 재귀함수(): print('재귀인거시야') 재귀함수() 재귀함수() 재귀함수 안에 재귀함수가 있죠 파이썬은 기본적으로 최대 재귀 깊이 제한이 있어서 중간에 막혀여 오류뜬다는 소리져 오류가 왜뜨냐면 바닥이 드러나서입니당 count 로 몇번만에 바닥이 드러나는지 확인해보께여 count = 0 def 재귀(): global count print(count, '번째 재귀인거시야') count += 1 재귀() 재귀() 997번째에서 나네여 (0부터 시작합니당) RecursionError: maximum recursion depth exceeded while calling.. 2022. 8. 5.
[백준] 2747번 피보나치 수 문제풀이(python) 문제링크: https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net python 풀이 memo = [0] * 50 def 피(n): if n == 0: return 0 elif n == 1: return 1 elif memo[n]: return memo[n] memo[n] = 피(n - 1) + 피(n - 2) return memo[n] a = int(input()) print(피(a)) 2747번 문제는 일반적인 재귀함.. 2022. 8. 1.
[백준] 10872번 팩토리얼 문제 풀이 (python) 문제 링크: https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net python 풀이 def 재귀팩토리얼(n): if n 2022. 7. 31.
[프로그래머스] Lv1 시저 암호_python 문제 풀이 출처 https://programmers.co.kr/learn/courses/30/lessons/12926 문제 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a" s는 알파벳 소문자, 대문자, 공백이고, 공백은 아무리 밀어도 공백 입출력예시 "AB" "z"' "a B z" 문제풀이1 def solution(s, n): sentense = s answer = "" 대문자 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 소문자 = "abcdefghijklmnopqrstuvwxyz" for i in range(len(sentense)): if sentense[i] in.. 2022. 7. 9.
[프로그래머스] Lv1 가운데 글자 가져오기_python 문제 풀이 출처 https://programmers.co.kr/learn/courses/30/lessons/12903 문제 단어 s의 가운데 글자를 반환하는 함수 단어의 길이가 짝수라면 가운데 두글자를 반환 입출력예시 "abcde" "qwer" 문제풀이1 def solution(s): 길이 = len(s) if 길이 %2 ==0: return s[길이//2-1]+s[길이//2] elif 길이 %2 ==1: return s[길이//2] 2022. 7. 8.
[프로그래머스] Lv1 이상한 문자 만들기_python 문제 풀이 출처 https://programmers.co.kr/learn/courses/30/lessons/12930 문제 각 단어는 하나 이상의 공백문자로 구분 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다. 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다. 입출력예시 "try hello world" 문제풀이1 def solution(s): arr = [] word_index = 0 for i in range(len(s)): if s[i] == ' ': word_index = 0 arr.append(s[i]) elif word_index % 2 == 0:.. 2022. 7. 7.
[프로그래머스] Lv1 콜라츠 추측_python 문제 풀이 출처 https://programmers.co.kr/learn/courses/30/lessons/12943 문제 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다. 1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성하라 단 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1 입출력예시 문제풀이1 def solution(num): count = 0 while n.. 2022. 7. 6.
반응형

티스토리툴바