배열을 이용하여 문자열을 표현할 수 도 있다. 다음을 보자.

char str[ ] = "Hello world!"; 

위의 코드를 통해 배열 str에 char형 배열이 할당된 것을 확인할 수 있다. 그렇다면 위의 배열의 앞에서 배웠던 sizeof함수를 이용하여 길이를 알아보자.

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
 
int main(void) {
    char str[] = "Hello world!"// 글자는 공백을 포함하여 12개 이다. 
 
    int len = sizeof(str) / sizeof(char);
    printf("배열의 길이 : %d\n", len);
    
    return 0;
}
cs

<실행결과>

공백을 포함하여 Hello world! 는 12글자인데 왜 13글자가 나올까? 이는 널 문자 때문이다. 다시 말하면 배열 str은 다음의 구조와 같다.

널 문자 \0가 포함된 모습

그렇다면 이 널 문자는 왜 포함되는 것 일까? 바로 문자열을 표현하기 위해서 이다.

 

char arr[ ] = {'H', 'i', '~'}; // 널 문자(\0)가 없으므로 단순한 문자 배열

char arr2[ ] = {'H', 'i', '~', '\0'}; // 널 문자(\0)가 존재하므로 문자열  

 

즉 C언어에서는 문자열에서 널 문자를 인식하고 이를 문자열의 마지막으로 인식한다.


예제

프로그램 사용자로부터 하나의 영단어를 입력받아서 입력받은 영단어를 뒤집어서 출력하도록 예제를 작성하라 단 널 문자의 위치를 변경해서는 안된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main(void) {
    char str[100];
    scanf("%s", str);
 
    int len = 0;
    while (str[len] != '\0')
        len++;
 
    char temp;
 
    for (int i = 0; i < len / 2; i++) {
        temp = str[i];
        str[i] = str[len - 1 - i];
        str[len - 1 - i] = temp;
    }
 
    printf("%s", str);
    return 0;
}
cs

<실행결과>

 

'C' 카테고리의 다른 글

5. 포인터와 함수  (0) 2021.06.25
4. 포인터와 배열  (0) 2021.06.22
3. 포인터  (0) 2021.06.21
1-1 배열 예제  (0) 2021.06.21
1. 배열 - 배열과 초기화에 관하여  (0) 2021.06.21

길이가 5인 int형 배열을 선언하여 사용자로부터 5개의 숫자를 입력받은 후 배열의 모든 원소중 최대 값, 최소 값, 모든 원소들의 합을 구하는 예제를 작성하라

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
void getMaxValue(int arr[], int len) {
    int max = 0;
    for(int i = 0; i < len; i++) {
        if(arr[i] > max) 
            max = arr[i];
    }
    printf("배열의 원소들 중 최대값은 %d 입니다.\n", max);
}
 
void getMinValue(int arr[], int len) {
    int min = 9999// max 값 설정
    for(int i = 0; i < len; i++) {
        if(arr[i] < min) 
            min = arr[i];
    }
    printf("배열의 원소들 중 최대값은 %d 입니다.\n", min);
}
 
void getTotalSum(int arr[], int len) {
    int total = 0;
    for(int i = 0; i < len; i++) {
        total += arr[i];
    }
    printf("배열의 원소들 중 최대값은 %d 입니다.\n", total);
}
 
int main(void) {
    int arr[5];
 
    for(int i = 0; i < 5; i++) {
        scanf("%d"&arr[i]);
    }
 
    int len = sizeof(arr) / sizeof(int);
 
    getMaxValue(arr, len);
    getMinValue(arr, len);
    getTotalSum(arr, len);
 
    return 0;
}
cs

<실행결과>

'C' 카테고리의 다른 글

5. 포인터와 함수  (0) 2021.06.25
4. 포인터와 배열  (0) 2021.06.22
3. 포인터  (0) 2021.06.21
2. 배열을 이용하여 문자열의 표현  (0) 2021.06.21
1. 배열 - 배열과 초기화에 관하여  (0) 2021.06.21
배열이란?

배열이란 둘 이상의 변수를 모아 놓은 것이다. 배열의 선언 방식은 다음과 같다.

위에서 볼 수 있듯이 int arr[10]; 이면 자료형이 int, 배열의 이름이 arr, 배열의 길이가 10이라는 것을 말하는 것이다.

1
int arr[10];
cs

위에서 볼 수 있듯이 int arr[10]; 이면 자료형이 int, 배열의 이름이 arr, 배열의 길이가 10이라는 것을 말하는 것이다.

또한 특징이 있는데 배열의 시작은 0부터 시작한다는 것이다. 따라서 위의 길이가 10인 배열의 경우 0번째 원소부터 9번째 원소까지 존재한다.

배열의 가장 큰 장점이 존재하는데 바로 반복문을 이용하여 순차적으로 접근이 가능하다는 점이다. 이것을 예시를 통해 알아보자.

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main(void) {
    int arr[5= {010203040 }; // 전부 더하면 100 이다. 
    int sum = 0;
 
    for(int i = 0; i < 5; i++) { // 반복문을 통해 모든 원소들을 더함
        sum += arr[i];
    }
    printf("배열의 모든 원소의 합 : %d", sum);
    return 0;
}
cs

배열의 선언과 동시에 초기화

배열의 초기화의 방법은 총 3가지가 존재한다. 다음을 통해 알아보자.

  1. int arr[5] = {1, 2, 3, 4, 5}; // 차례차례 초기화
  2. int arr1[ ] = {1, 2, 3, 4, 5}; // 컴파일러에 의해서 자동으로 길이 5가 채워진다
  3. int arr3[5] = {1, 2};  // 3, 4, 5 번째 요소는 자동으로 0으로 채워진다.

배열의 길이를 구하는 sizeof() 함수

배열의 길이를 따로 명시하지 않더라도 sizeof 함수를 통해 알 수 있다. 먼저 일반적인 배열 int arr[5] = {1, 2, 3, 4, 5};를 생각해보면 int형이므로 한 요소당 4byte씩 총 20byte이다. 따라서 sizeof(arr);는 20byte이다. 이를 int의 크기 4byte로 나누면 5 즉 배열의 길이를 구할 수 있다. 따라서 배열의 길이는 int len = sizeof(arr) / sizeof(int);로 구할 수 있다. 예시를 보면 다음과 같다.

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main(void) {
    int arr1[5= {010203040 };  
    double arr2[4= {0.01.02.03.0};
    float arr3[6= {0.01.02.03.04.05.0};
 
    printf("배열 arr1의 크기 : %d\n"sizeof(arr1));
    printf("배열 arr2의 크기 : %d\n"sizeof(arr2));
    printf("배열 arr3의 크기 : %d\n"sizeof(arr3));
 
    int len1 = sizeof(arr1) / sizeof(int); // 배열 1의 길이
    int len2 = sizeof(arr2) / sizeof(double); // 배열 2의 길이
    int len3 = sizeof(arr3) / sizeof(float); // 배열 3의 길이
 
    printf("배열 arr1의 길이 : %d\n", len1);
    printf("배열 arr2의 길이 : %d\n", len2);
    printf("배열 arr3의 길이 : %d\n", len3);
 
    return 0;
}
cs

<실행결과>

 

'C' 카테고리의 다른 글

5. 포인터와 함수  (0) 2021.06.25
4. 포인터와 배열  (0) 2021.06.22
3. 포인터  (0) 2021.06.21
2. 배열을 이용하여 문자열의 표현  (0) 2021.06.21
1-1 배열 예제  (0) 2021.06.21

이 포스팅은 나동빈 님의 www.youtube.com/watch?v=Ppimbaxm8d8 벨만포드 알고리즘 강의를 참고하였습니다.

개념

벨만 포드 알고리즘은 다익스트라 알고리즘과 비슷하지만 음의 간선이 있는 경우 사용할 수 있다는 점에서 큰 장점을 지닙니다. 또한 음의 간선 사이클이 존재할 경우 이를 검출할 수도 있는 장점을 지니고 있습니다. 

이러한 장점을 가짐과 동시에 O(ElogV)라는 시간복잡도를 지닌 다익스트라 알고리즘과 달리 O(VE)의 시간 복잡도를 지닌다는 단점도 존재합니다.

과정은 다음과 같습니다.

 

1. 출발 노드를 설정합니다.

2. 최단 거리 테이블을 초기화 합니다.

3. 전체 간선 E를 확인합니다. 

4. 각 간선을 확인하며 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 계산합니다.

5. 위의 3, 4번 과정을 n-1번 반복을 합니다.

6. 만약 n번째에서도 최단 거리 테이블이 갱신된다면 음의 간선 순환 사이클이 존재한다는 것입니다.


소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n, m = map(int, input().split())
edges = []
dist = [INF] * (1+n)
 
for i in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
 
def bf(start):
    dist[start] = 0
    for i in range(n):
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                if i == n-1:
                    return True
    return False
 
negative_circle = bf(1)
 
if negative_circle:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])
 
cs

 

www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 


문제 해결을 위한 과정

이 문제의 경우 BFS를 이용하면 해결할 수 있는 문제였습니다. 보통 BFS 문제의 경우 이차원 리스트 혹은 이차원 배열에서 특정 지점에서 다른 지점으로 퍼져나가는 형식으로 탐색하는 것인데 특이하게 이 문제의 경우 일차원 리스트상에서 해결해야 하기 때문에 처음에는 생각하기가 조금 어려웠던 문제였습니다.

먼저 문제의 예시를 살펴보도록 하겠습니다.

5의 위치에서 시작하여 17까지 가야합니다. 시간이 걸리지 않는 순간이동의 방식으로 현재 위치 * 2 한 지점으로 이동할 수 있습니다. 또는 시간이 1초 걸려서 현재 위치의 좌측 위치 혹은 우측 위치로 이동할 수 있습니다.

이를 너비 우선이 방식으로 큐에 넣어주고 차례 차례 탐색해 나갑니다.


소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n, m = map(int, input().split())
max = 100001
visited = [0* max
move = [-11]
 
def bfs():
    q = deque()
    q.append(n)
    count = 0
    visited[n] = 1
    if 2*< max and not visited[2*n]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우 순간이동으로 탐색
        visited[2*n] = 1
        q.append(2*n)
    if visited[m] != 0# 도착점인 경우 
        print(visited[m] - 1)
        return
    while q:
        pos = q.popleft()
        if visited[m] != 0# 도착점인 경우
            print(visited[m] - 1)
            return
        if 2*pos < max and not visited[2*pos]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우
            visited[2*pos] = visited[pos] # 순간이동으로 탐색
            q.append(2*pos)
        for i in range(2): # 시간을 1초 소비하며 좌, 우를 탐색하는 경우
           npos = pos + move[i]
           if 0 <= npos < max:
               if not visited[npos]:
                   visited[npos] = visited[pos] + 1
                   q.append(npos)
 
bfs()
 
cs

 

www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net


문제 해결을 위한 과정

이 문제의 경우 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 그러나 주의할 점이 있었는데 바로 꼭 거쳐야하는 2개의 지점이 있다는것 입니다. 지나가야 하는 지점이 x, y라 할 경우

1 -> x -> y -> N

1 -> y -> x -> N 

이렇게 두가지의 경우가 있으므로 위의 두가지 경우에 대한 다익스트라 알고리즘을 적용하여 거리를 각각 구한 후 더 작은 숫자를 출력하면 됩니다. 또한 문제에서 이동할 수 없는 거리라면 -1을 출력하라는 조건이 있었기 때문에 이를 유의하여 해결합니다.


소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import heapq
INF = 1001
 
n, m = map(int, input().split())
graph = [[] for _ in range(1 + n)]
 
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
 
def dijkstra(start, pos):
    distance = [INF] * (1 + n)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
       
    return distance[pos]
x, y = map(int, input().split())
dist1 = dijkstra(1, x)
dist2 = dijkstra(x, y)
dist3 = dijkstra(y, n)
 
dist4 = dijkstra(1, y)
dist5 = dijkstra(y, x)
dist6 = dijkstra(x, n)
 
ans = min(dist1 + dist2 + dist3, dist4 + dist5 + dist6)
if ans >= INF:
    print(-1)
else:
    print(ans)
 
 
cs

 

www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net


문제 해결을 위한 과정

이 문제의 경우 DFS 카테고리에 있었던 깊이 우선 탐색 방식으로 해결할 수 있었던 문제입니다. 저는 처음에 tree구조를 직접 정의하여 해결하려 했으나 복잡하게 해결하는 것 같아 트리를 구현하는 방식이 아닌 단순하게 리스트에 그래프를 삽입하고 dfs를 이용하여 해결하는 기본적인 방식으로 해결하였습니다. 

문제의 예제 2번을 기준으로 설명드리겠습니다. -1 0 0 1 1 인데 0번째 노드는 root노드이므로 따로 빼두고 나머지 경우를 보겠습니다. 그 후 노드 1을 제거합니다. 그 과정은 다음 그림과 같습니다.

좌측은 1을 제거하기전 우측은 1을 제거한 후입니다. 리프 노드가 3개에서 1개로 감소한 것을 알 수 있습니다.

따라서 문제에서 주어진 노드부터 차례차례 삭제를 해 나아간 후(dfs를 응용한 remove함수로 구현) dfs를 이용해 리프 노드의 개수를 세주면 됩니다.


문제 해결을 위한 과정

위의 과정에 단 한가지 예외가 붙는데 바로 루트 노드를 삭제하는 경우입니다. 처음 입력받을 때 루트 노드를 따로 뺀 후 삭제를 시작할 입력받은 노드가 루트 노드라면 바로 0을 출력해주면 됩니다. 이유는 루트 노드를 삭제하는 경우 전체 노드가 없어지기 때문입니다.


소스코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import copy
= int(input())
graph = [[] for _ in range(n+1)]
data = list(map(int, input().split()))
for i in range(n):
    if data[i] == -1# 부모가 -1인 경우 루트노드로 설정
        root = i
        continue
    graph[data[i]].append(i) # 루트노드가 아닌경우 해당 그래프의 점에 연결
start = int(input())
 
def dfs(graph, visited, v): # dfs 방식으로 탐색
    global count
    visited[v] = True # 방문처리
    if len(graph[v]) == 0# 리프 노드의 개수를 셈
        count += 1
    for i in graph[v]: # 방문처리하지 않은 노드를 재귀의 방식으로 dfs 탐색
        if not visited[i]:
            dfs(graph, visited, i)
    return count
 
def remove(tempgraph, graph, visited, v): # 입력받은 수의 자식노드를 제거해나가는 함수 dfs 방식 응용
    visited[v] = True
    for i in range(n): # 그래프를 조회하며 dfs 방식으로 탐색한 노드들을 tempgraph에서 삭제
        for j in range(len(graph[i])):
            if graph[i][j] == v:
                tempgraph[i].remove(v)
    for i in graph[v]:
        if not visited[i]:
            remove(tempgraph, graph, visited, i)
 
if start != root: # 지우기 시작할 노드가 root가 아닌경우
    tempgraph = copy.deepcopy(graph) # graph를 복사하여 tempgraph생성
    count = 0
    visited = [0* (1 + n)
    remove(tempgraph, graph, visited, start)
 
    count = 0
    visited = [0* (1 + n)
    print(dfs(tempgraph, visited, root))
else# 지우기 시작할 노드가 root인 경우 그냥 0을 출력함
    print(0)
cs

 

www.acmicpc.net/problem/1074

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서

www.acmicpc.net


문제 해결을 위한 과정

이 문제의 경우 전형적인 재귀, 분할 정복으로 해결할 수 있는 문제였습니다. 입력받은 좌표가 전체 영역에서 어떤 사분면에 위치하는지 파악 후 이들을 분할한 뒤 또 어떤 사분면에 해당하는지 위치를 알아가면 해결할 수 있는 문제였습니다.

그림으로 설명하겠습니다. 

 

n이 3인 경우를 예로 들겠습니다.

4행 6열즉 52가 몇 번째로 탐색이 되는지 판단해봅시다. (이미 52라 나와있긴 합니다만...)

우선 크게 4개의 사분면으로 쪼개면 해당 좌표는 4 사분면에 위치합니다. 그 후 쪼개면 다음 그림과 같습니다.  

이렇게 분할하면 이번에는 2 사분면에 위치하는 것을 알 수 있습니다. 그 후 한번 더 분할합니다.

이번에는 1 사분면에 위치하는 것을 알 수 있습니다. 정리해보면 4 사분면->2 사분면->1 사분면으로 이동한 것을 알 수 있고 n이 1인 경우이므로 여기서 분할은 종료가 됩니다.

맨 처음에 4 사분면에 위치하고 4행 6열이 그 다음에는 2사분면에 위치하고 0행 2열이 됩니다. 그 후 1사분면의 0행 0열로 위치가 바뀌므로 우리는 사분면을 나눌때마다 좌표를 재배치 해줘야하는것을 알 수 있습니다. 따라서 reallocate()를 정의하여 해결해줍니다.


문제 해결을 위한 팁

이번에는 reallocate함수를 자세하게 알아봅시다. 위의 예시를 그대로 이용하겠습니다.

4사분면에 위치한 4행 6열이 2 사분면으로 이동할 때 0행 2열이 되었습니다. 따라서 각각 4 만큼씩 줄어들었습니다.

이후 0행 2열이 0행 0열이 되었는데 이번에는 열만 2 만큼이 줄어든 것을 알 수 있습니다. 따라서 이를 일반화하면 다음과 같습니다.

 

1 사분면인 경우 -> 유지

2 사분면인 경우 -> 열 값만 2^(n-1)만큼 감소

3 사분면인 경우 -> 행 값만 2^(n-1)만큼 감소

4 사분면인 경우 -> 행 열 모두 2^(n-1)만큼 감소


소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n, r, c = map(int, input().split())
def find(r, c): # 사분면 찾는 함수
    if 0 <= r < 2 ** (n-1and 0 <= c < 2 ** (n-1):
        return 1
    elif 0 <= r < 2 ** (n-1and 2 ** (n-1<= c < 2 ** (n):
        return 2
    elif 2 ** (n-1<= r < 2 ** (n) and 0 <= c < 2 ** (n-1):
        return 3
    else:
        return 4
 
def reallocate(): # 사분면을 쪼갠후 좌표값을 재배치
    global r, c, n
 
    if res == 2# 2사분면인 경우
        c -= 2 ** (n-1)
    elif res == 3# 3사분면인 경우
        r -= 2 ** (n-1)
    elif res == 4# 4사분면인 경우
        r -= 2 ** (n-1)
        c -= 2 ** (n-1)
    n -= 1
 
ans = 0
while True:
    if n <= 0:
        break
    res = find(r, c)
    ans = ans + (res-1* (4 ** (n-1))
    reallocate()
 
print(ans)
 
cs

 

+ Recent posts