본문 바로가기

Problem Solving/boj

(68)
[BOJ]1593. 문자 해독(Python) / Sliding Window 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열 S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다. 사용 알고리즘 : Sliding Window 처음에 순열 구하는 코드로 접근했으나 시간초과로 틀리는 것을 보고, 슬라이딩 윈도우 방식으..
[BOJ] 21609. 상어 중학교(Python) / Simulation 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 2021 상반기 삼성 SW역량테스트 기출문제이다. 이번에 출제된 4문제 중 내 기준 가장 까다롭고 시간이 많이 든 문제였다.. BFS의 효율을 높이기 위한 전략이 필요했다. 완전 구현 문제로 고도의 집중력을 발휘해야 한다. 특별히 사용한 알고리즘은 가장 큰 그룹 찾을 때와 이를 지울 때의 BFS 정도이고, 완전 구현 문제이다. 사용 알고리즘 : Simultaion (+ BFS) 사용 자료구조 : Max Heap(최대 힙) 1번 조건 - "크기가 가장 큰 블록 ..
[BOJ] 21611. 마법사 상어와 블리자드(Python) / Simulation 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net # 2시간 30분 소요 사용 알고리즘 : 없음. 완전 구현(Simulation) 설명은 아래 주석으로 달아놓았다. 구슬 파괴 > 구슬 이동 > 이동 함수 안에서 구슬 폭발 > 구슬 변화 > 구슬 재배치 순으로 함수를 구성했다. 구슬 폭발 함수 explodeMarbles() 와 구슬 변화 함수 changeMarbles()는 복붙으로 만들어 매우 유사한 기능을 하고, 구슬 이동 함수 moveMarbles() 와 구슬 재배치 함수 drawMarbles..
[BOJ] 21608. 상어 초등학교(Python) / Simulation 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 2021 상반기 삼성전자 기출문제로, 실버 1로 책정된 쉬운 문제다. 요즘 추세는 특정 알고리즘 사용 없이 빡구현! 인가 보다. 사용 알고리즘 : Hash(딕셔너리), Heap(최대 힙) 크게 설명할 것 없이 문제에 주어진 3개의 조건을 우선순위 큐로 사용한 최대 힙으로 구현했다. heap을 최대힙으로 사용하려면 push할 때 원소에 '-'를 붙여서 push하면 된다! heappop(hq)하면 우선순위가 가장 높은 원소가 나온다! 또 하나, 내가 저지른..
[BOJ] 21610. 마법사 상어와 비바라기(Python) / Simulation 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net # 2021 상반기 삼성전자 코딩테스트 기출 문제다. 백준에 복원문제가 업로드되어 풀어봤다. # 요새 삼성 SW역량테스트 추세가 완전 쌩 구현인 듯 싶다. # 1시간 41분 소요,, 쉬운 시뮬레이션 문젠데 너무 오래 걸렸다. 사용 알고리즘 : 특별한 알고리즘은 없다. 주어진 대로 그대로 구현하면 됨! 아래 주석으로 꼼꼼하게 설명해놓았다! 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline # 8방향 ..
[BOJ] 1747. 소수&팰린드롬(Python) 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 사용 알고리즘 : 소수판별 알고리즘(제곱근까지 구함) N을 1씩 늘려가며 팰린드롬이고 소수인 조건을 만족시키는 즉시 반..
[BOJ] 4358. 생태학(Python) 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 사용 자료구조 : 해시(Hash) 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline nameInfo = dict() # 나무 이름 등장 횟수 nameSet = set() # 중복 없앤 이름 리스트 cnt = 0 while..
[BOJ] 9935. 문자열 폭발(Python) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 처음 풀었을 때 시간초과 나서, 다른 분 풀이 보고 스택을 써야한다는 아이디어를 얻어 다시 코딩해서 pass했다. 사용 자료구조 : 문자열 + 스택 코드 설명 아래 주석에 달아놓았다. 핵심 아이디어는 폭발 문자열의 마지막 글자가 현재 탐색하는 문자와 같고, 폭발 문자열과 스택에 폭발 문자열의 길이만큼의 문자열이 같다면, 스택에서 폭발 문자열의 길이만큼 pop() 해준다. 마지막 문자까지 모든 탐색이 끝났을 때, 스택에 남아있는 문자가 있다면 스택을..