선형구조 리스트 배열, 연결리스트 코딩테스트 (1)

 

목차

---

서론

코딩테스트 계획 포스팅에서 이어지는 포스팅이다. 오늘은 배열에 대해서 문제를 풀어보았다. 배열은 너도 알고 나도 아는것이라 딱히 개념에 대해 적을게 없어보인다. 그러니 바로 문제로 넘어갈것임. 문제는 백준 10808 https://www.acmicpc.net/problem/10808를 풀었다. 내가 보는 강의에 나오기 때문.

---

 

배열 문제 - 백준 10808 내가 푼 과정

나는 우선 l에다가 input을 받았다. 그리고 문제에서 소문자만 해당한다고 했다. 영어의 소문자는 26개라는...것을 외우지 않았다.. 그 언저리인건 알지만 아무튼 몰랐어서 백준에 있는 답 보고 하나하나셌다 허허. 아무튼 26개가 있으니 result에 0으로 구성된 26개의 열을 만들었다. 그리고 ord()를 사용해서 알파벳을 숫자로 바꿨고, 해당 함수는 아스키코드 값으로 바꾸는 것이기에, 소문자 a에 해당하는 96을 빼줬다. 그리고 해당 숫자에 해당하는 result 열의 개수를 하나씩 추가했다. 마지막으로 한칸씩 띄쓰해서 출력했다. 영상서는 C++를 사용해서 나와 얼마나 흡사한지는 모르겠는데 설명들으면 나랑 아이디어는 같더라. 고로 이번 문제는 답지 생략.

l = 'baekjoon'
result = [0]*26

for i in range(len(l)) :  
    a = ord(l[i])
    result[a-96] += 1  #숫자로 변환해서 하나씩 넣기 

for i in result : # 공백으로 구분해서 출력
    print(i,end=' ')

---

추가로 문제를 풀려고 했더니 프로그래머스의 알고리즘 고득점 킷에는 배열이 없다. 스택, 큐가 있긴하지만 이건 해당 강의가 따로 있기에 일단 배열 문제는 스킵하고 빨리 다른 문제 풀어볼 예정임. 자료구조상 애매한 부분이 있어서 이 부분은 유도리 있게 넘어가고자한다. 그래도 DFS, BFS 이 부분은 칼같이 나뉘지않을까.. 아무튼 일단 배열운 여기까지.

 

---

연결리스트와 그 종류

연결리스트는 배열의 각각의 원소가 서로를 기억하는 경우다. 한 명이 모두를 기억하는게 아니라 서로서로 기억하는 구조라고 보면 된다. 연결리스트의 종류는 1. singly linked list 2. doubly linked list 3. circular linked list 가 있다. 그리고 해당 구조는 아래 사진을 참고하자. 단순 배열과 연결 리스트의 큰 차이는 원소를 확인하는것과 추가,제거하는 것이다. 연결리스트는 확인은 느것에 비해 (묻고 묻고 묻고 묻고 도착 = O(N)), 추가/제거시 걔만 없애거나 그 주변부만 만지작 (응 너 저기 들어와, 응 너나가~ = O(1)) 거리면 되기 때문. 일반 배열은 그 반대라고 보면 되겠다. 연결 리스트 문제는 일단 생략.

출처: https://www.youtube.com/watch?v=C6MX5u7r72E

---