문제 백준 1107번 리모컨 문제를 해결했습니다. https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 ..

목표 순차적 자료구조인 큐의 개념에 대해서 알아보겠습니다. 개요 저번 포스팅에서는 순차적 자료구조인 스택에 대해서 알아보았습니다. 큐(Queue)는 스택과 비슷한 부분들이 많기 때문에 비교하면서 큐에 대해서 이해하는 시간을 갖도록 하겠습니다. 큐(Queue)란? 큐(Queue)는 스택과 비슷한 형태를 가집니다. 다만, 스택은 LIFO(Last In First Out) 구조로 마지막에 들어온 데이터가 제일 먼저 나가는 형태입니다. 큐는 FIFO(First In First Out) 구조로 맨 처음 들어온 데이터가 먼저 나가는 형태입니다. 예를 들어, 마트에서 줄 서는 것을 생각할 수 있겠네요. 스택에서는 Push, Pop, Len, Top 4가지 연산을 지원했습니다. 큐는 Enqueue, Dequeue, i..

개요 자료구조에서 배운 스택을 활용해서 백준 알고리즘 문제를 풀어보겠습니다. 참고 - [자료구조] 스택(Stack)이란? 스택을 활용해 괄호쌍 확인하기 제가 저번에 포스팅 했던 글입니다. 스택의 개념을 이해하면서 비슷한 예제를 풀었었는데요. 그 예시보다 조금 높은 난이도의 문제입니다. 문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과..

목표 스택을 활용해서 중위 표기법으로 입력한 연산을 후위 표기법으로 변환해서 결과를 출력하는 프로그램을 작성해보겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 수식 표기법 스택 예제 : 중위 표기법을 후위 표기법으로 변환하여 계산하는 계산기 정리 개요 저번 포스팅에서 스택에 대해서 복습했습니다. 스택은 LIFO(Last In First Out) 구조를 갖는 자료구조입니다. 마치 접시와 같이 마지막에 들어간 데이터가 맨 처음 나오는 구조로, 파이썬의 클래스를 활용해서 구현했습니다. 클래스 안에 멤버 리스트를 생성해서 append, pop 함수로 스택을 만들었습니다. 이번 포스팅에서는 스택을 활용해서 중위 표기(infix)로 입력된 수식을 후위 표기(postfix)로 바꾸고 계산하는 프로그램을 작성해보도록..

문제 왕이 마실 와인 8병 중 하나에 강력한 독이 들어 있다. 한 방울만이라도 치명적이다. 정상 와인을 아무리 섞어도 치명적이다. 다행히 검사장비를 구할 수 있다. 단, 검사는 1시간이 필요하다. 왕은 무조건 1시간 후에 와인을 마실테니 독이 든 병을 찾아내라는 명령을 내렸다. 이를 위해, 몇 대의 검사 장비가 있으면 충분할까? (한 번 검사할 때에는 여러 병의 와인을 섞어 검사가 가능하다.) 풀이 와인 8병을 검사하는데 최소한의 검사 장비로 해결해야하는 문제입니다. 8병의 와인이지만 사실 7병만 검사하면 충분합니다. (모두 독이 안들어있으면 검사안한 병에 독이 있으니까요.) 최대 7대의 검사 장비가 있으면 편하지만, 최소한의 검사 장비로 하는 것이 중요하기 때문에 다음과 같이 생각했습니다. 와인을 일자..

목표 예시를 통해서 시간 복잡도에 대한 개념을 이해하도록 하겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 예시로 이해하는 시간 복잡도 다양한 함수로 완벽하게 이해하기 정리 개요 저번 포스팅에서 알고리즘의 성능 평가를 위해서 시간 복잡도(Time Complexity)라는 개념을 이용한다고 했습니다. 사람들마다 H/W, S/W 환경이 다르기 때문에 가상 컴퓨터(Virtual Machine)에서 가상 언어로 이루어진 가상 코드를 사용해서 알고리즘의 성능을 평가합니다. 포스팅 마지막에 가상 코드의 예시를 확인하면서 마무리했는데요. 이번 포스팅에서는 마지막에 확인한 코드를 보면서 시간 복잡도를 이해하는 시간을 갖겠습니다. 예시로 이해하는 시간 복잡도 알고리즘의 성능 평가는 알고리즘의 수행 시간을 비교해서 진행..

개요 알고리즘, 자료구조에 관심이 있는 사람이라면 백준을 다 알고 계실 것이라고 생각합니다. 자료구조를 복습하고 있고, 알고리즘은 아직 배우지 않은 상태인데요. 이렇게 알고리즘에 대한 배경지식이 전무한 상태로 문제를 풀 기회가 생겨서 한 번 풀어봤습니다. https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉..

목표 인류 최초의 알고리즘인 최대 공약수를 구하는 알고리즘에 대해 알아보도록 하겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 알고리즘(Algorithm)의 어원 최대 공약수(GCD) 계산 알고리즘, 유클리드 호제법 GCD를 파이썬으로 구현하기 마치며.. 개요 다음 학기에 배울 알고리즘을 준비하기 위해 자료구조를 복습하기로 했습니다. 이번 포스팅에서는 최초의 알고리즘인 최대 공약수를 구하는 알고리즘에 대해 알아보도록 하겠습니다. 알고리즘(Algorithm)의 어원 9세기에 현재 이란, 이라크 지역인 페르시아에서 대수학에 재능이 있던 수학자가 있었습니다. "알 - 카와리즈미(Al-khwarizmi)" 라는 수학자인데, 대수와 0에 관한 책을 페르시아어로 썼습니다. 이 책이 번역되서 유럽에 라틴어로 넘어가..