코딩 정복 가즈아~

(っ◔◡◔)っ ♥ 2021 취뽀하자!! ♥

알고리즘 풀이/백준

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net - key를 name으로 가지는 Map을 만들어 준다. value는 포켓몬 번호 - 입력한 값이 문자인 경우, map에서 포켓몬 이름으로 조회 한다. 입력한 값이 숫자인 경우, 배열 index로 빠르게 접근하기 위해, 배열도 하나 만들어 준다. - 찾은 것을 바로 바로 출력하게 되면, 오버 헤드가 쌓여 성능저하가 발생하게 된다. (시간이 매우 오래걸림 ㅠ) String..

2021. 8. 4.

알고리즘 풀이/백준

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 핵심은 최솟값을 구하기 위해 최대한 더하여 큰 수를 빼는 것이다. 1. 마이너스(-)를 기준으로 문자열을 자른다. 2. 잘라진 문자열 속 숫자들을 다 더해주고 큐에 넣어준다. 3. 차례대로 뺀다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util...

2021. 8. 2.

알고리즘 풀이/백준

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net dp에는 두 종류가 있다. 나는 이번에 Bottom-up을 사용해서 풀어봤다. 1. Bottom-up : 반복문을 이용하여 풀이 2. Top-down : 재귀를 이용하여 풀이 - 먼저 1을 빼보고 계산을 한다. - 만약 3으로 나누어진다면, 1로 뺀것과 어느게 더 작은지 비교 - 만약 2로 나누어진다면, 1로 뺀것과 어느게 더 작은지 비교 dp[1]은 어차피 0이므로 따로 초기화 하지 않고, dp[2]부터 반복문을 돌아 dp[n]까지 찾아준다. import java.io.BufferedReader; import..

2021. 8. 2.

알고리즘 풀이/백준

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 이 문제를 풀때, 플로이드 와샬의 개념을 적용하였다. 모든 정점에서 모든 정점까지의 최단거리 플로이드 와샬은 모든 정점에서 모든 정점까지의 최단거리를 구하는 것으로 한 정점에서 모든 정점까지의 거리를 구하는 다익스트라와는 다른 개념이다. 핵심은 거쳐가는 정점을 기준으로 최단거리를 구해야 한다는 것이다!! - 인접행렬을 만들고, 자기 자신(road[i..

2021. 8. 2.

알고리즘 풀이/백준

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 하나씩 칸 수를 세었다간 시간초과가 나는 문제였다. 따라서, 몇사분면에 위치했는지를 파악하여 거쳐온 사분면의 숫자 만큼을 더해주는 방식으로 풀어야 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

2021. 7. 22.

카테고리 없음

('https://jisunshine.tistory.com/79'이하 'MARS')은(는) 「개인정보 보호법」 제30조에 따라 정부주체의 개인정보를 보호하고 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다. ○ 이 개인정보처리방침은 2021년 1월 1부터 적용됩니다. 제1조(개인정보의 처리 목적) ('https://jisunshine.tistory.com/79'이하 'MARS')은(는) 다음의 목적을 위하여 개인정보를 처리합니다. 처리하고 있는 개인정보는 다음의 목적 이외의 용도로는 이용되지 않으며 이용 목적이 변경되는 겨우에는 「개인정보 보호법」 제18조에 따라 별도의 동의를 받는 등 필요한 조치를 이행할 예정입니다. 제2조(개인정보의..

2021. 5. 19.

알고리즘 풀이/백준

문제 풀이 방법 - 1~N의 부분집합을 모두 구한다. - 부분집합에 '포함된 팀' vs '포함되지 않은 팀'으로 2개의 팀으로 나누어 각각의 팀이 연결되어있는지 확인한다. - 두 팀이 유효하면, 각 팀의 점수 차이를 구하여 최솟값과 비교 후 갱신한다. 소스 코드 package com.boj.gold5; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; public class 백준_17471_게리맨더링 { static int N, matrix[][], people[], result..

2021. 3. 15.

알고리즘 풀이/백준

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 풀이 방법 - n : 회전할 톱니바퀴 번호, d : 회전 방향 - n왼쪽으로 하나씩 이동하면서 [n-j-1]번 톱니바퀴의 2번과 [n-j]번 톱니바퀴의 6번이 서로 다른 경우, 회전해야하므로 isTurn에 회전 방향을 기록해 나간다. - [n-j-1]번 톱니바퀴의 2번과 [n-j]번 톱니바퀴의 6번이 같은 경우, 더이상 회전하지 않으므로 break - 오른쪽도 왼쪽과 같은 방법으로 탐색하..

2021. 3. 14.