# boj

wowns226

📕 문제 📌 링크 📗 접근 방식 각 타일은 Point 클래스로 표현되며, Board 클래스에 배치(클래스화 하여 풀려고 노력함) DFS (깊이 우선 탐색)를 활용하여 모든 가능한 움직임 조합을 시도 각 움직임 조합마다 보드를 업데이트하고 최대 블록 값을 계산 모든 움직임 조합을 시도하고 난 후 최대 블록 값을 출력 >* 중요한 접근 방식 * >한 방향을 결정 (상하좌우 상관없음, 본인 상으로 결정) >그렇다면 선택한 방향을 제외한 방향을 어떻게 구현할 것인가? > >만약 아래로 가고 싶다면 전체 매트릭스(Board)를 180도 회전하여 위로 이동한다면 결국 아

dong98

알고리즘 분류 브루트포스 🔗 문제 📎 문제 출처 https://www.acmicpc.net/problem/1436 🔗 코드 해결 방법을 고민하기 전에 문제에 대한 이해를 하는데 시간이 오래 걸렸었다. 666,1666,2666,3666,,,,이런 식으로 흘러가는 것은 이해했다. 그렇다면 문제에서 등장한 예시인 66666은 66번째 영화 제목이 아닌가 한참을 고민했다. 즉, 5666 다음은 6666이라고 생각했던 것이다. 하지만 5666과 6666사이에는 666을 포함하고 있

joajy

1. Link https://www.acmicpc.net/problem/11758 2. 풀이 과정 > 1. 솔직히 몰라서 진짜 하드코딩했는데, 그래도 틀리길래 그냥 외적 상기할 겸 검색했습니다. 그랬더니 Counter Clock Wise라는 알고리즘이 있더군요. CCW는 직역하면 시계 반대 방향을 의미합니다. Clock Wise가 시계 방향을 뜻하니 시계 방향 및 반시계 방향에 대한 문제라고 유추할 수 있습니다. 행렬을 배웠다는 가정 하에 풀이할 수 있다고 생각합니다. 만약 행렬을 배운 적이 없다면 한 번 인터넷에서 찾아보는 걸 추천합니다.(기하 및 선형대수학 등 다양한 분야에서 많이 사용합니다.) > 1. 세 점을 사용하여 두 벡터를 만들어줍니다. (x1을 시점으로 해야 하므로 x1,x2와 x1,x3을 연산하면 됩니다. 이렇게 만들어진 두 벡터를 행렬화하여 외적한 값을 계산합니다. 각 벡터의 내적값을 (V1x, V1y), (V2x,V2y)라

ssook1222

📍 문제 > "여기도 할인, 저기도 할인! 곧 할인을 해 드릴게요, 따란딴딴🔔" 이 노래는 최근 스톤카 슈퍼마켓의 스피커에서 재생되는 즐거운 노래입니다! 그리고 지금 스톤카 슈퍼마켓에서 하고 있는 할인에 대한 규칙은 다음과 같습니다 : 각 고객은 상점에 일정 금액을 남깁니다. 하루가 끝날 때, 상점 경영진은 임의의 번호 k를 선택합니다. 그런 다음, 그들은 그 날 상점에서 가장 많은 금액을 쓴 k번째 큰 금액을 찾아서 그 고객에게 무료로 견과류가 들어간 초콜릿을 보내줍니다. (물론, 그 초콜릿은 "스톤카 식료품점에서 만들어졌습니다."라고 적혀 있습니다.) 당신은 슈퍼마켓에서 고객이 사용한 금액이 중복될 때에는 어떤 방식으로 초콜릿을 받을 행운의 주인을 선택할지 궁금할 것입니다. 하지만, 우리는 그냥 질문을 하는 것이 목적입니다. 따라서 당신은 단순히 중복을 고려하지 않고 특정 날짜에 사용된 금액 중에서 k번째로 큰 금액을 찾기만 하면 됩니다!

jihong5524

문제 링크 난이도 : Silver 4 (solved.ac 2023.09.29. 기준) 문제 > 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 알고리즘 > 수학 브루트포스 풀이 1부터 n까지의 한수의 개수를 구해야 하기 때문에 반복문으로 1부터 n까지의 모든 수를 한수인지 판별하여 개수를 세는 count 변수에 +1을 하는 방법으로 한수의 개수를 구할 수 있다. 자리수가 2개까지의 양의 정수(1~99)들은 모두 각 자리수가 등차수열을 이루는 한수이기 때문에 그냥 count 변수에 +1을 한다. 하지만 100부터 N까지의 수들은 한수인지 판별하여야 한다. 각 자리 수의 차이를 구해야 하기 때

doxxx93

문제 링크 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

aoleejohn

문제를 완벽히 이해하는데 좀 애를 먹은 문제이다. 주의할 점은 비활성화 바이러스 또한 바이러스라는 점이다. 때문에 실험실이 비활성화 활성화 여부에 상관없이 빈공간만 아니면 된다는 점을 유의해야한다.

doxxx93

무지성 알고리즘 챌린지 카톡방에 들어와서 문제를 푸는 중이다. 문제 링크 문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 횟수만큼 답

jihong5524

문제 링크 난이도 : Silver 5 (solved.ac 2023.09.27. 기준) 문제 > 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로. 단, 중복된 단어는 하나만 남기고 제거해야 한다. 알고리즘 > 정렬 풀이 입력받은 문자열을 정렬하기 위해 C++ 표준라이브러리인 에 있는 sort 함수를 사용한다. 하지만 단순히 사전순으로 정렬하는 것이 아닌, 조건에 따라 정렬해야 하기 때문에 compare을 sort의 사용자 지정 함수로 만들어 정렬한다. 그리고 중복되는 단어는 하나만 남기고 제거해야 하기 때문에 첫번째 단어는 출력하고, 두번째 단어부터는 중복되는 단어들을 출력하지 않는다. 코드

jitae-moon

My Solution 출처: https://www.acmicpc.net/

ssook1222

📍 문제 당신은 인기 있는 주간 텔레비전 토크 쇼의 호스트로서, 다가올 다이어트 에피소드의 세부 사항에 대해 작업 중입니다. 게스트로는 최근 핫한 다이어트 프로그램인 "다이어트 하고 싶나요?"를 자체 기획한 Dr. Kevorkian을 초대할 예정입니다. 이 프로그램은 매일 체중을 1 파운드 감소시키는 것을 보장하고 있습니다! 당신은 다이어트를 진행 중인 여러 다이어터를 쇼에 초대하기로 예정되어 있는데, 이 참가자들 모두가 Dr. Kevorkian의 프로그램에 참여하고 있습니다. 당신은 쇼를 더 가시적으로 만들기 위해 쇼에 출연하는 다이어터들을 그들의 다이어트 시작 체중을 내림차 순 기준으로 소개하려고 합니다. 문제는 그들이 작성한 양식에서는 아래와 같은 정보만을 담고있다는 것입니다: 이름, 다이어트 진행 일수, 다이어트 시작 체중. 당신은 오늘 밤 촬영 시간까지 이 정보들을 계산해야 합니다. 간만에 쓰지 않았던 수학 기술을 활용해야 하겠군요! 입력

vkdldjvkdnj

BOJ 3197 - 백조의 호수 링크 (2023.09.27 기준 P5) 문제 >두 마리의 백조가 호수에서 살고 있으며, 호수는 물이나 얼음인 칸으로 이루어져 있다. 매일 물은 인접한 얼음인 칸을 녹인다. 백조가 만나기 위한 최소 일수 출력 알고리즘 >BFS & 분리 집합 풀이 >백조가 속해 있는 물 공간에서는 자유롭게 움직일 수 있다. 두 백조가 만나기 위해선 결국, 두 백조가 속해 있는 물 공간이 만나야 한다는 뜻이 된다. > 물은 인접한 빙판을 녹인다. 녹이는 시간은 하루. 이는 BFS를 사용하면 된다. > 하나의 물 공간은 곧, 하나의 집합이다. 분리 집합을 사용하여 물인 공간은 하나의 집합으로 만들고, BFS를 돌리면서 물과 인접한 빙판은 물과 union하면 된다. > 그런데, 녹이면서 union하고 두 백조의 집합이 같은 집합인지 판별하게 되면

gawgjiug

1159번 : 농구 경기 간단하게 생각하면 문자열의 첫 글자가 5번이상 반복되는 알파벳을 찾는 것 알파벳을 저장할 인덱스 생성 맨 앞자리만 char 자료형에 입력 받아서 해당하는 인덱스를 증가 시킴 배열 alpha의 인덱스를 돌면서 인덱스의 값이 5이상인 경우 해당 알파벳을 출력

3670lsh

📌접근 원소 개수를 파악하기 위해 dict() 필요 입력문자열 길이 짝수 : 개수가 홀수인 원소 x 홀수 : 개수가 홀수인 원소 1개 문자열 길이 짝수 : 앞뒤로 반전 홀수 : 가운데 홀수인 문자 추가후 반전 📌코드 조건 분기 mid_char str 길이가 짝수 일때는 odd = 0 ,midchar = '' 이어야 하고, str 길이가 홀수 일때는 odd = 1 , midchar= 'n'이어야 한다. 반전 파이썬에서 슬라이싱을 이용하여 [ end : start : -1 ] 처럼 쓰면 start+1 ~ end 를 반전할 수 있다. dictionary 정렬\ Key를 기준으로 정렬 (오름차순) Key를 기준으로 정렬 (내림차순) item[0] = key , item[1] = value 를 의미한다. value를 기준을오 정렬 (오름차순 )

aoleejohn

행렬을 잘 다뤄야 하는 문제이다. 주의해야 할 점이 좀 몇가지가 있는데 행과 열을 대칭으로 바꿔서 정렬을 해준다음 다시 대칭으로 변환하여 열에 대한 정렬을 해줄 떄 복사의 범위가 행열중 큰 수까지 복사되어야 한다는 점이다. 또한 문제에서 100 초가 넘어가거나 행렬의 길이가 100이 넘어갈 때의 처리를 문제설명에서 명시하기에 문제를 주의깊게 읽어야한다.

doxxx93

링크 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 풀이 루트가 없는 트리가 있고 특정 노드를 루트로 정한다는 건, 문제만 읽어서는 머리속에서 잘 그려지지 않을 수 있다. 아래와 같이 예제 1을 루트를 바꿔서 여러가지 트리를 만들어보자 ![](https://velog.velcdn.com/images/doxxx93/post/e3150f05-48dc-4550-a50

ssook1222

📍 문제 정상적인 팰린드롬은 숫자 또는 문자의 문자열로, 앞에서부터 뒤로 읽어도 뒤에서부터 앞으로 읽어도 동일한 문자열입니다. 예를 들어, "ABCDEDCBA" 문자열은 팰린드롬입니다. 왜냐하면 이 문자열은 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 모두 동일합니다. 거울 모양 문자열은 문자열의 각 요소가 그 역(reverse)으로 바뀌었을 때 (만약 역이 있는 경우) 문자열을 뒤에서부터 읽을 때 결과가 원래 문자열과 동일한 문자열입니다. 예를 들어, "3AIAE" 문자열은 거울 모양 문자열입니다. 왜냐하면 "A"와 "I"는 자신의 역(reverse)이며, "3"과 "E"는 서로의 역(reverse)입니다. 거울 팰린드롬은 정상적인 팰린드롬의 조건과 거울 모양 문자열의 조건을 모두 충족하는 문자열입니다. "ATOYOTA" 문자열은 거울 팰린드롬입니다. 왜냐하면 이 문자열을 뒤에서부터 읽으면 원본과 동일하며, 각 문자가 그 역으로 대체되고 결과를 뒤

vkdldjvkdnj

BOJ 16507 - 어두운 건 무서워 링크 (2023.09.26 기준 S1) 문제 >R×C 크기의 사진이 있으며 각 픽셀마다의 밝기가 주어진다. Q개의 쿼리마다 r1, c1, r2, c2가 주어진다. 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균 출력 알고리즘 >2차원 누적 합 풀이 > > (r1, c1) ~ (r2, c2) 까지의 구간 합을 구해야 한다. 그러면 일단 연노랑 영역 prefixsumr2에서 노랑 영역 prefixsumr2과 초록 영역 prefix_sumr1-1을 빼보자. 그러면 (0, 0) ~ (r1-1, c1-1)

dakyommii

🏅 Gold 5 ✏️ 최종 솔루션 ⭐️ 구현 seq: 자리 배치하는 순서 기록 board: 해당 자리에 앉는 숫자 기록 love: love현재 숫자=true 형식으로 선호 관계 저장 node: {현재 자리 인접 선호 관계 개수, 현재 자리 인접 빈 자리 개수 , 행, 열} 자리 배치하는 순서와 선호 관계 입력 받기 자리 배치하기 1) 현재 인덱스가 앉을 수 있는 모든 자리를 돌면서 각 자리의 인접 자리 선호관계 개수, 빈 자리 개수 count 해서 node 로 묶어서 우선순위 큐에 저장 2) 모든 자리 탐색 후에 우선순위 top node 의 행, 열을 현재 인덱스의 자리로 확정하여 board 에 저장 각 자리의 인접 자리 중 선호 관계 개수 count 해서 answer 갱신 📌 self feedback ❗️ vector 정렬 위한 cmp 함수와 큐 정렬 위한 cmp 함수는 방

aoleejohn

문제만 보면 크게 어렵지 않지만 상어가 왔다 갔다 하는 부분을 구현하는 데 시간을 좀 쓴 문제이다. 수식으로 만들어서 풀려하였지만 단순히 직접 이동하는 방법을 사용하였고, 이때 일정 거리 이상이면 반복되는 구간이 존재하므로 최적화를 해줄 수 있다.