알고리즘19

• 

  [알고리즘, BOJ] 1504 특정한 최단 경로 - java 문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, .. 알고리즘 2025. 6. 16.

• 

  [알고리즘, BOJ] 11066 파일 합치기 - java 문제소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40,.. 알고리즘 2025. 6. 16.

• 

  알고리즘에서 이벤트 기반 접근 오늘은 특정 문제의 풀이를 가져오진 않았다. 주말에 Moloco 코딩테스트를 보다가 뼈아프게 실수한 게 있어서 복기의 목적으로 문제를 정리해본다. 몰로코 코딩 테스트는 4문제 70분으로 주어진다. 난이도는 전반적으로 쉬운 편이다. 백준 기준으로 실버 1~5 수준의 문제가 나오는데 복잡한 알고리즘과 자료구조를 묻기보다 빠른 문제 해결 능력을 물어보는 유형이 나온다.결국 한 문제를 시간 내에 풀지 못하고 제출했다. 시험이 끝나고 곰곰이 생각해보니 분명히 풀었던 유형이었다. 코드트리의 "코드트리 오마카세"가 정확히 이런 유형이었다.구간의 변화를 이벤트로 관리코드시그널 문제를 구체적으로 밝힐 수는 없지만 코드트리 오마카세와 못 풀었던 문제의 유형을 일반화한다면 "구간의 변화를 이벤트로 관리"한다는 점이다. 이때.. 알고리즘 2024. 11. 11.

• 

  [알고리즘, BOJ] 1109 섬 - java 문제지민이는 보물을 찾아 떠나기 위해 섬과 바다가 그려져 있는 지도를 샀다. 지도는 N×M 크기의 직사각형 모양이고, 각각의 1 ×1 크기의 칸에는 ‘x’ 또는 ‘.’중의 하나가 쓰여 있다.바다는 ‘.’이 가로로 또는 세로로 최대로 연결되어 있는 그룹이다. 섬은 ‘x’가 가로, 세로, 또는 대각선으로 최대로 연결되어 있는 그룹이다.만약 어떤 섬이 다른 섬을 포함하고 있지 않는다면, 그 섬은 높이가 0이다. 만약 어떤 섬A가 포함하고 있는 섬 중에 가장 높이가 높은 섬의 높이가 K라면, 그 섬 A의 높이는 K+1이다.섬 A가 섬 B를 포함한다는 말은, 일단 A와 B가 다르고, 섬 B의 어느 곳에서 출발해도 A의 밖으로 나갈 수 없을 때이다. 이때 대각선으로 이동은 불가능하다.다음과 같은 지도를 보자.xxx.. 알고리즘 2024. 10. 19.

• 

  [알고리즘, BOJ] 17071 숨바꼭질 5 - java 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을.. 알고리즘 2024. 10. 17.

• 

  [알고리즘, 코드트리] 왕실의 기사 대결 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 아래와 같다. 총 두 가지 동작을 수행해야 한다. (1) 기사 이동 : 왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사.. 알고리즘 2024. 10. 11.

• 

  [알고리즘, 코드트리] 코드트리 메신저 - java ※ 주의!! 이 문제는 사람의 인내심과 정신력을 시험합니다!! 어쭙잖은 각오로 이 문제를 도전하지 마세요.  문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 아래와 같다. 총 다섯 가지 동작을 수행해야 한다.(1) 사내 메신저 준비 : 이진트리 구조의 사내 메신저를 초기화합니다. (2) 알림망 설정 ON / OFF  : 처음 모든 채팅방의 알림망 설정은 켜져있습니다. 이 기능이 작동되면 c번 채팅방의 알림망 설정이 ON 상태라면 OFF로 바꿔주고, OFF 상태라면 ON으로 .. 알고리즘 2024. 10. 11.

• 

  [알고리즘, 코드트리] 루돌프의 반란 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 아래와 같다. 총 네 가지 동작을 수행해야 한다.(1) 루돌프의 움직임 : 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다.(2) 산타의 움직임 : 산타는 1번부터 P번까지 순서대로 움직입니다. 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.(3) 충돌 : 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다. 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 C만큼의 점수를 얻게 됩니다. 이와 동시에.. 알고리즘 2024. 10. 10.

• 

  [알고리즘, 코드트리] 코드트리 오마카세 - java ※ 주의!! 이 풀이는 코드트리 해설을 강하게 참고하고 있습니다!!  문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 아래와 같다. 총 세 가지 동작을 수행해야 한다.(1) 주방장의 초밥 만들기 : 주방장이 시각 t에 위치 x 앞에 있는 벨트 위에 name 이름을 부착한 회전 초밥을 하나 올려놓는다(2) 손님 입장 : 이름이 name인 사람이 시각 t에 위치 x에 있는 의자로 가서 앉은 뒤 n개의 초밥을 먹을 때까지 기다리게 된다.(3) 사진 촬영 : 시각 t에 코드트리 오.. 알고리즘 2024. 10. 9.

• 

  [알고리즘, 코드트리] 고대 문명 유적 탐사 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 아래와 같다. 총 다섯 가지 동작을 수행해야 한다.(1) 탐사 진행. 3 X 3 격자를 90도, 180도, 270도 회전시킬 수 있다. (2) 이 때, 얻을 수 있는 가장 높은 순위의 유물을 획득한다.(3) 유물을 획득하면 해당 격자는 비어있게 되는데 이 때, 벽면에 써있는 유물의 번호를 주어진 순서대로 채운다.(4) 연쇄 반응을 통해 유물을 획득할 수 있다.(5) 위 (1) ~ (4) 과정을 Q번 반복한다.(6) 어떠한 방법.. 알고리즘 2024. 10. 8.

• 

  [알고리즘, 코드트리] 코드트리 투어 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 이렇다. 총 다섯 가지 동작을 수행해야 한다.(1) 코드트리 랜드 관련 정보가 주어집니다. 도시의 수 n 과 간선의 수 m, 그리고 m 개의 간선에 해당하는 정보 (vi​, ui​, wi​) 가 주어집니다.  (2) 코드트리 여행사는 (id, revenueid​, destid​) 에 해당하는 여행 상품을 추가로 만들고 이를 관리 목록에 추가 (3) 고유 식별자 id 에 해당하는 여행 상품이 존재하는 경우, 해당 id 의 여행 .. 알고리즘 2024. 10. 7.

• 

  [알고리즘, 코드트리] 마법의 숲 탐색 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하자면 이렇다. 총 네 가지 동작을 수행해야 한다.(1) 남쪽으로 한 칸 내려갑니다.(2) (1)의 방법으로 이동할 수 없으면 서쪽 방향으로 회전하면서 내려갑니다. 이렇게 이동할 때 출구가 반시계방향으로 이동합니다.(3) (1)과 (2)의 방법으로 이동할 수 없으면 동쪽 방향으로 회전하면서 내려갑니다. 이렇게 이동할 때 출구가 시계방향으로 이동합니다.입력첫 번째 줄에는 숲의 크기를 의미하는 R, C, 정령의 수 K가 공백을 사이에 두.. 알고리즘 2024. 10. 6.