https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 난이도 : 실버 5 태그 : 그리디, 문자열 설명 주어진 문자열로 UCPC라는 약자를 도출할 수 있는지를 판단하는 문제입니다. 초기 아이디어는 리스트를 하나 두고, 사용한 문자열을 하나씩 빼면서 리스트가 비면 도출 가능하다고 판단했었는데, 생각해보니 U - C - P - C 순으로 해야더라고요... 결국 UCPC 중 몇 번째 문자열까지 가능한지 체크할 포인터 변수 하나를 두..
이번에 알아볼 것은 굉장히 유명한 자료구조 삼대장들인 스택(Stack), 큐(Queue), 데크(Deque) 입니다. 스택 (Stack) 스택은 자료구조의 맨 위에서만 삽입과 삭제가 일어나는 자료구조 입니다. 포인터가 맨 위를 가르키고 있어, 데이터의 가장 위에서만 삽입과 삭제가 일어나지요. 가장 나중에 들어간 원소가 가장 빨리 나오는 LIFO(Last in - First out) 구조 입니다. PUSH를 통해 원소를 삽입, POP을 통해 원소를 꺼냅니다. 이는 쌓아놓은 접시와 비슷합니다. 접시를 쌓을 때는 보통 가장 윗 접시부터 꺼내 쓰곤하죠? 컨트롤 + z를 눌러 뒤로가기를 하는 것도, 브라우저의 뒤로가기도 스택의 예시 중 하나입니다. 자바의 Stack 클래스 출력 : 10, 10, 5, 3 자바에서..
이번에 알아볼 것은 그래프 탐색의 대표적인 방법인 그래프의 표현 방법인 인접 리스트와 인접 행렬입니다. 그래프와 트리에 관한 내용은 이전 포스팅을 참고해주세요. https://uknowblog.tistory.com/357 [자료구조] 그래프(Graph)와 트리(Tree) - 점과 선의 예술 그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어 uknowblog.tistory.com 그래프의 연결 표현 : 인접 배열과 인접 리스트 그래프의 연결을 표현하는 방법에는 인접 배열과 인접 리스트가 있습니다. 이름처럼 배열을 썼느냐, 리스트를 썼느냐의 차..
그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어진 형태입니다. 그래프의 시초 위 두 개의 그림은 다들 수학시간때 한 번씩 본 그림일텐데요. '쾨니히스베르크 다리 건너기' 문제입니다. 쾨니히스베르크(현 러시아 칼리닌그라드) 중앙에는 섬이 있는데, 7개의 다리를 단 한 번씩만 모두 건널 수 있느냐? 라는 문제입니다. 이걸 단순화 시킨게 아래의 그림인데, 각 육지를 점, 다리를 선으로 나타낸 것이 그래프의 시초 중 하나라고 추측되고 있습니다. 참고로 위 문제는 '한 번씩 모두 건널 수 없다'라는 것이 수학적으로 증명되었으며, 자세한 내용은 오일..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 문자열, 스택 설명 모든 왼쪽 괄호는 오른쪽 괄호와 맞아야 합니다. [](), [()] 등은 맞지만, ([], ([)] 등은 맞지 않습니다. 스택을 활용하기 좋은 문제일 것 같네요. [()]을 예로 들겠습니다. 첫 번째 글자 : [ stack에 문자를 넣습니다. 현재 스택 : [ 두 번째 글자 : ( stack이 비어있지 않으나, 가장 ..
https://www.acmicpc.net/problem/11328 11328번: Strfry C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래 www.acmicpc.net 난이도 : 브론즈 2 태그 : 구현, 문자 설명 두 개의 문자열을 입력받고, 한 문자열을 적절히 재배치하여 다른 문자열을 만들 수 있는지 판단하는 문제입니다. 즉 애너그램인지 판단하는 것이죠. https://namu.wiki/w/%EC%95%A0%EB%84%88%EA%B7%B8%EB%9E%A8 애너그램 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수..
https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 난이도 : 브론즈 2 태그 : 구현, 문자열 설명 26개의 배열을 선언하고 -1로 초기화한뒤, A ~ Z, 각 문자가 처음으로 나오는 순간이 몇 번째인지 저장합니다. 첫 번째로 나오는 순간이므로, -1인지 확인 후 업데이트 하는게 주의점입니다. 소스코드 #include #include int main() { char str[100]; scanf("%s", str); int result..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 난이도 : 실버 2 태그 : 자료구조, 스택, 연결리스트 시도 1 간단히 생각해보면, 스택이나 리스트 하나를 만들어두고 커서의 위치를 담을 cursorIdx 변수를 만들어 특정 위치에서 add 혹은 remove를 하면 쉽게 풀릴 것 같네요 import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val wor..
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 난이도 : 실버 2 태그 : 브루트포스, 백트래킹 설명 배열의 순서를 적절히 섞어 위 식의 최댓값을 찾는 문제였습니다. 처음에는 위 식을 |A[0] - A[1]| + |A[2] - A[3]| 과 같이 두 식의 차이의 절대값 인줄 알고 그리디로 접근하면 되겠지? 싶었는데 |A[0] - A[1]| + |A[1] - A[2]| 였습니다 ㅎㅎ; 😭 흠... 그럼 두 번째 방법으로, 백트래킹으로 모든 경우의 수를 탐색하..
https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체 설명 골드바흐 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측입니다. 아직 수학적으로 증명되지 않았기에 추측이라고 불립니다. 4보다 큰 짝수를 두 홀수 소수의 합으로 나타낼 수 있을 경우, 두 소수의 차이가 가장 큰 두 수를 출력, 나타낼 수 없을 경우 "Goldb..