알고리즘17

• 

  알고리즘에서 이벤트 기반 접근 오늘은 특정 문제의 풀이를 가져오진 않았다. 주말에 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.

• 

  [알고리즘, 코드트리] 색깔 트리 - java 문제문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 요약하자면 이렇다. 총 네 가지 동작을 수행해야 한다.(1) 노드 추가 - 노드를 트리에 추가합니다. 각 노드는 고유한 번호 mid​, 부모 노드 번호 pid​, 색깔 color 그리고 최대 깊이 maxdepth​ 를 가집니다. - 만약 기존 노드들의 maxdepth​ 값으로 인해 새로운 노드가 추가됨으로써 모순이 발생한다면, 현재 노드는 추가하지 않음에 유의합니다.(2) 색깔 변경 - 특정 노드 mid​ 를 루트로 하는 서브트리의 모.. 알고리즘 2024. 10. 5.

• 

  [알고리즘, BOJ] 13460 구슬 탈출 2 - java 문제스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1 ×1 크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 .. 알고리즘 2024. 10. 4.