https://www.acmicpc.net/problem/17547 17547번: Floor Plan You are an architect and you have just been appointed to build a new swimming hall. The organisation behind these plans has acquired funding for a swimming pool and surrounding building as large as they want, but unfortunately they could not find anyone wi www.acmicpc.net 영어로 된 문제지만 쫄지마세요. n이 주어졌을때 $$ n = m^2-k^2 $$ 위 수식을 만족하는 m과 k를 구하면 됩니..
알고리즘
www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 이번에는 이 문제를 풀어볼게요. 세그먼트 트리를 이용해서 최솟값과 최댓값을 구하는 문제입니다. 이론파트에서 너무 누적합 얘기만 해서 찔렸거든요 헣헣 저번에 작성해뒀던 틀에서 조금의 수정으로 풀어보겠습니다. + 연산 대신에 min 연산과 max 연산으로 고치면 되겠네요. 그러면 짜잔~ import math import sys def input(): return sys.stdi..
세그먼트 트리에 대한 글은 이미 많습니다. 심지어 다들 구체적으로 설명해주고 계십니다. 그런데 세그먼트 트리를 단지 구간합 트리라고 알고 계시는 분들이 생각보다 많이 계신 이유로 오해를 정정하고자 포스팅해보겠습니다. 세그먼트 트리가 없다면? 세그먼트 트리(구간 트리)는 주어진 쿼리에 대해서 빠르게 응답하기 위한 자료구조입니다. 배열 A가 주어져있고 A의 start~end 구간까지의 합을 구하려고 합니다. for문으로 answer+=A[i]를 돌리면 되겠죠. 그런데 만약 이 구간내 값이 변동이 된다면 어떨까요?? 총 M번 반복한다고 가정했을때, 수정 연산(O(1))+ 합산 연산 = O(NM)의 시간복잡도가 발생합니다. 세그먼트 트리 도입 여기에 세그먼트 트리를 사용한다면 어떻게 변할까요?? 수정 연산 = ..
programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 2021년 상반기 웹 백엔드 개발 데브 매칭에 출제된 문제입니다. 그때도 푼 기억이 있는 문제인데, 다시 풀려니까 코드를 더럽게 짰다만 기억나고 디테일한 부분은 기억이 안나서 다시 풀어봤습니다. 문제 요약 lottos는 내가 보유한 로또 번호 win_nums는 당첨 로또 번호입니다. lottos 배열의 0은 지워져서 알 수 없는 ..
programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 오늘의 문제입니다. 수식 문자열이 주어지면 (+,-,*)연산의 우선 순위를 능력껏 수정해서 최대값을 계산하라는 문제입니다. 문제 접근 저 같은 경우에는 일단 "100+200"이 있으면 100,+,200 씩 나누도록 분리했습니다. test = expression.replace('-',' - ').replace('+',' + ').replace('*',' * ').split()..
ps 거의 한 달만인가요 허허 토요일에 코딩테스트가 있어서 급하게 벼락치기로 준비해봅니다. 합격하면 좋고 합격을 못하더라도 예전보다만 제발 잘 봤으면 좋겠습니다. 어쨋든 오늘 풀 문제는 2021년 카카오 공채 코딩테스트 1번 문제였던 신규 아이디 추천 문제입니다. programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 접근 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳..
이진 트리 계층 구조인 트리의 자식이 left, right 둘로 이루어진 형태를 이진 트리라고 합니다. 이진 트리를 구성하고 dfs와 bfs로 탐색하는 예제를 작성하는 것이 이 포스팅의 목표입니다. 그림에서 초록 원들을 각각 노드라고 부릅니다. 각 노드들이 가지를 뻗듯이 연결되어 있으니(같은 이유로 트리라는 이름이 붙여졌습니다.) Node의 값과 연결된 노드들의 정보가 필요하겠죠. 즉 Node 클래스에는 다음과 같은 필드가 필요합니다. public class Node{ int value; Node left; Node right; ... } 생성자는 직접 만들어보세요. DFS DFS는 깊이 우선 탐색이라고 부릅니다. 트리에서의 깊이는 맨 위에 있는 노드(루트 노드)로 부터 특정 노드까지의 길이를 깊이라고 ..
www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 구현 문제로 특별한 알고리즘 기법에 대한 사전 지식 없이 풀 수 있는 문제입니다. 문제 설명란 외의 입력란에 있는 조건들도 보면서 풀어주시면 됩니다. 소스 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) k = int(input()) dx = [0,1,0,-1] dy = [1,0,-1,0] board = [[0..
www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 그래프 이론을 방금 배운 사람들도 바로 적용해볼 수 있는 문제입니다. 굳이 따지자면 그래프를 인접 리스트 형태로 만든 다음에 DFS로 탐색했습니다. 인접 리스트를 구현한 방법만 설명드릴게요. graph[1-1]에는 2랑 5가 들어갑니다. 즉 graph[n-1]에는 n과 연결된 노드를 넣어줍니다. 이미 방문한 노드는 가지 않도록 visited 배열도 관리해줍니다. 최종적으로 방문한 노드들은 visited에 체크가 되어..
문제 링크 www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 문제 요약 두 에너지 드링크 a, b가 있고, 양이 각각 Xa, Xb라 할 때, 다음 둘 중 하나의 선택을 할 수 있다. a의 양을 Xa + (Xb / 2)로 만들고, b를 버리기 b의 양을 Xb + (Xa / 2)로 만들고, a를 버리기 위의 방식으로 에너지 드링크를 합쳐서 그 양을 최대로 하자. 접근 그리디 문제이고 접근법도 굉장히 쉽습니다. 그냥 가장 양이 많은 드링크에 그다음 양이 많은 드링크..
