본문 바로가기

Problem Solving

 (93)
[Programmers] 수식 최대화(Python) / 2020 카카오 인턴십 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 2020 카카오 인턴십 기출문제이다. Level2 인데 생각보다 까다로웠다. 사용 알고리즘 : 순열, 구현 처음 참고한 코드는 아래 링크로 남겨둔다. 저 분의 코드 흐름은 같으나, 난 permutation 라이브러리로 순열을 구현해 반복문으로 가장 순위가 높은 순으로 계산했다. 계산 시에는 eval 함수로 나온 정수를 다시 문자열로 바꾸며 계속 계산을 진행했다. grapetown.tistory.com/63 파이썬 코드는 다음과 같다. from itertools..
[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..
[Programmers] 정수 삼각형(Python) / Dynamic Programming 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr # 14분 소요 사용 알고리즘 : Dynamic Programming(동적 계획법) (가장 아래 행-1) 행부터 가장 아래 행의 값들을 참고해 더 큰 값을 선택해 더하면서 현 위치 값을 갱신해 올라온다. 가장 상단 행까지 값을 모두 채우면 첫 값(triangle[0][0])을 리턴한다. 파이썬 코드는 다음과 같다. def solution(triangle): for r in range(len(triangle)-2, -1, -1): for c in range(r+1): triangle[r][c] += max(triangle[r+1][c], ..
[Programmers] 등굣길(Python) / Dynamic Programming 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 사용 알고리즘 : Dynamic Programming(동적 계획법) 맵의 크기보다 행 + 1, 열 + 1 크기만큼 크게 만든다. 시작 위치(1, 1)는 넘어가고, 물 웅덩이(-1) 표시된 부분은 0으로 바꿔줌. 이외의 위치별로 좌, 상 방향의 숫자들을 더하며 끝까지 채운다. 가장 오른쪽 하단의 값(A[n][m])을 주어진 값(100,000,000,007)으로 나눈 나머지를 리턴한다. 파이썬 코드는 다음과 같다. def solution(m, n, pud..
[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방향 ..

티스토리툴바