본문 바로가기

알고리즘 문제풀이

 (9)
[백준] 10942 팰린드롬? (Java) https://www.acmicpc.net/problem/10942문제 설명팰린드롬 : 거꾸로 읽어도 똑같은 단어- 숫자 배열을 줬을 때 주어진 범위 구간이 팰린드롬인지 아닌지 확인조건* 1 ≤ N ≤ 2,000* M(질문의 개수) : 최대 백만문제 해결 프로세스1. 주어진 범위 구간에서 s인덱스와 e 인덱스 자리의 값이 같은지 확인2. 같지 않다면 0.3. 같다면 s + 1과 e-1 인덱스 비교4. DP로 접근 (2차원 배열)  - s와 e의 차가 2보다 작을 때는 s인덱스와 e인덱스만 비교해줘도 바로 팰린드롬인지 아닌지 알 수 있음  - 2보다 커질 경우 s + 1과 e-1 인덱스를 매개변수로 두고 재귀 호출코드import java.io.BufferedReader;import java.io.IOExc..
[코드트리] 이상한체스 (Java) 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 문제설명1. 각각의 말은 네 방향 중 한가지 방향을 선택할 수 있음2. 체스판의 말들의 방향을 적절히 설정하여 갈 수 없는 격자의 크기를 최소화하라 -> 최대한 많이 가라3. 본인 말은 뛰어 넘어갈 수 있다4. 상대 말은 뛰어 넘어갈 수 없다. 1번 : 정해진 방향 한방향으로만 이동가능  -> 0, 1, 2, 3 중 하나2번 : 좌우로 이동 -> {0, 1}, {2, 3} 중 하나 3번 : 상좌, 상우, 하좌, 하우 -> {0,2}, {0,3}, {1,2}, {1,3}4번 : 상좌우, 좌상하, 하좌우, 우상..
[코드트리] 생명과학부 랩 인턴 (Java) 문제설명n x m 격자판에서 움직이는 콤팡이 채취빨간색으로 표시된 숫자 : 곰팡이 크기를 의미파란색으로 표시된 숫자 : 속력을 의미1. 첫번째 열부터 탐색(위에서 아래로)2. 곰팡이 채취 후 해당 칸은 빈칸이 된다.3. 해당 열의 채취가 완료되면 곰팡이는 이동을 시작4. 벽에 도달한 곰팡이는 방향을 반대로 바꾸고, 속력은 유지한 채 이동5. 한 칸에 두마리 이상의 곰팡이가 있을 때는 크기가 큰 곰팡이가 다른 곰팡이를 잡아먹음6. 오른쪽 열로 이동-> 채취한 곰팡이 크기의 총합을 구하여라입력n x m: 격자 크기k : 곰팡이 수문제 해결 프로세스1. 첫번째 열 -> 마지막 열까지 이동할 때까지 프로그램 실행2. 해당 열의 곰팡이 탐색()3. 이동 위치를 저장할 배열 생성 후 곰팡이 이동4. 이미 곰팡이가 ..
[백준] 14712 넴모넴모 (Java) 문제설명격자판의 비어 있는 칸을 임의로 골라 "넴모"를 하나 올려놓거나, "넴모"가 올라간 칸 네 개가 2 x 2사각형을 이루는 부분을 찾아 그 위에 있는 "넴모"들을 모두 없애는 것을 계속 반복한다. 넴모가 사라지지 않는 배치의 가짓수를 계산하라조건- 최대 5 x 5 배열문제 해결 프로세스DFS로 네모를 하나씩 놓고 네모가 생성되었는지 체크네모가 생성되었다면 종료그렇지 않다면 정답 + 1코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N, M; static bool..
[백준] 13460 구슬탈출2 (Java) https://www.acmicpc.net/problem/13460문제설명구슬탈출 : 직사각형 보드에 빨간 구슬과 파란구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임가장 바깥 쪽 행 열을 막혀져 있음보드에는 구멍이 하나 있다.파란구슬은 구멍에 들어가면 안된다.빨간 구슬, 파란구슬 동시에 들어가도 안된다.빨간 구슬과 파란구슬은 동시에 같은 칸에 있을 수 없다.기울이는 동작은 더 이상 구슬이 움직이지 않을 때까지 진행최소 몇번만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하라입력* 두 정수 N, M (3 ≤ N, M ≤ 10)* '.' 빈칸* '#' 벽* 'O' 구멍* 'R' 빨간 구슬* 'B' 파란구슬문제 해결 프로세스1. 빨간 구슬과 파란 구슬의 위치를 모두 저장할 수 있는 클래스 선언..
[백준] 12100 2048(Easy) (Java) https://www.acmicpc.net/problem/12100입력N (1 ≤ N ≤ 20)들어올 수 있는 최대 값 2 ~ 1024로 2의 제곱근 형태문제 해결 프로세스1. 5번을 움직여 최대 값을 찾기 위해서는 순열이 필요함 (상하좌우)2. 순열이 만들어졌을 때 해당 방향으로 게임 시작3. 원본배열 남기고 복사배열 사용4. 벽으로 밀기, 합치기 2개 메서드 필요코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N, answer; static int[][] original; stati..
[백준] 1477 휴게소 세우기 (Java) https://www.acmicpc.net/problem/1477문제설명1. 현재 휴게소의 개수는 N개이다2. M개의 휴게소를 추가로 설치하려고 함3. 휴게소의 거리 중 최대값이 최소가 되도록 하라조건* 시간 2초1. 이미 휴게소가 있는 곳은 설치 불가2. 고속도로 끝에는 설치 불가3. 휴게소는 정수의 위치만 세울 수 있음입력0 ≤ N ≤ 501 ≤ M ≤ 100100 ≤ L ≤ 1,0001 ≤ 휴게소의 위치 ≤ L-1문제 해결 프로세스1. 휴게소의 위치를 입력받고, 오름차순 정렬(간격을 계산해야하므로 0과 L의 크기를 배열 양 끝에 넣어줘야 함)2. 휴게소의 최대 간격 설정(tempInterval) -> 정확한 간격을 모르므로 L의 중간값으로 설정하고 추후 변경하자3. L에서 tempInterval 나..
[코드트리] 자율주행 자동차(Java) 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai조건1. 현재방향 기준 왼쪽으로 이동한 적이 없을 시 좌회전 후 1칸 전진2. 인도이거나 이미 방문한 경우 좌로 회전 반복3. 모든 방향에 대해서 방문한 경우 현재 방향을 유지한 채 한칸 후진(후진 불가하다면 작동 중지)-> 자율 주행 자동차의 작동이 멈췄을 때의 거쳐갔던 면적 계산하기입력도로 0, 인도 1문제 해결 프로세스1. n x m 사이즈의 도로와 방문배열 초기화2. 자동차의 위치정보, 방향을 담을 수 있는 클래스 생성3. 왼쪽 방문 체크 후 방문하지 않았다면 차량의 위치와 방향 변경4. 방문했다면 자..

티스토리툴바