설모의 기록

이 문제는 로봇청소기가 map을 돌아다니며 얼마만큼의 영역을 청소하는지를 구하는 문제입니다. 로봇청소기가 돌아다니는 조건은 아래와 같습니다. 현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 수행한다.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 이 문제는 전형적인 dfs 문제입니다. 우선 제가 생각..

이 문제는 높이 차이가 1이고 L만큼 평평한 곳에 경사로를 설치하는 문제입니다. map 그림만 보고 dfs, bfs 문제라고 예상했는데 그냥 이중포문 문제였네요! 위의 그림과 같은 땅이 있을 때, L = 2 라고 주어졌습니다. 높이가 차이나는 곳은 그 차이가 1이여야 하며, 주어진 조건에 맞게 경사로를 설치할 수 있어야 합니다. 그림에서는 초록색으로 표시한 부분이 지나갈 수 있는 길입니다.길은 가로와 세로만 생각하면 되니까 편하게 배열 두 개를 선언하고 i, j 만 바꿔서 저장한 후에 똑같은 로직을 사용했습니다. checkBuild 함수에서는 받은 배열의 index 에 저장된 길이 지나갈 수 있는지를 확인합니다. 지나갈 수 없다면 return을, 지나갈 수 있다면 result에 +1 을 하는 방식입니다...

이 문제는 4개의 톱니바퀴가 연쇄적으로 회전한 후의 점수를 산출하는 문제입니다. 4개의 톱니바퀴는 각각 8개의 톱니를 갖고 있으며 N 또는 S극입니다. 하나의 톱니바퀴를 회전하면 위의 그림과 같이 다른 톱니와 맞닿아 있는 부분이 다른 양 옆의 톱니도 반대방향으로 회전하고, 그 톱니들의 양 옆도 맞닿아 있는 부분이 다르다면 연쇄적으로 회전을 하게 됩니다. 그림이 어지럽게 그려져서 그렇지, LinkedList로 생각하면 쉽습니다. 시계방향으로 회전하는 것은 리스트의 마지막 요소를 뺴와 첫번째 인덱스에 추가하는 것이고, 반시계방향으로 회전하는 것은 리스트의 첫번째 요소를 빼와 마지막에 추가하는 것과 같습니다. 그리고 회전하기 전에 각각의 톱니바퀴가 양 옆의 톱니바퀴와 맞닿아 있는 곳이 같은지를 체크해주고, 회..

이 문제는 다트게임에서 얻는 점수를 출력하는 게임입니다. 라디안 각도가 헷갈려서 연습문제 1~4번 문제 중 가장 많이 헤맨 문제입니다. 먼저 점수를 다르게 받을 수 있는 구역에 대한 반지름 5개가 주어지고, 대희가 다트를 쏜 개수가 주어지며 그 다음부터 쏜 다트의 (x, y) 좌표가 주어집니다. 우선 다트판이 20개 칸으로 나누어져있고, 반 개의 칸만큼 회전되어 있으므로 저는 다시 반 개의 칸만큼 회전시켜야 된다고 생각했습니다. 그래서 시계방향으로 회전해서 0~(360/20) 의 점수가 13이라 하고, 대희가 쏜 다트의 각도도 각각 -9만큼 회전시켰습니다. 주어진 (x, y) 를 피타고라스 정리를 이용해 원점으로부터의 반지름(대각선)의 길이를 구할 수 있습니다. 이 반지름( Math.sqrt(x*x + ..

이 문제는 정우가 각 과목에서 얻을 수 있는 시험 점수가 입력되고, 정우가 최고 점수를 맡도록 입력된 K만큼 과목을 고르는 문제입니다. 간단한 문제여서 배열을 정렬한 다음, 배열의 끝에서부터 K개만큼 Answer에 더해 출력했습니다. 간단한 문제이기 때문에 설명도 간단하게 하고 넘어가겠습니다.

이 문제는 마지막 라운드의 사람들의 점수를 알려줬을 때, 최종 우승할 가능성이 있는 사람들의 수를 구하는 문제입니다. 점수는 참가자가 N명이라고 했을 때, 1등부터 차례대로 N점, (N -1) 점, (N - 2)점, ... , 1점 을 부여합니다. 저는 우선 입력받은 사람들의 점수를 Arrays.sort() 함수를 이용해 정렬했습니다. 그 배열을 arr이라고 하겠습니다. arr[i] 아이가 1등을 하려면 arr[i + 1] ~ arr[N - 1] 사람들이 arr[i] 사람보다 낮은 점수를 받아야 합니다. 따라서 가장 이상적인 방법은 그 다음 사람부터 N -1, N - 2, ... , 1 점을 받으면 가능성이 있을거예요. 그 앞(arr[0] ~ arr[i - 1]) 은 생각안해도 되는 이유는 어차피 그 앞..

이 문제는 주어진 숫자중에서 홀수번 나타나는 숫자들의 XOR 연산결과를 출력하라는 문제입니다. 저도 풀다가 함정에 빠져서 배열을 만들고, 배열의 인덱스를 숫자라 생각하고 숫자가 나타나는 횟수를 배열에 저장하는 식으로 풀려고 했더니 메모리를 초과했다는 런타임 에러가 발생했습니다. '대체 배열을 안 쓰고 이걸 어떻게 풀지..?' 라는 생각에 빠져있었는데 이게 바로 XOR 연산의 함정입니다. 기본적으로 XOR 연산은 두 수 a, b가 다르면 0이 됩니다. 따라서 b^b를 하면 자동으로 상쇄되기 때문에 홀수인지 짝수인지 나타난 횟수를 신경쓰지 않고 XOR연산에 모두 추가하면 되는 간단한 문제였습니다. XOR 연산의 기본 개념만 알고 있었어도 빠르게 풀고 넘길 문제였습니다T^T

팰린드롬(Palindrome)이란 '기러기' 와 같이 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말합니다. 이 문제는 주어진 문자열이 팰린드롬인지 아닌지를 검사하는 간단한 문제입니다. 저는 반복문을 이용해 처음부터 가운데까지 검사하는 코드를 구현했습니다.

이 문제는 주어진 NxM 배열에서 (0, 0) 에서 (N - 1, M - 1) 칸까지 가는 최소한의 칸의 수를 구하는 문제입니다. 문제에서는 (1, 1) 에서 (N, M) 으로 가는 최소한의 칸의 수를 구하라고 했지만, 인덱스의 개념상 (0, 0) 에서 (N - 1, M - 1) 로 가는 것이 이해하기 편해서 아래의 문제는 이것을 바탕으로 풀이한 알고리즘입니다. 이 문제는 BFS 문제입니다. 처음 (0, 0) 을 큐에 넣고 while 문 안에서 큐에 있는 노드들의 다음 목적지를 다시 큐에 넣고 반복하면 됩니다. 코드는 아래와 같습니다.

바둑과 체스같은 게임에서는 상대방이 다음에 어떤 자리에 수를 놓을것인가 까지 생각을 하며 게임을 진행해야 합니다. 이런 게임에 인공지능을 투입한다면, 이 인공지능도 사람이 어디에 놓게 될것인가를 생각하도록 코드를 구현해야 합니다. 이 때 사용하는 알고리즘이 바로 최소최대 알고리즘입니다. 최소최대 알고리즘 (Minmax Algorithm)바둑과 체스같은 게임에서는 상대방은 내가 제일 불리한 곳에 수를 두게 될 것입니다. 그래서 내 차례에는 내게 제일 유리한 수, 상대방 차례에는 내게 제일 불리한 수가 선택될 것이며, 단지 다음 턴만이 아니라 그 이후의 수까지도 바라보며 탐색을 해가는 과정입니다. 정리하자면, 최대와 최소를 번갈아가며 선택해 가장 좋은 경우를 선택하는 것이 최소최대 알고리즘의 답이 됩니다. ..