본문 바로가기

IT 이야기/알고리즘22

반복문 2개로 부분 문자열 구하기 C++ / Java / 파이썬 임의의 문자열이 있을 때 부분문자열을 구하려면 어떻게 해야 할까요? 예를들어 'abcd' 라는 문자열이 있다면 부분 문자열은 a ab abc abcd b bc bcd c cd d 10개가 부분문자열입니다. 문자열의 인덱스를 0,1,2,3 이라고 생각해봅시다. 그리고 첫 인덱스, 마지막 인덱스를 반복문으로 찾는다고 생각해봅시다. 0 ~ 0 : a 0 ~ 1 : ab 0 ~ 2 : abc 0 ~ 3 : abcd 1 ~ 1 : b 1 ~ 2 : bc 1 ~ 3 : bcd 2 ~ 2 : c 2 ~ 3 : cd 3 ~ 3 : d 모양을 보니 for문을 2번 돌리고 첫 for문 i는 0부터 문자열 크기전까지 1씩 증가시키고, 두번째 for문은 j를 i로 선언해서 문자열 크기전까지 증가시키면 될 것 같습니다. 반복문.. 2023. 2. 7.

집합에서 원소 빠르게 찾기, 차집합, 합집합 알고리즘 풀이 C++ / Java / 파이썬 A라는 집합과 B라는 집합이 있습니다. 각각 집합에는 수많은 원소들이 있고 서로 겹치는 원소들을 빠르게 찾으려고 합니다. 백준 1269번 대칭 차집합 문제를 풀어보면서 집합의 속한 원소를 빠르게 찾는 방법을 알아봅시다. https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 집합 A에서 집합 B를 빼는 것을 차집합이라고 합니다. A에도 있고 B에도 있는 원소를 제거하는 것이 핵심입니다. 마찬가지로 집합 B에서 집합 A를 빼려면 같은 원소를 B에서.. 2023. 2. 7.

키, 값 자료구조 값을 빠르게 찾는 방법 C++ / Java / 파이썬 대표적인 키, 값(밸류) 자료구조인 HashMap에서 Key가 아닌 value로 데이터를 빠르게 찾을 수 있을까요? key를 해쉬하여 사용하기 때문에 해쉬되지 않은 밸류를 찾는것은 매우 어려운 일입니다. 모든 key 쌍을 다 확인해야 합니다. 하지만 조건이 적절하면 빠르게 찾는 방법이 있긴합니다. 만일 value가 중복되지 않는다면 키, 값 을 만들면서 값을 키로, 키를 값으로 한쌍을 더 만드는 것입니다. 알고리즘 대회에서 가끔 활용하는 스킬입니다. 적절한 문제인 백준 1620번 나는야 포켓몬 마스터 이다솜을 풀어보면서 확인해 봅시다. https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞.. 2023. 2. 3.

같은 데이터 빠르게 찾기 JAVA / C++ / 파이썬 Hash Map 자료구조는 key를 해싱하여 저장하고 빠르게 탐색합니다. 시간복잡도는 O(1)입니다. 자료구조에 대해 직관적인 이해를 하기 위해 적절한 알고리즘 문제를 찾았습니다. 백준 14425 문자열 집합 문체를 풀면서 Hash Map 또는 Set 자료구조에 대해 생각해 봅시다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 예제를 보면 5개의 문자열이 나옵니다. 이를 집합 S라 합니다. 그리고 11개의 문.. 2023. 2. 3.

내림차순 정렬하는 방법 JAVA / C++ / 파이썬 정렬은 기본이 오름차순입니다. 1,2,3,4,5,6... 각 언어별로 내림차순 정렬하는 방법을 쉬운 알고리즘 문제를 풀어보며 확인해봅시다. 9,8,7,6,5... https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net 백준 25305번 커트라인 문제를 풀어봅시다. 응시자의 숫자만큼 점수가 주어집니다. 몇등까지 상을 받는지 k값이 주어집니다. 문제 풀이 아이디어는 다음과 같습니다. 1) 성적을 내림차순으로 정렬합니다. 2) 배열의 k-1번 째 성적을 출력합니다. (배열은 0부터 시작이므로 1번째 성적은 a[0] 이므로 1을.. 2023. 1. 31.

좌표를 압축하는 알고리즘 JAVA / C++ / 파이썬 알고리즘 대회에서 좌표를 압축하는 아이디어는 많이 활용됩니다. 주어진 숫자를 압축해서 작은 용량과 작은 숫자 범위로 표현하는 것입니다. https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 매우 쉬운 좌표 압축 문제가 있습니다. 백준 18870번 좌표 압축을 풀어봅시다. 수직선위의 좌표는 매우 큰 범위를 갖습니다. 숫자도 100만개로 많습니다. (빠른 대량 입출력은 기본입니다.) 바로 떠오르는 아이디.. 2023. 1. 31.

평균, 중위값, 최빈값, 범위 구하기 C++ / JAVA / 파이썬 정렬 시간복잡도 백준 2108번 통계학 문제를 풀면서 각 언어별로 평균, 중위값, 최빈값, 범위를 구하는 알고리즘을 알아봅시다. https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제에 산술평균, 중앙값, 최빈값, 범위를 구하는 방법이 나와있습니다. 정수의 범위는 절대값 4000이므로 -4000에서 4000까지의 값을 갖습니다. 수의 개수는 500,000으로 정렬을 사용해도 시간초과가 나지 않고 충분합니다. 정렬 시간복잡도 : O(NlogN) 1. JAVA 1) 평균 구하기 .. 2023. 1. 20.

좌표 평면 2차원 배열로 표현 알고리즘 C++ / JAVA / 파이썬 백준 2663번 색종이 문제를 풀면서 좌표 평면을 2차원 배열로 어떻게 표현하는지 알고리즘 공부를 해봅시다. https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제를 보면 가로 세로 크기가 100밖에 안되는 아주 작은 좌표 평면입니다. 그렇다면 2차원 배열을 int[100][100] 선언하면 되는 간단한 문제입니다. 가로세로 길이가 10인 정사각형 색종이가 나올때마다 검은 영역을 1로 만들어줍니다. 최종적으로 1인 영역을 카운팅하면 넓이가 구해집니다.. 2023. 1. 20.

다이나믹 프로그래밍 알고리즘 C++ / Java / 파이썬 점화식 다이나믹 프로그래밍 알고리즘을 쉬운 문제를 풀며 공부해봅시다. 백준 2775 부녀회장이 될테야 문제를 풀어봅시다. https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net k와 n의 범위는 1부터 14까지 입니다. 매우 작네요. 느낌상 다이나믹 프로그래밍 알고리즘이라는 생각이 듭니다. 엑셀로 그림을 그려봅시다. 배열은 0부터 시작하므로 이해하기 쉽게 0호를 추가합니다. 0층의 i 호에는 i 명이 산다고 하네요. a층 b호에 사는 사람들은 a-1층의 1호부터 b호까지 사는 사람의 합입니다. 1층.. 2023. 1. 19.

문자 카운팅 알고리즘 C++ / Java / 파이썬 대소문자 변환 백준 1157번 : 단어 공부 문제를 풀면서 문자 카운팅 알고리즘과 대소문자 변환 방법을 알아봅시다. https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 단어가 주어집니다. 가장 많이 사용되는 알파벳을 대문자로 출력하는 문제입니다. 1) 처음 떠오르는 아이디어는 소문자를 모두 대문자로 변경하는 것입니다. 2) 알파벳은 26자 입니다. 크기가 26인 int형 배열을 선언하고 글자를 하나하나 보면서 +1 count 하면 되겠네요. 3) 가장 많은 알파벳을 출력하고, 여러개 존재하면 ?.. 2023. 1. 19.

이전 1 2 3 다음

티스토리툴바