본문 바로가기

분류 전체보기

 (308)
백준 1212 8진수 2진수 (JAVA) 문제 https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main{ public static void main(String[] args) throws IOException { StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputStre..
[백준] 2493 탑(JAVA) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 코드 import java.io.*; import java.util.Stack; import java.util.StringTokenizer; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..
[백준] 2580 스도쿠 (JAVA) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 문제 자체가 어렵지는 않으나 풀이방법에 대해서 조금 고민을 하여 푼 문제이다. 스도쿠의 룰은 잘 알다시피 가로세로 그리고 3*3이 되어있는 칸에서 중복을 허용하지 않는 선에서 수를 채워넣는 것이다. 그리하여 나는 81칸 전부를 차례대로 순회하며 만약 빈칸이 있다면 해당 칸에 들어갈수 있는 수를 찾은뒤 arr에 집어넣고 재귀적으로 호출해 나가며 풀이를 진행했다. 여기서 살짝 헷갈릴는 점은 적정..
[기타/알고리즘] 서로 다른 색의 두 점의 쌍 구하기(컨벡스 헐) 해당 문제는 학교 과제로 받은 문제이다. 문제의 요지는 빨간색점과 파란색점이 서로 교차하지않고 선을 그어야 한다. 처음에는 어떻게 해야할지 몰라 이리 저리 고민하다 컨벡스 헐 알고리즘이란 것을 발견하여 포스팅 하고자 여기에 쓴다. 이 문제는 최외곽의 점을 찾아 해당 점에서 반시계방향(시계방향으로 하여도 상관없음)회전하며 선을 차례대로 그었을때 해당 선에 의해서 나누어 지는 면에 속하는 파란색 점과 빨간색 점의 수를 동일하다면 그 때 선을 그어주고 분할정복기법을 이용해서 왼쪽 영역과 오른쪽 영역으로 나누어 각각 다시 분할정복을 수행해준다. import java.io.*; import java.nio.charset.StandardCharsets; import java.util.Arrays; import ja..
[백준] 18870 좌표 압축 (JAVA) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 해당 문제는 가만히 보면 그냥 정렬하였을경우 해당 인덱스의 수보다 작은 수가 몇개가 있냐는 말과 같다. 그렇기 나는 기존 입력값이 들어가있는 origin배열과 정렬되어있는 sort배열 마지막으로 map을 만들어주었다. 우선 처음으로는 입력값을 origin배열과 sort배열에 입력을 받고 Arrays.sort메소드를 이용해 sort를 정렬해준다..
[백준] 11723 집합(java) https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 해당 문제는 기본적인 set에 대해서 물어보는 문제이다. 문제에서 입력값을 주는대로 구현하는되는 문제라서 크게 어렵지는 않을것이라고 생각된다. 자세한거는 코드를 보면 이해가 갈것이다. 필자는 두가지 방식으로 구현했는데 우선 첫번째 코드는 try catch를 이용해 오류가 날경우 처리를 해 코드의 반복을 줄인것이고 두번째 코드는 값의 할당을 switch문 내부를 타고 들어갔을 경우 할당하는 방식을 이용해 오류를 처리한것이다. 이..
[백준] 2630 색종이 만들기(JAVA) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 필자는 문제를 처음보고 분할 정복과 재귀를 이용하면 쉽게 풀릴것 같다는 생각을 하였다. 이번에는 두개의 코드를 포스팅 할것이다. 우선 첫번째 코드는 내가 짠 코드이고 두번째는 다른 사람들이 짠 코드이다. 첫번째 코드는 우선 처음 메소드에 들어가면 해당사이즈 만큼의 색종이가 하나의 색으로 되어있는지 확인하고 만약 여기서 하나의 색으로만 되어있으면 그자리에서 바로 함수..
[백준] 2606 바이러스 (JAVA) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 이 문제는 그래프를 그리고 DFS혹은 BFS중 원하는것으로 하나를 선택해 탐색해 방문한 노드의 개수를 구하면된다. 나는 여기서 ArrayList속 ArrayList를 넣어 인접연결리스트를 구현하여 그래프를 구성했다. 그리고 만들어지 그래프에서 (1에서 시작하여) 현재위치의 노드에서 인접한 노드들의 번호를 큐에 넣는다. 그리고 큐에서 차례대로 뽑아서 만약 방문하지 않았다면 방문처리를 하고 위의 작업..
[프로그래머스] 로또의 최고순위와 최저순위 (JAVA) https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 이 문제는 그렇게 어려울것이 없는 문제다 문제를 요약하자면 비어있는수를 통해 당첨될수있는 가장 높은등수와 가장 낮은 등수를 구하면 된다. 즉 가장 높은등수는 0이 전부 당첨된 수라는것이고 가장 낮은 등수는 0이 전부 당첨되지 않은 등수라는 것이다. 그리 어려운 문제가 아니니 코드를 보면 금방 이해가 될것이다. ..
[백준] 1927 최소 힙 (JAVA) https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 이 문제는 힙을 이용해 구현하면 되는 문제로 나는 자바를 이용하기 때문 힙을 이용해 구현하였다. 풀이 방법은 문제에서 시킨대로 맨 처음 입력받느 N만큼 입력을 받고 이 때 만약 입력받은 값이 0이라면 힙에서 우선순위가 가장 높은 수를 뽑아서 출력하면 된다. 만약 힙이 비어있다면 0을 출력한다. 그리고 0이 아닌 임의의 수가 입력된다면 힙에 추가한다. import java...

티스토리툴바