본문 바로가기

알고리즘

 (66)
2629 - 양팔저울[G3] 문제https://www.acmicpc.net/problem/2629 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.입력첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게..
15683 - 감시[G4] 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 백트래킹 및 완전 탐색. 문제의 주어진 조건인 'CCTV는 90도 방향에서 회전할 수 있다' 의 모든 경우를 DCCTV의 배열에 전부 지정하였다. 이는 CCTV의 최대 개수가 8임에 가능한 점에 유의. 이후 백트래킹을 사용하여 모든 경우의 수를 탐색하였다. 자세한 내용은 코드와 주석을 참고할 것. 코드 import java.util.*; import java.io.*; cla..
배열 돌리기(오른쪽, 왼쪽 돌리기) 문제 풀이 시, 배열을 돌리는 문제를 종종 만나게 된다. 돌리는 방법을 핵심적으로 정리하였다. 방법 오른쪽 돌리기 (90도) - 1. 전치 행렬 수행 - 2. 수평 변환 수행 왼쪽 돌리기 (90도) - 1. 전치 행렬 수행 - 2. 수직 변환 수행 N * N 배열을 90도 오른쪽으로 회전하는 알고리즘을 Java로 구현하려면 다음과 같은 절차를 따른다. 1. 전치: 배열의 행과 열을 바꾼다. 이 과정에서 배열의 (i, j) 위치에 있는 원소는 (j, i) 위치로 이동한다. 말이 어려워 보이지만, 사실 그냥 대각선을 기준으로 arr[i][j]를 arr[j][i]로 변경하라는 뜻이다. //1. 전치 수행 for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { i..
왕실의 기사 대결[G3] 문제 https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 사실 기존 방식과 조금 다른 방식을 사용했다. copy 메서드를 통해 연쇄된 행동이 잘못되었을 경우, 백업된 값으로 다시 복구하는 기능이다. 또한, 문제의 가장 핵심은 '한 번에, 어딘가에 이동을 저장해놨다가', 모든 조건이 만족되었을 경우에만 일괄적으로 옮기는 것이다. 개념 자체는 백트래킹..
루돌프의 반란[G2] 문제 https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/submissions?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드 /* 2120 ==> 빠듯하게 3시간.. 디버거 하나하나 다 찍고 검증 Break문과 return, Continue를 잘 검증하자.. */ import java.io.*; import java.util.*; public class Main { static int N,M,P,C,D; stati..
나무박멸[G4] https://csg1353.tistory.com/51 이전에 틀렸던 문제를 연습차 다시 풀이하였다. 코드 import java.util.*; import java.io.*; public class Main { static int N, M, K, C; static int[][] map; static int[][] jecho; static int answer; static Queue tempQ = new ArrayDeque(); static Queue treeQ = new ArrayDeque(); static final int[] DR = {-1, 0, 1, 0}; static final int[] DC = {0, 1, 0, -1}; static final int[] DCR = {-1, -1, 1, 1};..
5972 - 택배 배송(G5) 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. N (1
요격 시스템 (LV.2) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용..

티스토리툴바