자료구조

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[BJ3190] 뱀
🚩 문제 설명 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 적어도 O(N^2) ◾ 벽에 부딪히거나, 자기자신에 닿지않고서 뱀의 이동경로가 끝났을 시 걸린 시간을 구하는 문제 ◾ 벽에 부딪히거나, 자기자신에 닿으면 게임 오버 ◾ 뱀은 매초마다 움직이며, 처음 뱀의 길이는 1입니다. ◾ 사과를 먹으면 뱀의 몸 길이가 1씩 늘어납니다. (사과는 먹으면 없어져야합니다. 이를 주의하시길 바랍니다.) ◾ 뱀은 맨 좌측 상단에서부터 시작됩..
→2022.04.28
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ1918] 후위 표기식
🚩 문제 설명 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 문자열의 길이를 N이라고 가정한다면 대략적으로 O(N^2)의 시간복잡도가 걸린다. ◾ 중위 표기식을 후위 표기식으로 변환하는 문제 ◾ 차량기지 알고리즘 (Shunting-yard Algorithm) 중위 표시식을 후위 표기식으로 바꾸는 알고리즘이다. 연산자를 저장하는 스택을 기반으로 이루어져 있다. 1. 연산자는 스택에 push 한다. 2. 해당 연산자 우선순위
→2021.11.29
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ11656] 접미사 배열
🚩 문제 설명 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ 문자열의 길이를 N이라고 가정한다면, ▪ 시간복잡도는 O(N)이라고 할 수 있다. ◾ 문자열의 모든 접미사를 출력하는 문제 ◾ 사전순으로 정렬하여 출력해야 한다. ✅ 입출력 1) 문자열 S가 주어진다. return ➡️ 모든 접미사를 정렬한 다음 출력 ✔️ 예제 1 baekjoon aekjoon baekjoon ekjoon joon kjoon n on oon 📑 문제 풀이 with 파이썬 (Python) import sys line = sy..
→2021.11.29
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ10824] 네 수
🚩 문제 설명 https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net ⏱️ 시간 복잡도 ▪ 각각의 자연수의 최대 크기는 100만에 해당한다. ▪ 이어붙이는 데 O(1)의 시간복잡도가 걸린다. ▪ 그리고 두 개의 합을 구하는데 O(1)의 시간복잡도가 걸린다. ▪ 따라서 시간복잡도는 O(1)로 해결할 수 있다. ◾ A, B, C, D 네 수가 주어지고 해당 수를 두개씩 이어붙인다. ◾ 이어붙인 AB와 CD의 합을 구하여 출력하는 문제. ✅ 입출력 1) 네 자연수가 공백을 기준으로 주어진다. return ➡️ AB와 CD의 합을 구하여 출력한다..
→2021.11.29
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ11655] ROT13
🚩 문제 설명 https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ 문자열의 크기가 N이라고 가정한다면, 시간 복잡도는 O(N)에 해당한다. ◾ ROT13 암호화 카이사르 암호의 일종 영어 알파벳을 13글자씩 밀어서 만든다. 해당 암호문을 복호화 할려면 다시 ROT13 하면 된다. ROT13은 알파벳 대/소문자에만 적용할 수 있다. ◾ 만약 알파벳이 아닌 숫자가 나온다면 원래 글자 그대로 남아 있어야 한다. ◾ 주어지는 문자열을 ROT13 에 맞게 암호화 하는 문제. ✅ 입출력 1) 암호화 해야할 ..
→2021.11.29
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ1935] 후위 표기식2
🚩 문제 설명 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 알파벳을 숫자로 치환해야하기 때문에 ▪ 주어지는 후위표기식에서 알파벳의 수를 M, 주어지는 숫자의 갯수를 N이라고 가정하면 ▪ 시간복잡도는 O(MN)을 따른다. ◾ 후위표기식으로 문제가 주어질 때 식을 계산하여 출력하는 문제 ◾ 중위 표기식 (Infix Notation) 일반적으로 사용하는 표기식 연산자를 피연산자들 사이에 두는 방식 ex) 2+1, ..
→2021.11.29

• 이전
• 1
• 2
• 3
• 4
• 다음