2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 에라토스테네스의 체를 생각하며 가장 작은 수부터 리스트에 추가하고 동시에 추가된 수들을 회전시켜 얻은 시계수가 아닌 수들은 걸러내는 방법을 적용했다. 1111을 가장 먼저 리스트에 추가하면 1111을 회전시켜 얻은 1111, 1111, 1111을 확인한다. 모두 같으므로 패스. 1112는 걸러지지 않았으므로 리스트에 추가한다. 1121, 1211, 2111을 제외한다. 이하 반복 입력된 수를 돌려 얻은 시계수가 리스트의 몇번째 항목인지만 확인해 출력하면 끝. using System; us..

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net IDEA 처음 봤을 때는 쉬운 정렬 문제구나 했다. 리스트를 만들었고 그냥 정렬해서 출력했다. 대신 List 형식의 요소를 꺼내올 때 하나씩 따로 꺼내오는 걸 몰라서 지저분하게 String 메소드를 이것저것 갖다 붙이게 됐다. 너무 맘에 안들어..하던 와중에 2차원 배열의 정렬 방법을 다른 분의 코드에서 찾았다. 리스트에서 특정 항목을 기준으로 배열하는 방법인데 엑셀에서 필터 적용하는 것과 비슷한 개념인 것 같..

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net IDEA 공집합을 제외한 모든 부분 집합의 원소의 합을 계산해보는 문제다. 하나만 고르는 경우, 둘을 고르는 경우, 이렇게 따로따로 생각하면 어떻게 접근해야할지 좀 막막한데 백트래킹의 원리를 생각해보면 모든 경로를 탐색하고, 매 탐색마다 탐색 중인 정점의 수치를 더해주고 되돌아갈 때 더했던 값을 다시 빼주면 1~N개까지의 원소를 갖는 모든 부분 집합을 한번씩 탐색할 수 있다. CODE using System; class Pro..

1247번: 부호 총 3개의 테스트 셋이 주어진다. 각 테스트 셋의 첫째 줄에는 N(1 ≤ N ≤ 100,000)이 주어지고, 둘째 줄부터 N개의 줄에 걸쳐 각 정수가 주어진다. 주어지는 정수의 절댓값은 9223372036854775807보다 작거 www.acmicpc.net 굉장히 쉬운 문제다. 그냥 입력을 받고 더해준 다음 부호를 확인해주고 출력하면 된다. BigInteger 형식을 쓴다면 말이다. 그렇게 쉽게 풀었다. using System; using System.Numerics; class Program { static void Main() { var n = new int(); var b = new BigInteger(); for(int i = 0; i < 3; i++) { b = 0; n = ..

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net IDEA 모든 가능성을 탐색하고 최적의 결과를 얻어내는 문제다. 처음에는 아무 생각 없이 BFS를 시도했다. 이 문제는 탐색 과정에 문자를 계속 붙여나가고 이걸 String으로 관리한다면 쓸모없는 메모리가 엄청 늘어날 것이다. 그래서 나는 StringBuilder로 경로를 저장하고 이걸 큐에 돌려 BFS를 실행하기로 했다. 너무 짧은 생각이었다. 문자 형식 데이터는 16바이트를 차지한다. 만약 한 지점에서 모든 방향이 가능했고 1회 탐색을 시도했다면 32..

20162번: 간식 파티 서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다. 집사는 서울이에게 N 일 www.acmicpc.net IDEA 이 문제는 아주 오래전 시도했다가 틀린 문제다. 입출력만 겨우겨우 하던 당시에는 너무 어렵다고 생각해서 취침 시간을 12분 남겨놓고 포기했던 모양이다. 문제를 간단히 정리하면 이렇다. 1. 서울이는 N일 동안 이어지는 간식 파티에서 간식을 골라 먹는다. 2. 서울이는 이전에 먹었던 간식보다 더 평점이 높은 간식만 먹는다. 3. 간식 파티가 끝날 때까지 서울이가 먹은 간식의 평점 총합의 최고치는? 오늘이 i일이고 오늘 주어지는 간식의 평점을 snack[ i ], ..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net IDEA 브루트포스 문제는 복잡한 생각을 할 필요가 없어서 좋다. 한 때 재밌게 하던 2048 게임을 구현하는 문제다. 모든 가능성을 탐색해서 원하는 결과를 뽑아내면 된다. 탐색 과정에서 이전 과정을 기억해두고 되돌아가 다른 경로를 탐색할 수 있도록 하는 것이 관건이다. N * N 크기의 배열을 스택에 담아 탐색 과정을 관리하도록 했다. 처음에는 N * N 배열을 매개변수로 하는 재귀 호출로 구현했다. 그런데 매개변수로 받아온 데이터는..

9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net IDEA 코드가 문제에 그대로 제시되어있어서 그대로 해봤다. w(11,11,11)만 해도 구하는데 몇분 걸린다. 이런 재귀호출의 경우 똑같은 매개변수로 호출된 메소드가 엄청나게 많다. 그럼 첫 호출에 어떤 값에 대한 정보를 기억해두면 두번째부터 불필요한 호출은 줄일 수 있다. 이렇게 여러번 호출될 값을 미리 저장해놓고 다음 호출에 저장된 값을 바로 출력해주는 방법을 메모이제이션 이라고 한다. 간단히 3차원 배열로 구현했다. CODE using System; clas..