분류 전체보기

이는 0 이하의 값이 입력될 때까지 입력이 계속되는 간단한 예제이다. 다음과 같은 형태로 자연수를 입력으로 받고 0이하의 값이 입력되면 while 문을 빠져나와 배열을 출력한다. 하지만 이처럼 배열은 메모리의 특성이 정적이여서 메모리의 길이를 변경하는 것이 불가능하다. 위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속 입력하면 할당된 배열의 크기인 10을 넘어가는 문제가 발생한다. 이 문제를 해결하기 위해 정적인 배열이 아닌 동적으로 메모리를 구성하여 다음과 같은 연결리스트를 구성할 수 있다. ▼코드 설명 1. 노드 형태 구현 여기서 data는 데이터를 담을 공간이며 struct _node *next 는 아래 그림처럼 노드의 연결을 위한 포인터이다. head는 연결 리스트에서 머리를 가리키는 포인..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 위의 예제를 바탕으로 풀어보면 다음과 같다. 맨 처음 dp[0] 값은 1로 설정하고 arr[1] 의 값이 arr[0] 보다 크면 dp[1] 의 값은 dp[0] 에 1을 더한 2로 설정한다. arr[2] 의 값이 arr[0] , arr[1] 보다 크지 않기 때문에 dp[2] 의 값은 1로 설정한다. arr[3] 의 값이 ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다음 문제는 경우의 수를 모두 작성하여 규칙을 본 결과 피보나치 배열과 같다는 걸 알게 되었다. N자리 이친수의 개수는 다음과 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n..

리스트는 구현방법에 따라 순차 리스트, 연결 리스트로 나눌 수 있다. ▶순차리스트 - 배열을 기반으로 구현된 리스트 ▶연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 또한 리스트 자료구조는 데이터를 나란히 저장하며 중복된 데이터의 저장을 막지 않는다. 그리하여 리스트를 활용하는 예를 코드로 살펴보면 다음과 같다. 코드 부분 설명 ▼ 다음 코드에서는 먼저 리스트를 생성 및 초기화한 후 11, 11, 22, 22, 33 라는 값을 저장한다. 그리고 LCount 함수를 통해 현재 리스트 안에 있는 데이터의 수를 출력하고 LFirst 함수로 첫 번째 데이터를 조회한 후 while 문을 통해 다음으로 넘어가면서 데이터를 출력한다. LFirst 함수를 통해 첫 번째 데이터부터 조회하는데 22 라는 값을 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이 문제는 계단 오르기 방식과 비슷한 형태의 문제이다. https://3946.tistory.com/94 백준 2579번 - 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는 3946.tistory.com 먼..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net ▶그룹단어란 happy 처럼 알파벳이 서로 떨어져 있지 않은 경우를 말하고 aba 처럼 알파벳 a가 서로 떨어져 있을 경우 그룹단어가 아니다. ex) alpha[26] 배열을 생성하고 aba 라는 문자열이 있을 때 먼저 a가 속하는 alpha[0] 에 true 값을 반환해주고 그 다음 b가 속하는 alpha[1] 에 true 값을 반환하고 그 다음 a가 속하는 al..

1. 피보나치 수열로 재귀함수 알아보기 피보나치 수열 : 재귀적인 형태를 띠는 대표적인 수열 코드 #include int fibo(int n) { if (n == 1) return 0; else if (n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { for (int i = 1; i B), 맨 아래 원반을 C로 옮기는 상황(A->C), 그리고 나머지 원반 2개를 C로 옮기는 상황(B->C) 총 3개로 볼 수 있으며 A->C 를 제외한 두 개의 상황은 각각 3개의 상황으로 나눌 수 있다. 이를 코드로 표현하면 다음과 같다. 코드 실행결과

https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 위 문제는 String 클래스의 contains 와 replace 함수를 이용하여 생각보다 간단히 풀 수 있었다. 코드 import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br ..

▶이진 탐색 알고리즘을 적용하기 위한 조건 : 배열에 저장된 데이터는 정렬되어 있어야 한다. 다음과 같이 정렬된 상태로 데이터가 저장되어 있다고 가정할 때 이 배열에 숫자 3이 저장되어 있는지 확인하기 위하여 이진탐색 알고리즘을 적용해보자. 더보기 ▶ 이진 탐색 알고리즘의 첫 번째 시도: 1. 배열 인덱스의 시작과 끝은 각각 0과 8이다. 2. 0과 8을 합하여 그 결과를 2로 나눈다. 3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다. 첫 번째 시도 결과 arr[4]에 3이 저장되지 않았음을 확인하였다. 더보기 ▶ 이진 탐색 알고리즘의 두 번째 시도: 1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다. 2. 대소의 비교결과는 arr[4]..

자료구조 - '데이터의 저장' 을 담당하는 것 알고리즘 - 저장된 데이터를 대상으로 하는 '문제의 해결 방법' 시간 복잡도 - 알고리즘의 수행시간 분석결과 공간 복잡도 - 메모리 사용량에 대한 분석결과 메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘 하지만 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.