Programming/PS
-
백준 10799번 쇠막대기: C언어 풀이Programming/PS 2023. 9. 29. 01:27
백준 10799 쇠막대기 문제의 C언어 해설입니다.스택 자료구조 대신 이전에 등장한 문자를 저장하여 문제를 해결한 방법을 설명합니다.전략조각을 세는 방법작업대에서 쇠 막대기를 자르는 기계가 있다.편의상 막대의 길이는 무한하다고 가정해보자.작업자에게 내릴 수 있는 명령은 다음 4가지이다.작업대에 막대를 놓는다.작업대에서 막대를 치운다.작업대에 놓인 막대를 자른다. 잘린 왼쪽 조각을 조각 통에 넣는다.사람마다 다를 수 있겠지만, 이렇게 생각하면 상황이 좀 더 명확해진다.작업대 위 막대 수를 aligned_sticks, 조각 통 속 막대 수를 cut_sticks라고 하자.작업대에 막대를 놓으면 aligned_stics가 하나 추가된다.작업대에서 막대를 치우면 aligned_sticks가 하나 감소한다.작업대에..
-
백준 1874번 스택 수열: C언어 풀이 (C++, Python)Programming/PS 2023. 9. 29. 00:45
백준 1874 스택 수열 문제 해설입니다.스택을 활용한 기본적인 방법과, 문제의 제한 조건을 활용환 최적화된 방법을 C언어로 상세히 설명합니다.최종 코드는 C++과 파이썬 버전도 함께 적어두었습니다.전략스택 만들기스택 수열이니 스택을 만들어준다.수열의 원소가 주어졌을 때 필요한 조작을 push 파트와 pop 파트로 나눌 수 있다. push 파트에서는 필요한 만큼 숫자를 스택에 넣어준다.원소가 7이면 1부터 7까지 push해주면 된다. 이미 넣은 숫자는 다시 넣으면 안된다.push_waiting 변수를 정의해서 1~n 중 얼마나 스택에 넣어는지를 저장한다.pop 파트에서는 필요한 원소가 나올 때까지 pop해준다.스택이 비었는데도 원소가 나오지 않으면 NO를 출력하고 프로그램을 종료하면 된다.출력pus..
-
백준 12605번 단어 순서 뒤집기: C 언어 풀이Programming/PS 2023. 9. 17. 01:58
백준 12605 단어 순서 뒤집기 문제의 C언어 풀이 해설입니다.연결 리스트로 스택 자료구조를 구현하여 단어 순서를 뒤집는 방법을 설명합니다. 전략연결리스트로 구현한 스택단어 단위로 하나씩 스택에 넣어주고 위에서 부터 하나씩 뽑아준다. 자연스럽게 단어 순서가 역순으로 출력된다.여기서 단어의 개수가 딱히 주어지지 않았으므로, 스택을 연결 리스트로 구현하였다.입력 받기단어의 개수가 주어지지 않아 입력을 받는 게 까다롭다. fgets() 같은 걸 쓸 수 없다.이에 두 가지 방안을 생각해 봤다.scanf() + getchar()scanf()로 단어 단위로 읽고, 그 다음 getchar()를 한 번 호출한다.개행문자(\n)가 나오면 문장을 다 읽은 것이다.getchar()로 한 글자씩 받기말 그대로 한 글자씩 받..
-
백준 3217번 malloc: C언어 풀이Programming/PS 2023. 9. 16. 21:31
백준 3217번 malloc 문제의 C 언어 풀이 해설입니다.연결 리스트와 유사하게 동작하면서도 주소를 통한 빠른 접근이 가능하도록 배열을 이용해 메모리를 구현하는 방법을 소개합니다.변수명과 할당된 주소를 시간복잡도 O(1)에 찾을 수 있도록 해시 테이블을 구현하여 풀이하였습니다.전략메모리 구성메모리를 연결 리스트와 유사한 배열로 구성한다. 이전 철도 공사 문제 풀이 와 유사한 아이디어이다.연결 리스트 대신 이전, 다음 원소의 인덱스를 갖는 하나의 구조체를 배열에 넣어주면 배열이 가지는 빠른 접근 속도와 연결 리스트의 연결성, 두마리 토끼를 잡을 수 있다.여기서는 구조체를 같은 속성을 갖는 메모리의 구간으로 정의했다. 각 구간은 할당 여부(FREE/ALLOCATED), 구간의 크기, 이전 구간의 인덱..
-
백준 23309번 철도 공사: C언어 풀이Programming/PS 2023. 9. 11. 06:12
백준 23309번 철도공사 문제의 C 언어 풀이 해설입니다.연결 리스트를 배열로 대체하여 시간 초과를 해결하는 방법을 소개합니다.전략원형 연결 리스트 쓰지 않기노드 만들고, 메모리 할당하고, 연결하고... 열심히 만들어봐도 계속 시간 초과가 났다.역시 기본 개념만으로 골드 문제의 벽을 넘는 건 불가능한가? 라고 생각하던 와중에 하나의 아이디어가 떠올랐다.고유번호 i를 찾는 작업은 일반적인 연결 리스트에서 O(n)이 걸린다.이때 고유번호 i를 인덱스로 갖는 배열을 만들면 O(1)으로 찾을 수 있다.보통 연결 리스트는 앞/뒤 노드를 가르키는 포인터를 갖는다.배열도 마찬가지로 앞/뒤 노드의 인덱스를 같이 넣어주면 연결 리스트 처럼 사용할 수 있다.정수형으로 다음 역 번호와 이전 역 변호를 갖는 구조체 stru..
-
백준 1406번 에디터: C언어 풀이Programming/PS 2023. 9. 11. 04:29
백준 1406번 에디터 문제의 C 언어 풀이입니다.연결리스트를 사용한 구현 방식을 소개합니다.전략연결 리스트를 이용한 구현스택을 이용한 풀이도 있는 것 같지만 아직 안배웠으니 패스.정직하게 연결 리스트로 구현했다. "명령어가 수행되기 전 커서는 문장의 맨 뒤에 위치하고 있다고 한다"이 조건을 위해 끝에 NUL(\0) 문자를 넣어 두었다.조건 처리가 훨씬 편리해진다.코드#include #include enum operations{ LEFT = 'L', RIGHT = 'D', DELETE = 'B', PREPEND = 'P'};struct node{ char letter; struct node *next; struct node *prev;};void prepend(str..
-
백준 3273번 두 수의 합: C언어 풀이Programming/PS 2023. 9. 11. 03:55
백준 3273번 두 수의 합 문제의 C 언어 풀이 해설입니다.배열을 이용해 숫자의 등장 여부를 체크하는 방식으로, 시간복잡도 O(n)으로 두 수의 합이 특정 값이 되는 쌍의 개수를 구하는 방법을 설명합니다.전략원소의 등장 여부를 기록하는 Lookup 배열주어진 합이 10, 수열이 2, 6, 4 순서라고 해보자.첫번째 원소는 2다. Lookup 배열에서 10 - 2, 8을 찾아본다. 없다.2를 Lookup 배열에 등록한다.두번째 원소는 6이다. Lookup 배열에서 10 - 6, 4를 찾아본다. 있다.6을 Lookup 배열에 등록한다.세번째 원소는 4다. Lookup 배열에서 10 - 4, 6을 찾아본다. 있다.조건을 만족하는 쌍을 발견했으므로 카운트를 더해준다.찾은 경우 굳이 Lookup 배열에 등록할 ..