본문 바로가기

[Algorithms]/[Problems]

 (32)
BOJ. 11657번. 타임머신 이번 문제는 벨만-포드 알고리즘을 활용한 문제다. 실제 코드 상에서도, 각 정점을 돌아보면서 최소비용을 갱신해 나가는 형태가 다익스트라(우선순위 큐)를 사용하지 않은 코드랑 비슷했다. 물론 음의 가중치가 포함된 문제라 다익스트라로는 해결할 수 없다. + 추가로 거리를 계산할 때 오버플로우가 나는 바람에 출력초과가 나왔다. 넘칠 것 같으면 처음부터 long으로 넉넉하게 잡아주는 것도 실수를 줄이는 방법이 될 것 같다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000..
BOJ. 1238번. 파티 이 문제는 다익스트라 알고리즘을 뒤집어 붙이는 문제이다. 처음에 리스트로 맵을 만든 다음, 해당 맵을 기준으로 두가지 다익스트라 알고리즘(하나는 정방향, 하나는 역방향)을 만들려고 했다가, 데이터 자체를 반전시키는 편이 훨씬 간편하다는 것을 깨닫고 선회했다. 문제 풀이는 간단하다. 1. 정방향에 따른 방문체크배열, 인접리스트, 최소비용행렬을 선언한다. 2. 역방향도 마찬가지로 만들어 준다. 3. 정방향과 역방향 각각에 따른 최소비용행렬을 둘다 계산한 다음, 정향향,역방향 비용의 합 중 최대비용인 놈을 찾으면 끝 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터..
BOJ. 11780번. 플로이드 2 플로이드 1에 이어서 플로이드 2 문제도 풀어보았다. 1번이랑 다른 점은, 플로이드 워셜을 돌면서 바뀌는 내용들을 저장해야 된다는 것이다. 나는 ArrayList 배열을 선언해서, 최소비용이 갱신이 될 때마다 이를 저장하도록 만들었다. 그리고 마지막에 배열의 각 지점들을 돌면서 저장된 리스트 내용들을 출력하면 끝! www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net package week_11; import java.io.BufferedReader; impo..
BOJ. 20061번. 모노미노도미노 2 구현 순서에 주의해서 풀면 그리 어렵지 않게 해결할 수 있다. 이전에는 구현문제에 애를 많이 먹었는데, 한두어달 문제를 조금씩 풀다보니 조금씩 익숙해지고 있는 중인 것 같다. 나는 초록색 구역과 파란색구역을 따로 나누지 않고, 초록색 테이블을 대각선으로 반전시키면 파란색과 초록색 테이블이 동일해진다는 아이디어를 가지고, 두가지 구역을 같은 로직으로 처리했다. www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net import java.io.Buffered..
BOJ. 1600번. 말이 되고픈 원숭이 말이 되고픈 원숭이... 나를 보는 것 같다^^. 이 문제는 일반적인 BFS를 하되, 1. 평범하게 상하좌우로 움직일 수 도 있고 / 2. 말로 움직일 수 도 있다. 따라서 방문체크를 할 때, 당시의 말의 움직인 횟수가 영향을 미치기 때문에 차원을 3차원으로 늘려서 케이스를 나눠 생각해야 한다. 이 아이디어만 생각해낸다면 쉬운 BFS문제이다. www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net import java.io.BufferedReader..
BOJ. 16637번. 괄호 추가하기 이 문제를 처음에 접근할 때, 하나의 배열로 인덱스를 모두 관리하려고 했었는데 그게 쉽지 않았다. 따라서 number와 operation에 대한 배열 두개로 나눠서 풀었는데 훨씬 인덱스 관리가 편리해졌다. 1. 기본적인 아이디어는 dfs이다 2. 각 재귀호출 시 마다, operation의 인덱스를 하나씩 키워가면서 계산한다. 3. 이때 계산은 괄호를 추가하는 경우, 추가하지 않는 경우로 나누며 3-1. 괄호 추가하는 않는(필요없는) 경우 : 그대로 연산한 결과를 다음 연산자에게 넘겨준다. 3-2. 괄호 추가하는 경우: 다음연산자를 먼저 계산하고, 다다음 연산자에게 넘겨준다. www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 ..
BOJ. 2638번. 치즈 어디서 이렇게 비슷하게 생긴 문제들이 계속 나타나는지 모르겠다ㅎㅎ 단순한 BFS문제다. 다만 내부에 공기층이 생긴 경우 이를 따로 처리해 주어야 한다. 나는 거꿀로 외부에서부터 BFS탐색을 돌면서 외부 공기층을 2로 바꾸고, 이 외부 공기층( 2 )와 2면 이상 인접한 치즈들을 녹여주었다. www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net package week9; import java.io.BufferedReader; import java.io.IO..
BOJ. 11559번. Puyo Puyo 이 문제 덕에 구현실력을 확실히 늘릴수 있게 되었던 것 같다. 대략 2달 전쯤 풀었었는데, 삼성 SW역량테스트를 준비하다가 생각이 나서 다시 훑어본다는 느낌으로 끄적이게 되었다. 1. 빈칸이 아닌, 색상이 있는 칸을 만나면 BFS를 돈다. -> 리스트에 별도로 저장해 둔다. 2. 해당 리스트안의 요소가 4개 이상이면 터트린다 -> 이후 리스트 초기화! 3. 한개개도 못터트리면 그대로 while 문 종료. 아니라면 ans+1하고 계속 진행. www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록,..
BOJ. 17143번. 낚시왕 이전 방식과는 다르게 풀어보려고 했다가,, 머리가 굳어서인지 된통 당했다. 1. 낚시꾼을 한칸씩 움직인다. 2. 상어들을 움직인다. 3. 한놈씩 잡아낸다. 상어를 움직일 때 좌표변환만 유의하면 특별히 어렵지 않은 문제이다. www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..
BOJ. 19236번. 청소년상어 청소년 상어 문제는 그래도 그렇저럭 풀만했다...... 아닌가.....;;;; 물고기의 움직임 각각의 상태마다 상어가 움직이면서 그 map의 상태를 들고 다녀야 한다. 그 점만 유의해서 풀면 잘...해결할 수 있다...... www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net package week8; import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..

티스토리툴바