PS

Problem Solving (알고리즘, 자료구조 문제풀이)

PS

[PS] BOJ 15351 / 인생 점수

문제 링크: https://www.acmicpc.net/problem/15351 Thumbnail: Photo by Joshua Earle (Unsplash) 풀이 A = 1, B = 2, ..., Z = 26의 꼴로 계산하려면, 아스키 코드로 변환해 현재 알파벳이 몇번째인지 계산하면 됩니다. for c in content: if c == " ": continue score += ord(c) - ord("A") + 1 전체

PS

[PS] BOJ 16567 / 바이너리 왕국

문제 링크: https://www.acmicpc.net/problem/16567 Thumbnail: Photo by Gonzalo Facello (Unsplash) 생각 외의 부분에서 실수했던 문제였습니다 :P 풀이 알고리즘 구상 단순히 1 i꼴의 명령을 받으면 배열의 그 원소만 1로 바꾸고, 출력할 때 마다 배열을 순회하게 되면 \(O(NM)\) 꼴이 되며, 시간 초과가 발생합니다. 따라서, 1 i의 명령을

PS

[PS] BOJ 3224 / grupe

문제 링크: https://www.acmicpc.net/problem/3224 Thumbnail: Photo by Annie Williams (Unsplash) 며칠 고심하면서 이해해봤는데, 그만큼 재밌는 문제였습니다. 풀이 스택 (Stack) 기본적인 풀이는 스택을 이용합니다. 고정 크기의 스택을 먼저 구현해줍시다. class Stack: """Fixed size stack implementation.""" def __init__(self, max_size, default_

PS

[PS] BOJ 19844 / 단어 개수 세기

문제 링크: https://www.acmicpc.net/problem/19844 Thumbnail: Photo by Sven Brandsma (Unsplash) 문제 조건대로 구현하는게 간단할 거라 생각했지만, 생각보다 디테일에서 고전했습니다... 풀이 문제에서 이야기한 단어를 구분하는 조건은 다음과 같습니다: * 기본적으로는 띄어쓰기나 -(하이픈) 단위로 단어를 구분한다. * 앞 단어가 ce, je, ne, me, te, se, le, la, de, que

PS

[PS] BOJ 16953 / A → B

문제 링크: https://www.acmicpc.net/problem/16953 Thumbnail: Photo by Suhyeon Choi (Unsplash) 놀랍게도 그래프 탐색으로 풀 수 있습니다. 풀이 처음 봤을때는 어떻게 풀어야 하는지 고민했는데, 태그에 그래프 탐색을 보자마자 방법이 떠올랐습니다. 엥? 이게 그래프 탐색이라고? BFS(Breadth-First Search, 너비 우선 탐색)을 생각해봅시다. 큐를 기반으로, 현재 노드의 처리

알고리즘 / 백트래킹

[PS] BOJ 15652 / N과 M (4)

문제 링크: https://www.acmicpc.net/problem/15652 Thumbnail: Photo by Iqbal Pohan (Unsplash) 백트래킹 문제 시리즈, N과 M의 4번째 문제입니다. 풀이 백트래킹으로 풀이할 수 있습니다. 백트래킹이란, 모든 분기를 다 탐색하되 유망하지 않은 분기는 탐색에서 제외하는 방법입니다. 여기서 유망하지 않다를 판단하는 기준은 문제 조건을 기반으로 합니다. 유망하지 않다? 문제에서 요구하는

PS

[PS] BOJ 16928 / 뱀과 사다리 게임

문제 링크: https://www.acmicpc.net/problem/16928 Thumbnail: Photo by VD Photography (Unsplash) 다들 한번쯤은 들어보셨을 법한 클래식한 보드게임 입니다! 풀이 DFS로 풀이할 수 있습니다. 풀이에 앞서, 먼저 뱀과 사다리 게임의 규칙을 간단하게 정리해 봅시다. * 시작점은 1, 도착점은 100인 100칸짜리 보드판에서 게임을 진행한다. * 1~6의 값을 가지는 정육면체 주사위

PS

[PS] BOJ 6064 / 카잉 달력

문제 링크: https://www.acmicpc.net/problem/6064 Thumbnail: Photo by Seiji Seiji (Unsplash) 언젠가 시간을 내서 정수론을 공부해야겠습니다... 풀이 브루트포스 풀이로 접근했습니다. 기본적인 아이디어는 아래와 같습니다. # <x:y> = k일때, 어떻게 k를 찾아야 할까? # 1. 단순 계산 _x, _y = 1, 1 for i in range(1, lcm(M,

PS

[PS] BOJ 1241 / 머리 톡톡

문제 링크: https://www.acmicpc.net/problem/1241 Thumbnail: Photo by Margarida CSilva (Unsplash) 오늘도 등장한 약수 찾기 문제입니다. 풀이 풀이를 간단하게 정리하면, Counter + 약수 찾기 로 생각할 수 있습니다. '자신이 쓴 숫자가 다른 사람이 쓴 숫자의 배수이면' 이란 표현은 결국 자신의 약수를 쓴 사람이 몇명 있는지 찾는

PS

[PS] BOJ 10835 / 카드게임

문제 링크: https://www.acmicpc.net/problem/10835 Thumbnail: Photo by piotr sawejko (Unsplash) 항상 느끼는 거지만 DP는 너무 어렵습니다... 좀 더 풀다보면 직관이 생기지 않을까요? 풀이 bottom-up 접근으로 풀었습니다. DP 배열의 구성 DP[왼쪽 카드 더미의 남은 장 수][오른쪽 카드 더미의 남은 장 수] 꼴로 구성하고, DP 배열의

PS

[PS] BOJ 14232 / 보석 도둑

문제 링크: https://www.acmicpc.net/problem/14232 Thumbnail: Photo by Joshua Fuller (Unsplash) 풀이 '훔친 보석의 무게의 곱이 \(K\)와 딱 같게끔 하는 최대 보석의 개수를 구하라' 라는 문제는 결국 \(K\)를 소인수분해 해서 출력하라는 것과 같습니다. 전체 코드 from math import ceil, sqrt input = open(0)

PS

[PS] BOJ 29714 / 브실이의 구슬 아이스크림

문제 링크: https://www.acmicpc.net/problem/29714 Thumbnail: Photo by Elza Kurbanova (Unsplash) 여러분은 어떤 아이스크림을 좋아하시나요? 저는 메로나를 제일 좋아합니다 😄 풀이 태그에 해시를 이용한 집합과 맵이 있듯이, Map 자료구조를 이용하면 간단히 풀이할 수 있습니다. 기본적인 원리는 "각 아이스크림 구슬이 몇 개 있는지 파악하자" 입니다. 저는 파이썬의

PS

[PS] BOJ 24468 / 충돌의 수

문제 링크: https://www.acmicpc.net/problem/24468 Thumbnail: Photo by Mollie Sivaram (Unsplash) 구현 및 시뮬레이션 문제입니다. 풀이 문제에서 제시된 그대로 구현하면 됩니다. T초동안 (T초에 발생한 충돌도 포함) 공의 이동을 시뮬레이션 합니다 : * 각 공을 이동 방향대로 1칸씩 이동시킵니다. * 발생하는 충돌을 처리합니다: * 만약 벽 (왼쪽: 위치 0, 오른쪽: 위치 \(L\

PS

[PS] BOJ 26596 / 황금 칵테일

문제 링크: https://www.acmicpc.net/problem/26596 Thumbnail: Photo by Nuff . (Unsplash) 황금 칵테일 한잔, 온더락으로. 풀이 \(M\)회에 걸쳐 재료들을 투입하게 되는데, 이중에는 같은 재료가 여러 번 들어갈 수도 있습니다. 따라서, 각 재료마다 투입된 총량을 계산할 필요가 있는데, 저는 Map 자료구조의 일종인 딕셔너리(dict)를 사용해 구현했습니다. 재료별

PS

[PS] BOJ 25631 / 마트료시카 합치기

문제 링크: https://www.acmicpc.net/problem/25631 Thumbnail: Photo by Didssph (Unsplash) 마트료시카 인형 쌓기~ 풀이 크기가 서로 다른 마트료시카 인형들은 결과적으로 가장 큰 크기의 1개 인형으로 합쳐질 수 있다. 합쳐지지 못하고 인형이 하나 더 남게 되는 경우는 결국 같은 크기의 인형이 중복될 경우이므로, 인형을 크기를 기준으로 개수를 세어

PS

[PS] BOJ 21965 / 드높은 남산 위에 우뚝 선

문제 링크: https://www.acmicpc.net/problem/21965 Thumbnail: Photo by Ales Krivec (Unsplash) 마냥 간단하게 생각했었는데, 생각보다 실수하기 쉬운 문제였습니다. 풀이 문제에서 어떤 수열을 산이라고 부르기 위한 조건은 간단히 요약해보면, "수열의 원소들은 임의의 지점 전까지 계속 증가하다가 이후로는 계속 감소해야 한다." 입니다. 구현에 필요한 조건들을 정리해 보면

PS

[PS] BOJ 25710 / 점수 계산

문제 링크: https://www.acmicpc.net/problem/25710 Thumbnail: Photo by angg Y (Unsplash) 이 문제 덕분에 비둘기집의 원리를 이해했습니다..! 풀이 문제 입력으로 주어지는 배열 a는 최대 100,000개의 원소를 가집니다. 이 배열을 그대로 가지고 점수 계산을 하게 되면, 최대 \((100,000)^2)\번 반복하게 되며 당연하게도 제한 시간을 초과합니다.

PS

[PS] BOJ 24445 / 알고리즘 수업 - 너비 우선 탐색 2

문제 링크: https://www.acmicpc.net/problem/24445 Thumbnail: Photo by Aaron Burden (Unsplash) 그래프를 탐색하는 2가지 기초적인 방법인 DFS와 BFS, 그중 BFS(너비 우선 탐색) 에 대한 문제입니다. 풀이 문제에서도 의사 코드로 주었듯이, BFS(너비 우선 탐색)은 자식 노드보다 형제 노드를 먼저 순회하는 방식입니다. 큐를 활용하면 간단히 구현할

PS

[자료구조] 배열과 연결 리스트

Thumbnail: Photo by Frank van Hulst (Unsplash) 다른 추상 자료형(Abstract Data Type)을 구현할 때 기반이 되는 기초적인 선형 자료구조인 배열과 연결 리스트에 관해 간단히 정리해봤습니다. 배열 배열은 동일한 자료형의 원소들을 연속적인 메모리 공간에 저장하는 선형 자료 구조입니다. 배열의 크기는 고정되어 있어서, 선언 시에 크기를 지정해야 합니다. (어떤 자료형을

PS

[PS] BOJ 20301 / 반전 요세푸스

문제 링크: https://www.acmicpc.net/problem/20301 Thumbnail: Photo by Luiz Felipe S. C. (Unsplash) queue 계열 자료구조 연습에 항상 보이는 문제 유형입니다. 풀이 python의 경우, 내장 모듈 collections에 deque 자료구조가 사전에 구현되어 있습니다. (물론 list를 바로 사용해도 무방합니다) 이번 풀이는 내장 deque를 사용해 진행했습니다. 문제에서 \(M\)번째 사람마다

PS

[PS] BOJ 4096 / 팰린드로미터

문제 링크: https://www.acmicpc.net/problem/4096 Thumbnail: Photo by Spencer Backman (Unsplash) 생각만큼 간단하지 않아서 몇차례 고전했습니다... 생각한 과정 문자열을 \(S\), 이 문자열의 길이를 \(L\)이라고 합시다. 먼저 주어진 숫자가 팰린드로미터가 맞는지 판단하기 위해 1차례 문자열의 절반 (\(L\))만큼 반복하며 양 끝을 비교합니다. 이후, 팰린드로미터가 아니라면 다시 문자열의

PS

[PS] BOJ 7774 / 콘센트

문제 링크: https://www.acmicpc.net/problem/7774 Thumbnail: Photo by Ryan Quintal (Unsplash) 콘센트 규격이 두가지가 섞여 있는 동네라니... 왜 하나로 통일하지 않은 걸까요? 생각한 과정 처음에 A 단자 1개만 있고, A->B 멀티탭과 B->A 멀티탭을 받아 최대한 많은 A 단자를 만들어야 합니다. A 단자를 최대한

PS

[PS] BOJ 19939 / 박 터뜨리기

문제 링크: https://www.acmicpc.net/problem/19939 Thumbnail: Photo by Michelle Garres (Unsplash) 문제를 처음 봤을 때에는 풀이가 바로 떠오르지 않았지만, 차근차근 생각해보니 간단한 형태로 풀이를 정리해낼 수 있었습니다! 생각한 과정 이해에 도움이 되지 않을까 하여, 제가 생각한 과정을 남겨두겠습니다. \(K\)개의 바구니에 \(N\)개의 박을 나눠 담는데, 각

PS

[PS] BOJ 1244 / 스위치 켜고 끄기

문제 링크: https://www.acmicpc.net/problem/1244 Thumbnail: Photo by Vincent Battault (Unsplash) 아이디어는 굉장히 간단히 떠올랐는데, 이상한데서 삽질하느라 몇차례 틀렸습니다... 풀이 먼저, 스위치는 \(0\)과 \(1\) 두 가지를 가질 수 있습니다. 그냥 코드에 바로 써도 되지만, 가독성을 위해 스위치의 상태를 변경하는 함수를 별도로 분리했습니다. def turn_switch(x)

PS

[PS] BOJ 23969 / 알고리즘 수업 - 버블 정렬 2

문제 링크: https://www.acmicpc.net/problem/23969 Thumbnail: Photo by Soop Kim / Unsplash 버블 정렬 알고리즘을 이해한다면 쉽게 풀이할 수 있습니다. 풀이 버블 정렬 알고리즘의 의사 코드는 문제에서 보여주니, 이를 적절히 구현하면 됩니다. 이후, 배열 내 두 수의 교환이 일어날 때 마다 교환 횟수를 세어 K에 도달할 때 버블