Minjun Kim

PS

[PS] BOJ 33870 / 빗질의 중요성

문제 링크: https://www.acmicpc.net/problem/33870 Thumbnail: Photo by charlesdeluvio (Unsplash) 애완견의 빗질은 항상 잊지 말고 해줍시다~ 풀이 구현 별다른 어려움 없이, 문제 조건을 그대로 구현하면 되는 문제였습니다. 다만, 답을 맞히기까지 여러 차례 시행착오를 겪었습니다.. 털 상태 관리 1일차부터 \(M\)일차 까지 강아지 1마리씩 골라 빗고, 만약 이전에

Life

[월말정산] 25년 5월의 이야기

Thumbnail: Photo by Milan De Clercq (Unsplash) 벌써 5월도 다 갔습니다! 이 글을 쓰는 지금, 1시간 뒤면 6월이 오고 병장이 됩니다. 군생활 다했네!(아님) 5월은 4월에 시작한 일들을 꾸준히 하는 삶을 살았습니다. 뭔가 새로운 걸 도전해보고 싶은 생각도 있긴 한데, 당장은 꾸준히 하는 습관을 만들고 지켜내는데 더 열중했던 것 같네요.

PS

[PS] BOJ 15654 / N과 M (5)

문제 링크: https://www.acmicpc.net/problem/15654 Thumbnail: Photo by Brett Jordan (Unsplash) N과 M은 유명한 백트래킹 시리즈입니다. 풀이 백트래킹 (DFS) 백트래킹도 결국은 DFS입니다. 다만, 분기에 진입하기 전에 조건에 맞는지 아닌지를 미리 판단해, 적합하지 않은 분기라면 진입하지 않고 건너뛴다는 차이점이 있습니다. 이번 문제에서는 \(N\)과 \(M\), 그리고 \(N\)개의

PS

[PS] BOJ 12851 / 숨바꼭질 2

문제 링크: https://www.acmicpc.net/problem/12851 Thumbnail: Photo by loong xu (Unsplash) 어느덧 이런 유형의 문제는 BFS로 푸는게 보이기 시작했습니다. 풀이 BFS BFS로 전체 구간을 탐색하면서, 다음 탐색할 노드로 [\(X - 1\), \(X + 1\), \(2 \times X\)]를 넣어주면 됩니다. 단, 다음에 탐색할 지점이 전체 구간 (\(0 \le

PS

[PS] BOJ 1235 / 학생 번호

문제 링크: https://www.acmicpc.net/problem/1235 Thumbnail: Photo by CX Insight (Unsplash) 풀이 '집합'을 이용한 풀이 집합이란, 동일한 원소가 중복되지 않는 컨테이너 자료구조입니다. (다른 원소를 저장할 수 있는 자료구조) 집합을 구현하는 방법은 이 글에서 다루진 않겠습니다. 이번 풀이에서는 파이썬에 내장된 set를 사용했습니다. 알고리즘은 다음과 같습니다.

PS

[PS] BOJ 19592 / 장난감 경주

문제 링크: https://www.acmicpc.net/problem/19592 Thumbnail: Photo by Jefferson Sees (Unsplash) 최대값 최댓값 어느 쪽이 맞는 표기인지 헷갈려서 찾아봤는데, 최댓값이 맞다고 합니다 ㅎㅎ 풀이 이게 왜 이분 탐색? ~ 한 조건을 만족하는 최대/최솟값을 찾는 형태의 문제들을 최적화 문제 라고 부릅니다. 그러나, 최적화 문제를 왜 이분 탐색으로 풀

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)을 구현할 때 기반이 되는 기초적인 선형 자료구조인 배열과 연결 리스트에 관해 간단히 정리해봤습니다. 배열 배열은 동일한 자료형의 원소들을 연속적인 메모리 공간에 저장하는 선형 자료 구조입니다. 배열의 크기는 고정되어 있어서, 선언 시에 크기를 지정해야 합니다. (어떤 자료형을