오구리의 DevLog

▶1963 - 소수 경로 ▶문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민 중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.” “흠... 역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 ..

드디어 solved.ac에서 스트릭 100일을 달성했다. 작년(2022년) 11월 말에 알고리즘 1일 1문제를 시작했다. 그리고, 오늘(23.03.05) 드디어 100일을 달성했다. 꾸준히 하는 게 너무 귀찮기도 하고, 까먹을 뻔할 때도 있었다. 중간중간 브론즈 5, 브론즈 4 문제를 풀면서 스트릭을 채우는 날 도 있었다. 그래도 100일을 달성하고 나니까 지난 3개월 동안 알고리즘을 게을리하지 않았다는 생각에 뿌듯하다. 스트릭 100일을 채우는 동안 많은 일들이 있었다. 카카오와 야놀자에서 인턴을 지원해 코테를 보기도 했다. 꾸준히 알고리즘을 풀어와서 코테를 보기 위해 급하게 공부하지 않아서 좋았다. 물론 결과는 좋지 못했지만, 시험을 보는데 조급하지 않고 편안하게 시험 볼 수 있었다. 카카오 인턴은 ..

▶2573 - 빙산 ▶문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일 년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일 년 후에 그림 2와 같이 변형된다. 그림 3은 그림..

▶미로 탈출 명령어 - 2023 KAKAO BLIND RECRUITMENT (level 3) ▶문제 n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다. 단, 미로를 탈출하는 조건이 세 가지 있습니다. 격자의 바깥으로는 나갈 수 없습니다. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c) 격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다. 이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다. l: 왼쪽으로 한 칸 이동 r: 오른쪽으로 한 칸 이동 u: 위쪽으로 한 칸 이동 d: 아래쪽..

▶8111 - 0과 1 ▶문제 폴란드 왕자 구사과는 다음과 같은 수를 좋아한다. 0과 1로만 이루어져 있어야 한다. 1이 적어도 하나 있어야 한다. 수의 길이가 100 이하이다. 수가 0으로 시작하지 않는다. 예를 들어, 101은 구사과가 좋아하는 수이다. 자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다. 둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다. ▶출력 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. ▶풀이 1과 0이 들어가는 모든 ..

▶2146 - 다리 만들기 ▶문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다. 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다..

▶1715 - 카드 정렬하기 ▶문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 ..

▶3055 - 탈출 ▶문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해 보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해 있는 비어있는 칸(적어도 한 변을 공유..

오늘(23일) 새벽 5시 경기를 끝으로 챔피언스리그 16강 1차전이 끝이 났다. 경기결과는 다음과 같다. ▶ EPL의 굴욕 - 1무 3패 EPL팀 4팀이 16강에 진출했다. 대진을 보면 다들 쉽지 않은 팀을 만났고, 비교적 쉬운 상대를 만난 맨시티까지. 모두 승리를 챙기지 못했다. 4팀의 결과는 1무 3패. 솔직히 말해서 첼시와 토트넘은 이기지 못할 거라고 생각했다. 리버풀 또한 이기지 못할 거라고 생각했지만, 전반에 2골을 넣었을 때만 해도 레알마드리드를 손쉽게 이기는 듯했다. 하지만 알리송 골키퍼가 실수를 하며 동점도 내주게 되었고, 결국 패배로 이어졌다. 첼시, 토트넘, 리버풀 세 팀은 쉽지 않은 상대를 만났기에 그럴듯한 경기 결과가 나왔다. 하지만 라이프치히를 상대한 맨시티는 1대 1 무승부를 기..

▶2636 - 치즈 ▶문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X 친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. 은 원래 치즈의 두 시간 후 모양을 나..

맨체스터 시티를 좋아하는 개인이 쓴 글입니다. 개인의 의견이기에, 다소 편향성을 보일 수도 있습니다. 그렇더라도, 최대한 정보 전달을 위해 글을 쓰도록 하겠습니다. 혹시나 잘못된 정보를 전달하고 있다면, 댓글로 알려주시면 감사하겠습니다. UEFA 챔피언스리그 16강이 시작했다. 16강 1차전 8경기 중 4경기가 끝났다. 리버풀 vs 레알 마드리드 나폴리 vs 아인트라흐트 맨시티 vs 라이프치히 인테르 vs 포르투 이렇게 1차전 4경기가 남아있다. 16강부터는 대진운도 따라야 결승까지 쉽게 갈 수 있을 것이다. 대진만 봤을 때는 맨시티, 인테르, 나폴리가 손쉽게 8강에 갈 것이라고 생각한다. 그럼 전문적인 업체에서는 우승 확률을 어떻게 생각할까? ▶ 맨시티, 바이에른 뮌헨 강력한 우승 후보 맨시티와 바이에..

▶17251 - 힘 겨루기 ▶문제 과거 격투가로 명성을 떨치던 힘스트롱 씨는 "힘 겨루기"라는 대회를 주최하여 전국에 홍보를 하였다. 모집 공고를 보고 전국 각지에서 많은 사람들이 모였는 데, 모집 공고에 '힘'이란 것에 대해 정의하지 않아 혼란이 생긴 것이다. 헬스장에서 3대 500치는 근육질 아저씨부터, 유명 RPG 게임의 힘(STR) 스탯이 높은 사람까지 여러 종류의 힘을 두고 모인 것이다. 힘스트롱 씨는 문득 "아는 것이 힘이다"라는 유명 격언이 떠올랐다. 예선전에서 상식 퀴즈를 통해 참가자들의 힘을 수치화하였고, 이 수치를 통해 본선 참가자를 선정하기로 하였다. 그렇게 총 N명의 참가자가 본선에 진출하였다. 하지만 예상과 달리, 본선은 홍팀과 청팀 두 팀으로 나누어 승부를 겨루는 팀전으로 진행되..

▶1240 - 노드사이의 거리 ▶문제 N(2≤N≤1,000) 개의 노드로 이루어진 트리가 주어지고 M(M≤1,000) 개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. ▶입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. ▶출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. ▶풀이 일단 bfs를 이용해서 원하는 노드 간 거리를 구해줬다. 첫 번째 for문에서는 graph를 만들었고, 두 번째 for문에서는 두 노드를 입력받았다. 두 노드의 값을 bfs로 보내서 x에서 시작해 y에 도착하면 return해주는 방..

2022년 4월에 티스토리를 시작하고, 6월이 되어서야 구글 애드센스를 알게 되었다. 그때는 이미 남들이 말하는 구글 애드센스 기준이 충분했었다. 신청하기 위해서 찾아보던 중 모든 사람들이 말하는 공통점이 있었다. 1. 포스팅 글자 수 기본적으로 포스팅의 글자수가 1000자 이상은 되어야 한다는 것이다. 구글에서도 광고를 해주기 위해서 포스팅의 질이 좋아야 한다. 그 기준을 글자수로 보고 있는 것 같다. 대충 1000자 이상이 된다면 양질의 정보를 담은 글이라고 판단하는 것 같다. 이미 나는 그 이상 글을 쓰고 있었다. 알고리즘 문제 풀이를 기준으로 글을 쓰고 있었고, 글자수가 적어도 1000자가 되었던 것 같다. 2. 독창적인 글 여기저기서 복사하고 붙여넣기한 글은 품질이 좋지 않기에 잘해주지 않는 것..

맨체스터 시티를 좋아하는 개인이 쓴 글입니다. 개인의 의견이기에, 다소 편향성을 보일 수도 있습니다. 최대한, 정보 전달을 위해 글을 쓰도록 하겠습니다. 혹시나 잘못된 정보를 전달하고 있다면, 댓글로 알려주시면 감사하겠습니다. 잉글랜드 프리미어 리그에서 내가 가장 좋아하는 맨시티에게, 좋지 못한 일이 발생했다. 맨체스터 시티가 2009년부터 2018년 사이 100건이 넘는 재정 규정을 위반한 혐의를 받고 있다. 예전에도 비슷한 사건이 터진 적 있다. 2년 전에 UEFA 징계로 인해 유럽 대항전 2년 출전 정지 징계를 받았다. 하지만 스포츠 징계 중재소(CAS)에서 항소심을 열었고, 이에 승소해 징계를 받지 않았다. 그때는 유럽 대항전 2년 출전 정지 징계에 불과했지만, 이번에는 최대 리그 퇴출이라는 말까..

▶2174 - 로봇 시뮬레이션 ▶문제 가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다. 이 땅 위에 로봇들이 N(1≤N≤100) 개 있다. 로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. 위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다. 또한 각 로봇은 맨 처음에 NWES 중 하나의 방향을 향해 서 있다. 초기에 서 있는 로봇들의 위치는 서로 다르다. 이러한 로봇들에 M(1≤M≤100) 개의 명령을 내리려고 한다. 각각의 명령은 순차적으로 실행된다. 즉, 하나의 명령을 한 로봇에서 내렸으면, 그 명령이 완수될 때까지 그 로봇과 다른 모든 로봇에게 다른 명령을 내릴 수 없다. 각각의 로봇에 대해 수행하는 명령은 다음의 세 가지가 있다. L: 로봇이 향하고 ..

매일 내가 원하는 기사를 크롤링해서 알려주면 좋겠다는 생각을 했다. python 크롤링과 github action을 이용해서 매일 issue로 기사를 알려준다. 내가 했던 것들을 한번 포스팅에 써보려고 한다. https://github.com/dhalsdl12/Naver_Article GitHub - dhalsdl12/Naver_Article Contribute to dhalsdl12/Naver_Article development by creating an account on GitHub. github.com 모든 과정을 작업한 github 주소이고, 전체 코드는 여기서 확인할 수 있다. 나는 맨체스터 시티의 팬이라서, 네이버에서 '맨체스터 시티'를 검색해 크롤링하도록 했다. 관련도 순으로 최근 1일 동..

▶1197 - 최소 스패닝 트리 ▶문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. ▶입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 ..

▶2295 - 세 수의 합 ▶문제 N(5 ≤ N ≤ 1,000) 개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라. 예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다. ▶입력 첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경..

▶2629 - 양팔저울 ▶문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확..