All-rounder developer

[컴활] 컴퓨터활용능력 1급 (필기/실기) 시험 개요

타락파워개발자 — Mon, 2 Jun 2025 15:08:48 +0900

1. 시험 개요 및 범위

- 필기 시험은 객관식 60문항으로 구성되며 총 60분 동안 진행된다. 평균 60점 이상 합격이며, 40점 미만 과락이다.

- 실기 시험은 컴퓨터 작업형이며 총 90분(과목별 45분) 동안 진행된다. 두 과목 모두 70점 이상 합격이다.

- 실기의 경우 MS오피스 LTSC Professional Plus 2021 프로그램으로 실시한다. (2025.06.02 기준)

	주요 항목	문항 수	배점	시험 시간
필기	컴퓨터 일반	20	문항당 5점 (영역별 각 100점)	60분
	스프레드시트 일반	20
	데이터베이스 일반	20
실기	스프레드시트 실무			90분 (과목별 45분)
	데이터베이스 실무	DB 구축	30
		입력 및 수정	25
		조회 및 출력	20
		처리 기능	25

※ 정보 출처: https://license.korcham.net/co/examguide.do?mm=21&cd=0103

종목소개 시험안내

컴퓨터활용능력 종목소개 산업계의 정보화가 진전되면서 영업, 재무, 생산 등의 분야에 대한 경영분석은 물론 데이터 관리가 필수적입니다. <컴퓨터활용능력> 검정은 사무자동화의 필수 프로그

license.korcham.net

[Python] Anaconda 및 Jupyter Lab (혹은 Jupyter Notebook) 설치 (+ Conda 가상환경 생성/(비)활성화/리스트 확인)

타락파워개발자 — Sat, 24 May 2025 16:42:06 +0900

1. Anaconda 설치

아래 URL에 접속하여 좌측 Download 버튼을 클릭한다.

URL: https://www.anaconda.com/download/success

Download Now | Anaconda

Anaconda is the birthplace of Python data science. We are a movement of data scientists, data-driven enterprises, and open source communities.

www.anaconda.com

약정에 동의한 후 계속 Next를 해 준다.

마지막 설치 옵션 설정 화면에서 본인이 원하는 설정을 해 준다. 나는 경로 설정이 자동으로 되도록 "Add Anaconda3 to my PATH ..." 옵션을 추가로 체크해주었다.

그리고 초록색이 다 차도록 기다려주면 설치가 끝난다.

2. Conda 가상환경 생성 및 실행 (관련 명령어 알아보기)

Anaconda navigator에 접속하여 GUI 환경으로 jupyter notebook을 설치할 수도 있다.

그러나 나는 터미널에서 주로 작업할 것이다.

따라서 터미널에서 Conda 설치가 완료되었는지 확인하고 가상환경을 생성하겠다.

파워쉘에 들어가 아래 명령어를 실행하면 콘다가 정상적으로 설치되었는지 확인할 수 있다.

conda -V  # conda 24.9.2

나는 "conda 24.9.2"가 출력되어 정상적으로 설치되었음을 확인하였다.

설치가 잘 되었다면 아래 명령어를 통해 가상환경을 생성한다.

conda create -n "가상환경이름" python=(파이썬버전)

그리고 생성된 가상환경 리스트를 확인하기 위해서는 아래 명령어를 실행한다.

conda env list

아까 생성한 가상환경을 활성화(실행)하기 위해서는 아래 명령어를 실행한다.

conda activate (가상환경이름)

마지막으로 활성화된 가상환경을 종료하기 위해서는 아래 명령어를 실행한다.

conda deactivate

3. Jupyter lab 설치 및 실행

Conda의 설치 명령어인 conda install을 통해 jupyter을 설치한다. 명령어는 아래와 같다.

conda install jupyter

위 명령어를 실행한 후 jupyter lab(혹은 jupyter notebook)을 실행해준다.

jupyter lab

그러면 새로운 웹 브라우저 창에 주피터 랩(혹은 노트북) 창이 뜬다.

끝!

[SQLD] SQLD 시험 개요 및 일정 정리

타락파워개발자 — Sat, 17 May 2025 14:22:50 +0900

1. 일정

- 시험일: 2025.05.31.토요일

- 합격자 발표: 2025.06.27.금요일

- 응시 목적: 공기업 준비 및 전공 자격증 취득

- 응시 배경: 컴퓨터 관련 전공자, 데이터베이스 교과목 수강 경험 있음, SQLD 초시

2. 시험 개요 및 범위

- 2025.05.17 기준 작성되었으므로, 이후 시험 개정에 따라 변경될 수 있다.

- 필기 시험만 진행되며, 총 2과목 및 50문항으로 구성되어 있다.

- 시험은 90분 (1시간 30분) 동안 진행된다.

- 총점 60점 이상 합격하며, 40점 미만일 경우 과락으로 탈락할 수 있다.

과목명	주요 항목	세부 항목	문항 수	배점
데이터 모델링의 이해	데이터 모델링의 이해	데이터 모델의 이해, 엔터티, 속성, 관계, 식별자	10	20 (문항당 2점)
데이터 모델링의 이해	데이터 모델과 SQL	정규화, 관계와 조인의 이해, 모델이 표현하는 트랜잭션의 이해, Null 속성의 이해, 본질식별자 vs 인조식별자	10	20 (문항당 2점)
SQL 기본 및 활용	SQL 기본	관계형 데이터베이스의 개요, SELECT 문, 함수, WHERE절, GROUP BY, HAVING절, ORDER BY 절, 조인, 표준 조인	40	80 (문항당 2점)
	SQL 활용	서브 쿼리, 집합 연산자, 그룹 함수, 윈도우 함수, Top N 쿼리, 계층형 질의와 셀프 조인, PIVOT 절과 UNPIVOT 절, 정규표현식
	관리 구문	DML, TCL, DDL, DCL

※ 정보 출처: https://www.dataq.or.kr/www/sub/a_04.do

데이터자격검정

데이터자격검정, 빅데이터분석기사, DAP, DAsP, SQLP, SQLD, ADP, ADsP

www.dataq.or.kr

[백준][계수정렬] 과제 안 내신 분..?

타락파워개발자 — Thu, 24 Apr 2025 18:22:26 +0900

오늘의 학습 키워드

계수 정렬, 구현

오늘의 회고

오늘의 문제

https://www.acmicpc.net/problem/5597

28개의 중복되지 않는 1 이상 30 이하의 정수값을 입력 받는다.

이 중 1 이상 30 이하의 수 중 등장하지 않은 값 2개를 출력한다.

어려운 문제는 아니지만 "계수 정렬"이라는 개념을 적용해보기 좋은 문제인 것 같아 게시물로 작성해 본다.

계수 정렬에 대해 잘 모른다면 아래 글의 4. 계수 정렬 내용을 확인하세요! ☺️

https://developer-zoyh.tistory.com/30

[알고리즘] 정렬 시리즈 1탄: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

0. Introduction가장 기본이 되는 4가지 정렬 기법인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리해 보았다.이 정렬 기법들이 가장 좋다고 볼 순 없지만, 구현이 간단하거나 경우에 따라

developer-zoyh.tistory.com

나의 시도

'''
- 문제 유형: 구현
- 풀이 방법: 일종의 계수 정렬을 활용한다. 출석 여부 배열을 활용하자!
- 풀이 순서
1. 학생 수 만큼의 출석 여부(Boolean)를 저장할 배열 isAttended 배열을 만든다.
2. 제출한 28명의 출석 번호를 입력 받으며, 입력 받은 출석 번호에 대하여 isAttended 배열에 처리해준다.
3. 출석 여부 배열을 1번부터 돌며 값이 False인 위치의 인덱스(출석 번호)를 출력한다.

-> 1차원 배열을 순회하면서 모든 과정을 처리할 수 있으므로 시간 복잡도는 O(n)이다.
'''
cnt_students = 31 # 0번부터 시작하므로 +1
isAttended = [False] * cnt_students 

for _ in range(28):
    x = int(input())
    isAttended[x] = True

for i in range(1, cnt_students):
    if not isAttended[i]: print(i)

풀이는 계수 정렬 알고리즘을 참고하되, 개수를 세지 않고 등장 여부(True/False)를 체크해주었다.

1부터 배열을 돌면서 False인 값을 출력해주면, 입력에서 등장하지 않은 값을 출력할 수 있다.

오늘의 후기

계수 정렬을 몰랐던 때에도 풀 수 있던 문제이지만, 개념을 문제로 만나면서 머릿속에 있던 여러 파편들이 연결되는 듯한 느낌을 받았다.

문제의 여러 조건(입출력 형식, 제약 조건 등)을 보고 문제를 파악하고 설계해나가는 시야가 넓어지고 있다.

더 다양하고 재밌는 문제들을 풀어나가고 싶다.

[알고리즘] 정렬 시리즈 1탄: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

타락파워개발자 — Thu, 24 Apr 2025 18:00:28 +0900

0. Introduction

가장 기본이 되는 4가지 정렬 기법인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리해 보았다.

이 정렬 기법들이 가장 좋다고 볼 순 없지만, 구현이 간단하거나 경우에 따라 가장 효율적이기 때문에 많이 쓰이는 방법들이다.

각각의 정렬 기법들은 이름을 보면 어떻게 동작하는지 힌트를 얻을 수 있다. 하나씩 자세히 살펴보자.

참고로 아래 예시는 작은 값부터 점차 큰 값으로 정렬하는 오름차순 정렬을 기준으로 설명하고 있다.

1. 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

1-1. 선택 정렬의 특징

선택 정렬은 리스트를 돌면서 가장 작은 요소를 선택하여 맨 앞으로 가져온다.

1-2. 선택 정렬 동작 과정

따라서 위 이미지를 보았을 때, Step 1 에서는 5번 인덱스(여섯번째 값)의 1을 0번 인덱스의 4와 교환(swap)한다.

Step2 에서는 0번 인덱스를 제외한 나머지 배열에서 가장 작은 값인 2(6번 인덱스)를 가져와 1번 인덱스의 7과 교환(swap)한다.

이런 과정을 반복하며 맨 마지막 인덱스까지 채워나간다.

1-3. 선택 정렬의 시간 복잡도 및 활용 방법

이중 반복문을 통해 최소값을 찾아 교환해나가는 방식으로 시간 복잡도는 최선/최악의 경우 모두 O(n^2)이다.

로직이 직관적이고 구현 난이도가 어렵지 않기 때문에 데이터가 크지 않고 시간이 충분한 경우 간단하게 활용하기 좋다.

2. 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

2-1. 삽입 정렬의 특징

삽입 정렬은 적절한 위치에 새로운 요소를 삽입하는 과정을 반복하며 리스트 정렬 상태를 만들어나가는 방식이다.

기준 인덱스를 기준으로 좌측은 정렬된 리스트라고 가정하고, 기준 인덱스를 우측으로 한 칸씩 이동하며 값을 적절한 위치에 삽입해준다.

2-2. 삽입 정렬의 동작 과정

위 이미지를 살펴보자.

0번 인덱스에 위치한 4의 경우엔 기존 정렬된 리스트가 없으므로 위치를 유지한다.

1번 인덱스의 7은 4보다 크기 때문에 이동하지 않고 본인의 위치를 유지한다.

2번 인덱스의 5의 경우에는, 좌측 정렬된 리스트([4, 7])에서 4보다 크고 7보다 작으므로 그 사이에 삽입된다.

3번 인덱스의 3의 경우에는, 좌측 정렬된 리스트([4, 5, 7])에서 가장 작으므로 맨 앞에 삽입하고 다른 값들은 한 칸씩 뒤로 이동한다.

2-3. 삽입 정렬의 시간 복잡도 및 활용 방법

정렬된 리스트를 역으로 돌면서 본인이 삽입될 위치를 찾고, 값이 삽입되기 위해 다른 값들을 한 칸씩 이동 시켜야 한다.

최악의 경우(역순으로 정렬된 경우)에는 앞 쪽의 원소를 모두 탐색하는 작업을 수행해야 하므로 0 + 1 + 2+ 3 + ... + n = n(n-1)으로, O(n^2)의 시간 복잡도를 갖는다.

그러나 최선의 경우(순서대로 정렬된 경우)에는 앞 쪽의 원소를 전혀 탐색하지 않아도 되므로 배열을 순회하는 O(n)으로 가능하다.

따라서 배열이 거의 정렬되어 있는 상태에서 일부 값이 추가되는 상황이라면 삽입 정렬이 유리할 수 있다.

3. 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort) 1

퀵 정렬 (Quick Sort) 2

3-1. 퀵 정렬의 특징 및 시간 복잡도

퀵 정렬은 이름이 치명적이다. 원래 이렇게 도파민을 내뿜는 존재는 경계해야 한다. (ㅋㅋ)

퀵 정렬은 시간 복잡도가 중요한 특징이기에 다른 정렬 기법과 달리 동작 과정 설명에 앞서 특징과 함께 시간 복잡도를 설명하려고 한다.

퀵 정렬은 앞서 살펴본 두 정렬과 달리 비교 정렬이 아닌 분할 정렬이다.

분할 정렬은 배열이 분할되면서 길이가 짧아지기에 O(n log n)의 시간 복잡도로 정렬이 가능하다.

그러나 퀵 정렬은 피벗을 활용하여 비균등하게 정렬하는데, 최악의 경우 앞서 살펴보았던 선택 정렬이나 삽입 정렬처럼 O(n^2)으로 그다지 효율적이지 않다. 따라서 퀵 정렬은 '피벗'을 어떻게 정의해주는지가 굉장히 중요하다.

3-2. 퀵 정렬의 동작 과정

위 이미지를 통해 퀵 정렬의 정렬 과정을 구체적으로 살펴보자. 이 예시에서는 첫 번째 값을 피벗으로 정하였다.

퀵 정렬에서는 두 가지 지표(left, right)가 존재하는데, 하나(left)는 (피벗을 제외한) 좌측부터 피벗보다 큰 값을 탐색한다. 나머지 하나(right)는 우측부터 피벗보다 작은 값을 탐색한다. 그리고 각각의 지표가 기준에 충족되는 경우 서로의 값을 변경한다.

Step1-1에서 보면, left가 찾은 1번 인덱스의 7이 피벗 4보다 크고, right가 찾은 6번 인덱스의 7이 피벗 4보다 작기 때문에 두 값을 교환(swap)해 주었다.

Step1-2에서도 left가 찾은 2번 인덱스의 5가 피벗 4보다 크고, right가 찾은 5번 인덱스의 1이 피벗ㅅ 4보다 작기 때문에 두 값을 교환(swap)해 주었다.

step 1-3에서는 left와 right의 위치가 서로 역전되었으므로, right 위치로 피벗이 이동하고 피벗을 기준으로 좌측과 우측의 리스트를 나눈다.

이 때, 나누어진 리스트를 잘 살펴보자. 좌측 리스트는 피벗을 기준으로 "작은 값"들로만 구성되어 있고, 우측 리스트는 "큰 값"들로만 구성되어 있다. 이렇게 배열을 분할하면서 분할된 배열에 대해 정렬된 상태를 유지한다.

가장 작은 단위까지 분할하게 되면 전체 배열에 대해 정렬이 완료되며, 분할이 반복되며 배열의 크기가 작아질수록 정렬 속도가 빨라진다.

3-3. 퀵 정렬의 활용 방법

퀵 정렬은 피벗 설정 방식에 따라 최악의 시간 복잡도를 갖는 경우가 다르다.

이번 예시와 같이 첫 번째 값으로 설정해준 경우에는 리스트가 정렬되어 있는 경우이다.

퀵 정렬 특징을 고려해보면 피벗을 기준으로 왼쪽 서브 배열에 피벗보다 작은 값들, 오른쪽 서브 배열에 피벗보다 큰 값들이 배치된다.

오름차순으로 정렬된 경우 피벗의 왼쪽 서브 배열은 비어있고, 나머지 값은 모두 오른쪽 서브 배열로 들어가며 피벗이 한 칸씩 오른쪽으로 이동하게 된다. 역으로 내림차순으로 정렬된 경우는 반대로 값들이 모두 왼쪽 서브 배열로 들어가고, 오른쪽 서브 배열은 비어 있으며 피벗이 한 칸씩 왼쪽으로 이동하게 된다.

이를 방지하기 위해서는 무작위 값 혹은 중간값으로 결정하는 등 적절한 최적화 기법을 취해줄 수 있다.

4. 계수 정렬 (Count Sort)

계수 정렬 (Count Sort)

4-1. 계수 정렬의 특징

계수 정렬은 한국어로는 이름이 조금 어렵다. 그래서 영어 이름을 보면 단박에 의미를 파악할 수 있다.

개수(Count)를 세어 정렬을 하는 정렬 기법이다.

매우 빠르지만, 배열을 활용하므로 정렬 범위가 한정되어 있을 때 가능하다는 특징이 있다.

4-2. 계수 정렬의 동작 과정

빈도수를 세는 배열을 하나 정의한다.

그리고 입력을 받으면 배열의 해당 위치에 개수를 카운팅한다. 예를 들어 1을 하나 입력 받으면 arr[1] 값에 1을 증가시키는 것이다.

모두 입력을 받은 후에, 빈도 값을 저장한 배열을 순차적으로 돌면서 입력 받은 개수만큼 출력해준다.

4-3. 계수 정렬의 시간 복잡도 및 활용 방법

계수 정렬은 데이터의 입력 개수 n에 입력 범위 k를 더한 O(n+k)의 시간 복잡도로 가능하다.

입력 받으면서 개수를 카운팅하고 배열을 돌면서 개수만큼 인덱스를 출력해주는 것이 끝이기 때문에 구현도 간단하고 효율성도 아주 좋다.

특수한 상황에서만 사용 가능하다는 한계점이 있지만, 메모리와 시간이 아주 제한적인 상황에 잘 활용할 수 있을 것이다.

5. Conclusion

정렬은 학부 시절 알고리즘의 가장 처음으로 배우는 내용이었다. 그만큼 많이 쓰이고 중요하다는 의미이다.

어떤 알고리즘을 사용하느냐에 따라 시간・메모리의 효율성이 크게 좌우된다.

절대적인 정답이 없고, 상황에 따라 적절한 알고리즘을 채택하는 것이 필요하므로, 경험과 안목을 키우는 것이 중요하다.

파이썬의 경우 많은 함수들이 최적화되어 함수 형태로 제공되고 있지만, 이런 개념들을 잘 이해하고 필요 시에 직접 구현할 수 있어야 한다.

여러 프로그래밍 문제들을 풀면서 느꼈지만, 알고리즘을 통째로 적용하는 경우는 많지 않았다.

원리와 동작 과정을 온전히 이해하고, 자유자재로 활용할 수 있도록 여러 번 구현하고 설명해보아야겠다.

[백준][그리디] 회의실 배정

타락파워개발자 — Tue, 22 Apr 2025 20:55:11 +0900

오늘의 학습 키워드

정렬, 그리디 알고리즘

오늘의 회고

오늘의 문제

https://www.acmicpc.net/problem/1931

10만 이하의 정수 n이 입력으로 주어지고, 이어서 n개의 회의 시간(시작 시간, 종료 시간)이 주어진다.

하나의 회의실에 대해 최대 몇 개의 회의가 진행될 수 있는지 찾는 문제이다.

이 때 주의할 점은 아래와 같다.

1. 회의 시작 시간과 종료 시간이 동일할 수 있다 → 예: (1, 1) 가능

2. 이전 회의 종료 시간에 다음 회의가 시작할 수 있다. → 예: (1, 3), (3, 5) 가능

나의 시도

최종적으로 정렬 + 그리디 알고리즘으로 이 문제를 해결하였다.

이 문제를 처음 보았을 때 그리디 알고리즘으로 시도해보고, 잡히지 않는 반례가 있을 경우 그래프 탐색으로 접근하고자 했다.

또한 그리디 알고리즘에서는 아래 세 가지 형태로 정렬을 하여 형태를 살펴보았다.

1. 시작 시간 기준 정렬

2. 회의 시간 간격 기준 정렬

3. 종료 시간 기준 정렬

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

# 시작 시간 기준 정렬
res1 = sorted(meetings)
print("시작 시간 기준:")
display(res1)
print()

res2 = sorted(meetings, key=lambda x: (x[1]-x[0]))
print("회의 시간 간격 기준:")
display(res2)
print()

res3 = sorted(meetings, key=lambda x: (x[1], x[0]))
print("종료 시간 기준:")
display(res3)
print()

""" 실행 결과]
[입력]
 11
 1 4
 3 5
 0 6
 5 7
 3 8
 5 9
 6 10
 8 11
 8 12
 2 13
 12 14
 
 [출력]
시작 시간 기준:
[[0, 6],
 [1, 4],
 [2, 13],
 [3, 5],
 [3, 8],
 [5, 7],
 [5, 9],
 [6, 10],
 [8, 11],
 [8, 12],
 [12, 14]]

회의 시간 간격 기준:
[[3, 5],
 [5, 7],
 [12, 14],
 [1, 4],
 [8, 11],
 [5, 9],
 [6, 10],
 [8, 12],
 [3, 8],
 [0, 6],
 [2, 13]]

종료 시간 기준:
[[1, 4],
 [3, 5],
 [0, 6],
 [5, 7],
 [3, 8],
 [5, 9],
 [6, 10],
 [8, 11],
 [8, 12],
 [2, 13],
 [12, 14]]
"""

그리디 접근 방식을 고려하였을 때, 배열을 순차적으로 탐색하면서 결과를 찾는 것이 좋다고 생각하였다.

그리고 정렬 결과를 확인해보았을 때 "종료 시간"을 기준으로 정렬한 결과가 이에 가장 적합하였다.

현재 시점에서 가장 빠르게 종료된 회의를 찾고, 그 값을 기준으로 이후에 시작된 가장 빠르게 종료되는 회의를 찾는 방식이다.

이러한 접근 방식을 통해 아래와 같은 코드를 구현하였다.

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

# 종료시간 기준 정렬
meetings = sorted(meetings, key=lambda x: (x[1], x[0]))

answer, time = 0, -1
for st, en in meetings:
    if st >= time: 
        time = en
        answer += 1
print(answer)

새롭게 알게 된 점

그리디 알고리즘의 원리는 단순하게 느껴졌는데, 실제 적용을 위해서는 다양한 부분을 고려해주어야 한다는 것을 알게 되었다.

이 문제를 통해 주어진 조건 내에서 알고리즘의 적용이나 값의 처리를 어떻게 해주어야 할 지 설계하는 역량을 키울 수 있었다.

오늘의 후기

이 문제는 다양한 시도를 해 본 것에 비해, 왜 이게 잘 동작하는 지에 대한 검증은 잘 되지 않은 것 같다.

이 문제가 왜 그리디하게 접근했을 때 잘 동작하는지, 다른 반례가 더 있지는 않은지 조금 찝찝하다.

제대로 된 설계 없이, 다양한 시도 끝에 괜찮아 보이는 것들로 조합하다 보니 이런 결과를 보인 듯 하다.

그래프 탐색으로 이 문제를 한 번 더 시도해보면서, 왜 이 문제가 그리디로도 충분했는지 한 번 더 고민해보는 시간을 가져야겠다.

[백준][그리디] 잃어버린 괄호

타락파워개발자 — Tue, 22 Apr 2025 19:25:53 +0900

오늘의 학습 키워드

그리디 알고리즘, 문자열

오늘의 회고

오늘의 문제

https://www.acmicpc.net/problem/1541

입력으로 주어진 문자열 중 특정 부분에 괄호를 쳤을 때 가장 작은 값을 만드는 문제이다.

입력으로는 덧셈/뺄셈 부호(+, -)와 숫자로 구성된 문자열이 주어진다.

나의 시도

마이너스 사이에 있는 덧셈 부호를 모두 괄호로 묶어서 가장 큰 값을 빼 주는 방식으로 접근하였다.

따라서 아래와 같은 흐름으로 코드가 진행된다.

1. 문자열을 돌면서 마이너스를 만나면 스위치가 켜진다.

2. 스위치가 켜지면 마이너스 사이의 값들을 스택에 넣어 모두 더해준 다음, 스택의 값을 전체에서 빼준다.

formular = input()

switch = False # 마이너스 부호를 만나면 덧셈 부호를 뺄셈으로 바꿔줄 스위치
st = 0 # 피연산자(숫자)의 시작 위치
answer = 0 # 최종 정답 값

stack = []
for i, c in enumerate(formular):
    if c == '-' or c == '+': 
        operand = int(formular[st:i]) # 피연산자 값
        stack.append(operand)
        st = i+1 # 피연산자 위치 재정의
        if c == '-':
            answer = answer-sum(stack) if switch else answer+sum(stack)
            stack = []
            switch = True
        
        
stack.append(int(formular[st:]))
answer = answer-sum(stack) if switch else answer+sum(stack)
        
print(answer)

위 코드로 1차적으로 구현을 마치고 채점에 통과하였다.

그런데 코드가 깔끔하지 못한 것 같아 정리하는 과정에서 아래와 같은 결론을 도출할 수 있었다.

괄호를 쳐서 그 합을 빼준다는 것은, 괄호 내부의 각각의 항에 -1을 곱해서 음수 항으로 변경해준다는 것과 동일한 의미로 볼 수 있다.

따라서 스택에 넣어서 그 합을 빼 줄 필요 없이, 덧셈 연산이 아닌 마이너스 연산으로 수행해주면 된다.

또한 한 번 이상 마이너스 연산이 등장한 경우, 마이너스 연산 등장 이후의 양수항은 모두 음수항으로 변경된다.

즉, 스위치가 다시 꺼지는 경우가 없다는 것을 확인할 수 있었다.

위 결론을 통해 아래와 같이 코드를 좀 더 간소화할 수 있었다.

'''
모두 합쳐서 뺀다 = 더하지 않고 뺀다
-> 마이너스 뒤에 괄호를 친다는 것은 이후 항을 음수항으로 바꾸는 것이므로 마이너스 등장 후부터 빼주면 됨!
'''
formular = input()

switch = False
st = 0
answer = 0

for i, c in enumerate(formular):
    if c == '-' or c == '+':
        operand = int(formular[st:i])
        st = i+1
        if switch:
            answer -= operand
        else:
            answer += operand
            if c == '-': switch = True

operand = int(formular[st:])
answer = answer-operand if switch else answer+operand

print(answer)

문자열을 따라 반복문을 돌면서 연산자가 나타날 때마다 이전에 등장했던 피연산자에 대해 처리하므로, 시간 복잡도는 O(n)으로 가능하다.

다만 반복문 내부에서 마지막 연산자에 대해 처리해주지 않으므로 반복문 바깥에서 추가로 처리해주었다.

그러나 이것은 O(1)이므로 시간 복잡도에 영향을 주지 않는다.

오늘의 후기

한 번 더 코드를 간소화할 수 있는 방법이 있을 것 같은데 잘 떠오르지 않는다.

그래도 코드를 제출하고 마치는 것이 아니라, 다시 검토해보면서 개선해보는 것은 좋은 습관인 것 같다.

나중에 다시 이 포스팅을 다시 보게 될 때에는 이 코드를 더 간결하게 혹은 더 효율성 좋게 짤 수 있을 것이다.

끝!

[백준][정렬] 시리얼 번호

타락파워개발자 — Tue, 22 Apr 2025 17:54:57 +0900

오늘의 학습 키워드

정렬, 문자열

오늘의 회고

오늘의 문제

https://www.acmicpc.net/problem/1431

오늘의 문제는 문자열을 여러 개의 조건으로 정렬하는 문제이다.

입력으로 50 이하의 정수 n이 주어지고, 이어서 n개의 문자열이 주어진다.

(1) 문자열의 길이(오름차순), (2) 문자열에 포함된 숫자의 합(오름차순), (3) 문자의 사전순 정렬(오름차순)을 기준으로 정렬한다.

나의 시도

파이썬에서 제공하는 sorted 함수를 활용하였다.

이미 최적화 되어 있기에 효율성에서도 적합하고, key 파라미터에 lambda 함수를 이용하여 여러 조건에 대한 정렬이 가능하기 때문이다.

정렬 기준 중 2번 조건에 대해 별도의 함수를 구현해주었고, 이를 lambda 함수에 아래와 같이 추가해주었다.

def serial_sum(serial):
    answer = 0
    for c in serial:
        if '1' <= c <= '9':
            num = int(c)
            answer += num
    return answer

n = int(input())

serials = [input() for _ in range(n)]
serials = sorted(serials, key=lambda x: (len(x), serial_sum(x), x))

for serial in serials:
    print(serial)

새롭게 알게 된 점

다른 사람들의 코드를 살펴보던 중 문자열에서 숫자 값을 추출할 때 re 라이브러리와 정규식을 이용한 방법을 추가로 알게 되었다.

import re
x = "ABCD1234"

re.findall("\d+", x)

findall() 함수를 통해 문자열에 "\d+" 라는 문법을 적용해주면 숫자값만 추출하는 것을 확인할 수 있었다.

이 문제는 숫자만 추출했지만 다른 문제에서는 숫자, 소문자, 일부 특수문자 등 여러 조건의 문자열을 추출하는 문제들이 있었다.

이러한 문제들에 잘 적용하기 위해 정규식도 잘 이해해두어야겠다.

오늘의 후기

문자열이나 정렬 문제는 알고리즘이 어렵진 않은데, 자주 풀어보지 않아서 그런지 함수가 익숙치 않은 것 같다.

그래서 풀고 보면 함수 이름이 낯설지 않은데 바로 떠오르지 않는다는 문제가 있다.

코테 때 잘 활용하려면 더 자주 풀어보고, 블로그에 많이 기록해두어야겠다.

[백준][DFS/BFS] DFS와 BFS (+ 재귀 함수가 아닌 반복문을 이용한 DFS, 우선순위 큐를 이용한 인접 리스트)

타락파워개발자 — Wed, 16 Apr 2025 00:58:27 +0900

오늘의 학습 키워드

DFS, BFS, 스택, 큐, 우선순위 큐

오늘의 회고

오늘의 문제

https://www.acmicpc.net/problem/1260

그래프를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다.

방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다.

나의 시도

1. 인접 리스트 구현

그래프를 나타내기 위해 우선순위 큐를 이용한 인접 리스트를 구현하였다.

이 문제에서는 방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것부터 순회하여야 하기 때문에, 인접 리스트 내부 인덱스는 정렬된 상태로 유지되어야 한다. 우선순위 큐는 힙으로 구현되어 항상 정렬된 상태를 유지하며 삽입/삭제 시 O(log N)의 시간 복잡도를 가지므로, 리스트를 정렬하는 것보다 우선순위 큐를 이용하는 것이 시간 복잡도 측면에서 더 효율적일 것이라고 판단하였다.

n, m, v = map(int, input().split())

# 우선순위 큐를 이용하여 가장 작은 노드부터 고려
adj_list_bfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1
adj_list_dfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1

for _ in range(m):
    st, en = map(int, input().split())
    adj_list_bfs[st].put(en)
    adj_list_bfs[en].put(st) # 양방향 그래프
    adj_list_dfs[st].put(en)
    adj_list_dfs[en].put(st) # 양방향 그래프

이 문제에서는 BFS, DFS 두 함수에 인접 리스트가 필요하다.

그러나 인접 리스트가 2차원 배열이라 얕은 복사 방식으로는 배열을 복사할 수 없었다.

copy 모듈의 deepcopy 함수를 사용하니 컴파일 에러가 발생하여 리스트를 각각 생성해주었다.

슬라이싱 방식으로 깊은 복사도 가능하다고 하는데, 복사를 하는 것과 동일한 배열 두 개 만드는 것 중 어느 것이 더 나을지 모르겠다.

(혹시 이 글을 보는 분 중 이 부분을 더 효율적으로 구현할 수 있는 방법을 아신다면 부디 알려주세요 )

2. 반복문을 이용한 DFS 구현

이전에 재귀 함수를 이용해서 DFS를 구현했다가 RecursionError를 마주한 경험이 있다.

그 때는 sys의 setrecursionlimit()를 이용하여 재귀 함수의 허용 범위를 늘려주었다. (참고: https://developer-zoyh.tistory.com/18)

[백준][DFS] 99클럽 코테 스터디 4일차 TIL + 안전 영역 (+ RecursionError 핸들링 하기)

오늘의 학습 키워드DFS, 시뮬레이션 오늘의 회고 오늘의 문제 https://www.acmicpc.net/problem/2468(왜 미리보기가 안 불러와질까 )2차원 배열이 주어지고 각각의 칸에는 지형의 높이 정보를 나타내

developer-zoyh.tistory.com

그러나 실제 환경에서는 허용 범위를 늘리는 것이 아니라 제한된 메모리 환경 내에서 구현할 수 있어야 한다고 생각하여 반복문으로 DFS를 구현해보았다.

재귀 함수를 호출할 때에는 고려해주지 않아도 되었던 아래 포인트들을 집중 공략해서 구현해보았다.

1. Stack에서 노드를 제거하는 시점

2. 방문 처리하는 시점

3. 현재 노드를 전환해주는 시점

특히, 특정 노드에서 더 이상 방문하지 않은 인접 노드가 없어 스택에서 제거하게 된 경우, 스택에 남아있는 노드 중 최상단 값으로 현재 노드를 변경해주어야 한다. (이 부분을 빼먹어서 한 번 틀렸다..ㅎㅎ)

def dfs(v, adj_list):
    answer = str(v)
    c_node, stack = v, [v] # 시작 노드
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while stack:
        while True:
            # 방문하지 않은 인접 노드가 없는 경우
            if adj_list[c_node].empty(): 
                stack.pop()
                if stack: c_node = stack[-1]
                break

            n_node = adj_list[c_node].get()
            if not visited[n_node]:
                stack.append(n_node)
                answer += f' {n_node}'
                visited[n_node] = True
                c_node = n_node
                break
                
    return answer

이전에 정리했던 DFS의 동작 방식을 보면서 코드를 구현하니 머리로만 생각할 때보다 쉽게 접근할 수 있었다.

(참고: https://developer-zoyh.tistory.com/17)

[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)

0. IntroductionDFS와 BFS를 별도 게시물로 정리하려고 했으나 결국 하나의 게시물로 정리하게 되었다.둘은 이름이 비슷해서인지 잘 헷갈리는 것 같다.같은 게시물 안에서 동일한 그래프로 비교하면

developer-zoyh.tistory.com

3. BFS 구현

DFS를 확실히 이해하고 나니 BFS를 구현하는 것은 어렵지 않았다.

이전에 개념 정리하면서 BFS 코드를 한 번 구현해 보기도 하였고, 현재 노드를 기준으로 인접 노드를 모두 배열에 넣으면 되어서 그런지 구현 난이도가 쉽게 느껴졌다.

def bfs(v, adj_list):
    answer = ''
    que = deque([v])
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while que:
        c_node = que.popleft()
        answer += f'{c_node} '

        while not adj_list[c_node].empty():
            n_node = adj_list[c_node].get()
            if not visited[n_node]: 
                que.append(n_node)
                visited[n_node]=True
    
    return answer

4. 최종 코드

최종적으로 아래와 같이 코드를 완성하였다.

dfs, bfs를 각 함수로 정의하였고, 각 함소를 호출할 때 시작 노드 v와 인접 리스트를 함수에 파라미터로 전달하였다.

dfs는 스택, bfs는 큐와 함께 구현하였으며 두 코드 모두 반복문을 사용하였다.

from queue import PriorityQueue
from collections import deque

def dfs(v, adj_list):
    answer = str(v)
    c_node, stack = v, [v] # 시작 노드
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while stack:
        while True:
            # 방문하지 않은 인접 노드가 없는 경우
            if adj_list[c_node].empty(): 
                stack.pop()
                if stack: c_node = stack[-1]
                break

            n_node = adj_list[c_node].get()
            if not visited[n_node]:
                stack.append(n_node)
                answer += f' {n_node}'
                visited[n_node] = True
                c_node = n_node
                break
                
    return answer

def bfs(v, adj_list):
    answer = ''
    que = deque([v])
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while que:
        c_node = que.popleft()
        answer += f'{c_node} '

        while not adj_list[c_node].empty():
            n_node = adj_list[c_node].get()
            if not visited[n_node]: 
                que.append(n_node)
                visited[n_node]=True
    
    return answer

''' MAIN 구현부 '''

n, m, v = map(int, input().split())

# 우선순위 큐를 이용하여 가장 작은 노드부터 고려
adj_list_bfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1
adj_list_dfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1

for _ in range(m):
    st, en = map(int, input().split())
    adj_list_bfs[st].put(en)
    adj_list_bfs[en].put(st) # 양방향 그래프
    adj_list_dfs[st].put(en)
    adj_list_dfs[en].put(st) # 양방향 그래프


print(dfs(v, adj_list_bfs))
print(bfs(v, adj_list_dfs))

오늘의 후기

드디어 재귀 함수를 사용하지 않고 DFS를 구현할 수 있게 되었다!

RecursionError가 발생하는 게 찝찝했는데 드디어 해결할 수 있게 되어서 기쁘다.

또 우선순위 큐, 덱, 스택과 같이 기존에 개념으로만 이해하고 있던 자료구조들을 직접 코드를 통해 다뤄보게 되어 반갑고 좋았다.

앞으로 익숙해질 수 있도록 자주 활용해보려고 한다.

[알고리즘] 동적 계획법 (Dynamic Programming) + 메모이제이션(Memoization)

타락파워개발자 — Tue, 15 Apr 2025 19:16:43 +0900

1. 소개

~~동적 계획법은 해결하려는 문제를 작은 단위로 쪼개어 접근하는 방식이다. 사전 계산된 값을 여러 번 재활용할 때 효율적이다.~~

(DP를 정의할 때 '문제를 쪼개는 것'에 초점을 맞추는 것이 DP 이해에 방해가 된다고 판단하여 아래 내용으로 수정합니다.)

동적 계획법은 연산 속도를 개선하기 위해 문제를 재설계하는 기법이다.

사전에 계산된 값을 재연산 하지 않기 위하여 결과를 저장해둔다. 이를 위해 적절한 단위로 문제를 쪼개는 것이다.

즉, 동적 계획법에서 중요한 포인트는 문제를 쪼개는 것이 아니라, 연산이 여러 번 되는 것을 막기 위하여 문제를 재설계하는 것이다.

이 과정에서 메모리를 활용하거나 더 작은 단위의 문제로 쪼개어지는 과정이 필요할 수도 있다. (2025.04.28 수정)

나무위키에 와닿는 정의가 있어 아래에 추가한다.

동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. ( 출처: 나무위키 - 동적 계획법 )

대표적인 예시로는 피보나치 수가 있다.

피보나치 수는 동일한 부분 함수를 여러 번 호출하므로, 중간 결과를 저장해두면 전체 연산을 효율적으로 수행할 수 있는 대표적인 DP 문제이다.

피보나치 수의 정의부터 알아보자. 피보나치 수열은 첫 번째, 두 번째 항이 1이고 그 외의 모든 항은 이전 두 항의 합으로 구성된 수열이다. 즉, n번째 피보나치 수를 구하기 위해서는 n-1번째, n-2번째 피보나치 수를 구해야 한다.

피보나치 수열 n=6일 때 재귀 호출 횟수

위 그림은 피보나치 수열의 6번째 항을 구하는 알고리즘을 시각화한 것이다.

피보나치 함수를 F()라고 정의할 때, F(6)=F(5)+F(4) 이므로 F(6) 항을 구하기 위해서는 F(5), F(4)가 호출되어야 한다. 또한 F(5)=F(4)+F(3)이므로 F(4)와 F(3)이 호출되어야 한다.

여기서, F(6)과 F(5)를 구하는 과정에서 F(4)가 두 번 호출된 것을 알 수 있다.

위 이미지를 자세히 보면, F(6)을 구하는 과정에서 F(4) 외에도 부분 함수들이 여러 번 호출되고 있음을 확인할 수 있다.

동적 계획법에서는 이렇게 동일한 값을 여러 번 계산해야 하는 경우, 처음에만 연산한 후 메모리에 저장해두고 재사용한다.

2. 세부 방식

Dynamic Programming ❘ Top-down vs Bottom-up

2-1. Top-Down 방식

1. 정의

큰 문제를 계속해서 작은 문제로 분할하며 푸는 방식이다. 위 소개에서 보여준 예시가 Top-Down 방식이라고 볼 수 있다. F(6)을 구하기 위해 F(5)와 F(4)로 쪼개고, 다시 F(5)를 F(4)와 F(3)으로 쪼개고... 이 과정을 반복하며 가장 작은 문제로 분할한다.

대체적으로 재귀함수를 많이 활용한다.

2. 장점

직관적인 접근 방식으로 특정한 규칙을 찾기 어려운 경우에도 적용이 가능하다.

메모이제이션 기법과 결합하여 시간 복잡도를 개선할 수 있다.

3. 한계점

코드를 실행하는 환경의 스택 크기가 한정되어 있어 재귀 함수의 사용이 일부 제한될 수 있다.

메모리를 과도하게 사용하지 않도록 주의해야 한다.

2-2. Bottom-Up 방식

1. 정의

가장 작은 문제부터 쌓아 올려 점점 큰 문제를 푸는 것이다. 피보나치 문제를 예로 들자면 낮은 항부터 점차 상위 항으로 구해가는 방식을 예로 들 수 있다. 피보나치는 F(1)과 F(2)가 1이라는 특성이 있는데, 이 특성을 이용해서 작은 값부터 목표하는 값까지 구할 수 있다.

전체 문제를 통달하는 점화식이 존재하는 경우 이 방식을 적용할 수 있다. 피보나치 수열의 점화식은 F(n) = F(n-1) + F(n-2) 이다.

2. 장점

반복문을 이용하여 구현할 수 있으므로 메모리 측면에서 자유롭고, 속도가 빠르며, 코드가 간결하다.

점화식을 이용하므로 부분 식을 통해 전체 문제를 이해할 수 있다.

3. 한계점

점화식을 찾지 못 하는 경우 구현이 어렵다.

* Top-down 방식을 통해 문제를 풀어본 후 점화식을 찾는다면 Bottom-up 방식으로 변경하는 것도 좋은 방법!

3. 관련 개념: 메모이제이션(Memoization)

동적 계획법은 과거에 구한 해를 활용하여 문제를 해결하는 기법이다. 이 때, 이 과거에 구한 해를 다시 구하지 않도록 저장해두는(메모해두는) 기법을 "메모이제이션" 이라고 한다. 캐싱(Caching)이라고 부르기도 한다.

동적 계획법에서 메모이제이션과 결합하여 메모리를 활용하는 대신 시간 복잡도를 개선할 수 있다.

메모리에 값을 저장하는 기법도 세분화하자면 Top-down 방식에서 사용하는 방식이 메모이제이션이고, Bottom-up 방식에서는 타뷸레이션(Tabulation)이라는 별도의 방식이 존재한다.

그러나 아직 두 개념을 구분해야 하는 필요성을 명확하게 인지하지 못 했기에 두 개념에 대한 설명은 생략한다.

4. 다음 학습할 내용: 백트래킹(Backtracking)

동적 계획법으로 구할 수 있는 알고리즘은 모두 백트래킹을 이용하여 풀 수 있다고 한다.

동적 계획법이 시간은 더 빠르지만 메모리를 과도하게 사용하는 경향이 있기에, 메모리 제한이 있는 상황에서 백트래킹 알고리즘을 사용하면 좋다고 한다.

DFS, BFS, DP를 마무리한 후 백트래킹 알고리즘을 공부할 예정이다.