# codingame

jungmyeong96

세계적으로 유명한 AI대회인 CodinGame의 2022 Fall Chanllenge에 42seoul소속으로 참여하게 되었습니다. 42에서는 CodinGame의 데이터를 토대로 42를 대상으로하는 대회를 따로 열었는데, Amsterdam의 Codam 캠퍼스와 함께 랜덤으로 국제팀을 결성하여 3인 구성인 여러 팀을 만들어 대회를 진행하고 그들 중 가장 순위가 높은 인원에게 우승의 자격을 부여하는 것이었습니다. 팀원과의 소통 저희 팀은 같은 한국인인 minsuki2님과 저 그리고 네덜란드 codam

flfns333

Mad Pod Racing > CodinGame플랫폼에서 제공하는 AI 코딩실력 향상을 위한 컨텐츠이다. 모든 검문소를 가장 빠르게 통화하는 bot을 만드는것이 목표이다. 주어지는 코드 주어진 코드의 x, y좌표가 잘못 적혀있어 수정이 조금 필요하지만, 수정하고 나면 아래와 같이 다음 레벨을 추천해준다. 이처럼 좀더 빠른 적을 제공하여 나의 코드를 좀더 빠르게 움직이도록 수정을 요구한다. ![](https://velog.velcdn.com/images/flfns333/post/44ae015

flfns333

42서울에서 연계하는 codam! 하지만 아쉽게도 신청이 마감되었다. 해당 이벤트에서 공식적으로 사용하는 codinGame이라는 플랫폼에 접속하여 아쉬운 마음을 달래보고자 한다. CodinGame 페이지 주소 > #### 시작시 만들어 져있는 게임 엔진에 적을 식별하는 간단한 코드를 알려줌으로 써 관심을 끌었다. 아래의 사진은 옮겨 받은 식별 코드로 동작하는 게임을 캡쳐한 것이다. 이러한 방식으로 코딩을 유도하는 목적 > WHAT’S THIS GAM

newbieski

https://www.codingame.com/training/medium/river-crossing 문제요약 농부/늑대/염소/양배추가 강을 건넘 농부는 + 1을 갖고 강을 건널 수 있음 모든 상태는 조건을 지켜야함 농부가 없는 상태에서 늑대 + 염소 안됨 농부가 없는 상태에서 염소 + 양배추 안됨 상태표시는 L, R, L, R 같이 표시 시작상태 -> 끝 상태 가는 가장 짧은 경로, 짧은 경로가 여러개면 알파벳으로 앞서는 것 접근법 BFS + 경로 추적 어짜피 상태는 2^4 = 16개임 python에서 방문 처리 + 경로 추적은 set으로 구현함 착각했던 점 어떤 상태로 오는 가지 수는 1개이므로 유일한 경로만 있을 것 같은데? 반례 L R L L => R R L R, L R L R => R R L R 농부의 상태를 봐서 R이면

newbieski

https://www.codingame.com/training/hard/the-bridge-episode-2 접근법 완전탐색 backtracking 6개의 command가 있어서 경우의 수가 많아보이지만 진행하다 보면 쓰이지 않는 command 가 생김 : 적절한 가지치기가 됨 오토바이의 주소를 이용해 완전 탐색 + backtracking 수행 처음 입력시 완전탐색으로 답을 구한 후 매 턴 구한 답을 출력함 후기 다음번 오토바이의 speed 초기화 오류가 있어서 한참 해맴

newbieski

https://www.codingame.com/training/medium/find-the-winning-strategy 접근법 nim game 게임이론 Impartial game 스프라그 그런디 이론 참고 https://ohgym.tistory.com/21 https://librewiki.net/wiki/%ED%95%84%EC%8A%B9%EC%A0%84%EB%9E%B5%EA%B2%8C%EC%9E%84 정리 매번 이해하는 이론임 승리 상태를 유지하는게 목적인데, 이 경우에는 내 턴에 모든 가져갈 수 있는 것들의 xor이 0이 되게 유지하면 됨 주머니에서 마음대로 돌을 가져가는 게임이 이 문제와 동일한 내용임 요약 : 주머니에서 마음대로 돌을 가져가는데, 못가져 가는 사람이 짐 https://www.acmicpc.net/problem/11868 0이 아닌 경우에 0을 항상 만들 수 있는데, 이 부분 이해가 매번 어려웠음 -

newbieski

https://www.codingame.com/training/medium/rational-number-tree 접근법 LRLR은 직접 해보면 됨 : 왼쪽, 중간, 가운데 적절히 교체하면서 수를 찾는 부분은 이진탐색 사용 백준에 비슷한 문제가 생각나서 분수의 특징을 찾는 것인가 했는데.. 신기하게도 진짜 "사이값"임 : 새로 생성되는 분수의 크기는 두 분수의 사이에 있음 이를 이용해서 찾는 값이 왼쪽인지? 오른쪽인지 찾아갈 수 있음

newbieski

https://www.codingame.com/training/medium/dice-probability-calculator 접근 방법 : 완전탐색 주어진 테스트케이스에서 나올 수 있는 숫자의 범위가 엄청 크지는 않음 경우의 수도 엄청 크지 않음 중위 -> 후위 표현식 변환 필요 https://www.acmicpc.net/problem/1918 https://crong-dev.tistory.com/19 "d" 변수는 적절히 처리해서 완전탐색으로 활용

newbieski

https://www.codingame.com/training/medium/photo-booth-transformation 접근법 이동함수를 구하고 cycle의 길이를 구하고 길이들의 최소공배수 gcd(a, b, c) = gcd(a, gcd(b, c)) lcm(a, b, c) = lcm(a, lcm(b, c 후기 문제설명에서 보여주는 링크가 흥미로움 (재귀적인 그림)

newbieski

https://www.codingame.com/training/medium/bender-episode-1 문제에서 시키는대로 구현해야하는데 이동 경로도 출력해야함 beer 상태일때는 벽을 부수고 이동하는 것임! 접근법 conditon에 대한 변수들 생성 vty방향[beer] 처음에는 boolean으로 했으나 loop처리를 위해 int로 변경 이동함수 다음 이동을 결정함 방향만 바뀌는 경우 방향만 바꿔놓고 return 함 이때 중복 처리를 방지하기 위해 ignoreflag를 이용함 위치가 바뀐 경우 이동 경로를 저장함 이때 transport로 바뀌는 경우는 저장하지 않음 ignoreflag를 활용해서 경로를 저장함 loop 처리 방문한 곳을 또 방문하면 loop라고 판단하였으나 예외가 있었음 벽을 부수고 방문한 곳을 또 방문한 경우 count를 저장

newbieski

https://www.codingame.com/training/easy/retaining-water/discuss easy 난이도라 별거 아닌 줄 알았는데 까다로웠음 접근 1 상/하/좌/우의 최대값중에서 최소값이 채울 수 있는 최대 높이인줄 알았는데, 물이 흐른다는것을 고려하지 못했음 접근2 외벽은 물을 채울 수 없으니 "벽"이라고 두고 완전탐색으로 접근함 어떤 위치를 target = 'Z'에서 거꾸로 채워봄 인접한 것들이 target보다 작으면 계속 채워봄 채워야 하는 곳이 "벽"이면 실패임 이렇게 찾다가보면 적절한 target을 찾을 것임 target으로 채움 target을 찾을때랑 비슷한데 다른점은 채우는 물의 양을 계산해서 합에 더하고 처리를 끝냈다는 표시를 함 "벽"인 경우는 진행하지 않음 결과적으로 처리를 끝냈다는 표시 = "벽"과 동일하게 처리함 후기 단순한 접근

newbieski

https://www.codingame.com/training/easy/a-childs-play cycle을 찾는 문제 위치 + 방향까지 고려해서 찾아야함 cycle의 시작점에서 k번 움직이는 것을 고려해야함 n = p + cycle_len * x + a

newbieski

https://www.codingame.com/training/easy/container-terminal easy 난이도였는데 많이 해맸던 문제 count를 구하고 앞으로 나올 것들은 미리 비워놓아야하나....로 접근했는데 실패 : 예시에서 CBACBACBACBA를 보고 그렇게 접근함 그리디로 접근하면 됨 스택에 쌓인 것 중 같은 것이 있다면, 그곳에 쌓는다. 놓을 수 있는 것 중에서 가장 작은곳에 쌓는다. 아니면 새로 스택을 만든다. 생각해보니 "같은 것이 있는 조건"은 "놓을 수 있는 것 중에서 가장 작은 곳에 쌓는 조건"에 포함이 되겠다!

newbieski

https://www.codingame.com/training/hard/skynet-revolution-episode-2 episode1일때는 길을 끊어서 바이러스가 gateway까지 못가게 막아야함 gateway는 한개 길은 아무곳이나 끊을 수 있음 이때는 바이러스의 현재 위치부터 bfs해서 최단경로에 있는 길을 끊어서 해결했었음 episode2 gateway가 여러개(최대 20개) gateway와 바로 연결된 길만 끊을 수 있음 접근1 bfs 수행 후 가까운 gateway근처에 있는 아무 길이나 끊었음 실패 : 갈래길에서 한쪽만 끊어서 바이러스가 다른 한쪽으로 가게됨 여유가 있게 끊을 수 있는 길이 있고, 미리 끊어야하는 길이 있구나.. 깨달음 접근2 끊어야하는 길들이 한 지점에 몰려있는 경우가 있는데, 많이 몰려있는 길 먼저 끊음 + 가까운것 먼저 실패 : 여전히 미리 끊어야하는 길이 있었음..여유가

newbieski

https://www.codingame.com/training/easy/1d-spreadsheet n번째 입력은 n번째 cell의 값임 reference를 참고할 수 없으면 일단 넘어감 입력이 100개이므로 100번 반복하다가 보면 언젠가는 모든 cell의 값을 구함 dependency등을 이용해서 순서대로 구해도 되지만 n이 100개라서 그냥 반복해도 됨

newbieski

https://www.codingame.com/multiplayer/optimization/code-of-the-rings 설명 주인공이 숲에서 탈출해야함 탈출하려면 주어진 마법 주문을 말해야하는데, 돌멩이(rune)를 이용해야함 rune은 30개가 있고, 각각의 rune은 빈공간 ~ Z까지 있음 rune은 위 아래로 돌릴 수 있는데 순서대로 돌아감(캔싱턴 락 다이얼 같은 것) 주인공은 rune을 옮겨갈 수 있고, 가장 끝이랑 처음은 연결되어 있음(원형 트랙 같다고 보면 됨) 옮기고/돌리고/말하고.... 저런 action을 사용해서 마법주문을 말해야하는데 action 길이를 짧게하는 것이 목표임 quest map 통과하려면 6.5K보다 작아야함 expert rule 이 있음 : loop 사용! 접근1 - 단순하게 마법주문 하나씩 처리하는데, "이동 + rune 돌리기" 값이 가장 작은 곳을 찾아서 처리 11489 = 11K

newbieski

https://www.codingame.com/multiplayer/optimization/code-vs-zombies 설명 주인공이 잘 이동해서 좀비를 처리하고, 사람을 구해야함 사람들이 다 좀비에게 당하면 게임이 끝남 주인공은 주변 일정 공간에 있는 좀비를 다 처리할 수 있음(다수) 좀비는 일정 거리에 있는 사람을 없앴을 수 있음(1명?) score를 많이 얻어야 최종 랭킹이 올라감 접근법 좀비와 가장 가까이 있는 사람을 구하러 가기 좀비와 너무 가까운 사람은 포기 지금 구하러 가도 못구할 것 같은 사람은 포기 이렇게 해도 구할 사람이 없으면? 좀비와 가장 가까운 사람 구하기 좀비와 가장 멀리 있는 사람 구하기 테스트케이스가 애니메이션으로 잘 나와서 적절히 고려해보면 됨 아쉬운 점 목표 점수인 40000점은 넘기기는 함 테스트케이스별로 주인공의 움직임을 보면....답답한 모습이 많이 보임 더

newbieski

https://www.codingame.com/training/hard/cloudy-weather 설명 로봇이 움직이는데 목적지로 가서 수리를 해야함 구름을 피해서 출발지점으로 가야함(배터리 상태가 안좋아서 태양에너지가 있을때만 이동가능하고, 구름으로 가려지면 이동을 못함) 최단 거리 구하기 접근법 단순 BFS로 하기에는 값의 범위가 큼 (10^9) 구름의 개수는 250개 이하이나, 값의 범위가 큼(10^9) BFS로 접근하되 좌표를 적절히 압축함 구름의 시작/끝 + 시작-1/끝+1 을 하면 대략 1000 * 1000 개 정도의 좌표 생성 시작 -1, 끝 + 1도 좌표에 추가하는 이유는 우주선이 구름에 바싹 붙어서 가는 경우도 고려하기 위해서임(한 칸 = 압축한 한 칸으로 하고 싶은데, 구름 주변 한 칸도 살리고 싶어서임) 1000 * 1000 지도 크기를 대상으로 BFS 실시 생성한 지도에서 한 칸의 크기가 서

newbieski

https://www.codingame.com/training/hard/the-labyrinth LABYRINTH : 미궁 설명 주인공이 control room을 찾아서 끄면(?) 그때부터 타이머가 돌아감 타이머가 돌기전에 시작지점으로 와야함 주인공 주변 5*5만 보여주고 나머지는 안개로 안보이므로 알아서 잘 찾아야함 연료가 1200 주어짐 = 1200번 이동 가능 접근법 control room을 찾기전과 찾은 후로 나눔 control room을 찾은 후에 약간의 트릭(?)이 필요함 타이머는 불가능한 값이 주어지지는 않는 것 같음 연료도 잘 쓰면 부족하지는 않은 것 같음 control room을 찾은 후 C -> 시작점으로 BFS를 수행해서 최단거리를 구하고(구하면서 경로 저장) 현재 상태에서 어디로 가야할지 판단해서 간다 이때 최단거리 > 알람이면 뭔가 안 구한 부분이 있는 것이니까 안개부분(? 부분)을 더 탐색한다 매번 BFS

newbieski

화성에 우주선을 착륙시켜야한다. 단, 조건이 있다. 평평한 곳에 우주선의 각도는 똑바르게(문제에서는 0도라고 표현) 수평 속력은 20m/s 이하(절대값) 수직 속력은 40m/s 이하(절대값) 그외 문제 조건들은 문제에서 확인하면 됨 https://www.codingame.com/multiplayer/optimization/mars-lander 문제는 1단계, 2단계로 주어지는데 1단계는 튜토리얼 수준임 접근 방법 - 1단계 모든 조건이 단순화 된 상태라서, 수직 속력이 커지면 적절히 추력을 시켜주면 됨 접근 방법 - 2단계 테스트 케이스도 여러개이고 할 일이 많음 로켓을 목적지근처로 보내는 것과 착륙을 하는 부분으로 나눠서 접근함 목적지 근처로 보내기 완전 탐색 + 시뮬레이션 rotate를 -90 ~ 90으로 했을때와 thrust를 0 ~ 4로 했을때를 조합함 hspeed, vspeed를 구해서 이 상태로 착륙지의 중간에 해당하는