알고리즘
1.[백준] 2292번 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다.
2.[백준] 1193번 분수찾기
나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
3.[백준] 2869번 달팽이는 올라가고 싶다
하루 동안 달팽이가 올라간 거리를 up, 내려가는 거리를 down, 총 올라가야하는 거리를 v라고 한다. 이 때 아침에 up만큼 올라가서 꼭대기에 도달한다면 밤의 down은 계산하지 않아도 된다. 이 부분이 핵심이다. 따라서 처음 계산을 할 때 v에서 up만큼 빼주고
4.[백준] 10757번 큰 수 A + B
문제에서 제시하는 수의 범위((0 < A,B < 10^10000)는 일반적으로 큰 수를 표현할 때 사용하는 long 자료형(2^64)보다 훨씬 크기 때문에 단순히 덧셈 연산으로는 풀 수 없다. 자바 라이브러리를 사용해서 이럴 때 사용하는 자료형 또는 클래스가
5.[백준] 1978번 소수 찾기
많이 익숙한 소수를 구하는 문제이다. 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다. 이러한 소수를 구하기 위해 가장 간단한 방법은 입력값 n보다 작은 수로 일일히 나눠보는 것이다. 이 때 이 나누는 값의 범위를 $$\\sqrt{n}$$ 까
6.[백준] 2581번 소수
직전에 풀었던 소수 찾기 문제에서 사용했던 방법을 적용하면 간단하게 풀 수 있다. 함수는 그대로 가져와 사용했다.
7.[백준] 1929번 소수 구하기
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 소수를 구할 범위만큼의 배열을 생성하고 그 안에서 합성수들을 찾아내 제거해나가는 식으로 구현할 수 있다.아래는 1부터 n까지의 수들이 소수인지 아닌지 판별하는 배열을 만드는 코드이다. i를 n의 제
8.[백준] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6
이번 문제는 코드는 간단하지만 수들의 패턴을 찾고 공식화 하는 것 때문에 애를 먹었다. 다른 블로그들에서는 코드에 사용하는 식만 딱 나와있고 그에 관한 설명은 충분히 되어있지 않거나 납득이 가지 않아, 예전에 배웠던 수학을 간신히 되새겨가며 설명해보았다.
9.[SWEA][1859] 백만 장자 프로젝트
문제링크데이터를 뒤에서부터 읽으면 쉽다. 먼저 맨 뒤의 숫자를 MAX 값으로 설정한다. 앞 인덱스의 숫자보다 크면 그 차이값을 SUM에 더하고, 작으면 그 앞의 숫자를 MAX로 한다. 이를 데이터 배열 맨 뒤부터 앞까지 수행해주면 된다.
10.[백준] 28116번 선택 정렬의 이동 거리
문제 링크스터디에서 각자 진도에 맞는 알고리즘 문제를 풀기로 했는데 재밌어 보여서 고르게 되었다. 그러나 단순한 선택 정렬 알고리즘과는 다르게 생각보다 많은 시간을 투자했다. 아직 문제 풀이에 경험이 부족한 것 같다.기능적인 구현 자체는 어렵지 않았지만 널리 알려진 선
11.[백준] 23883번 알고리즘 수업 - 선택 정렬 3
문제 링크N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구하자.처음에 문제를 제대로 읽지 않고, 이전에 풀었던 28116번 방법을 적용하려다가 낭패를 겪었다. 28116번 문제는 수열 A는 무
12.[백준] 4779번 칸토어 집합
문제 링크재귀를 이용해서 칸토어 집합의 근사를 만들어야 하는 문제다. 이 때 전체 집합이 유한이라고 가정한다.(칸토어 집합에 대해서 유튜브 영상도 보고 블로그도 훑어봤지만 아직 명확하게 이해하지 못했다. 나중에 다시 보려고 한다.)$n^3$개의 '-'로 이루어진 문자열
13.[백준] 17478번 재귀함수가 뭔가요?
https://www.acmicpc.net/problem/status/17478/1002/1언뜻 봤을 때 복잡해보이지만 규칙이 있다.제일 먼저 첫 번째 문장은 한 번만 출력된다.그리고 재귀 때마다 4줄의 문장이 반복된다.재귀의 마지막에는 두 개의 문장을 출력하
14.[백준] 16678번 모독
https://www.acmicpc.net/problem/16678왕은 단 1번의 "Defile" 프로젝트 실행을 통해 모든 국회의원을 없애려고 한다. 프로젝트 내용은 다음과 같다.프로젝트를 한 번만 수행하기 위해서는 명예 점수들을 오름차순으로 정렬했을 때 이
15.[프로그래머스] 베스트앨범
처음으로 프로그래머스 문제를 풀어보았다. 확실히 입출력 면에서는 백준보다 편한 것 같다. 프로그래머스 사이트에서 다른 사람들의 풀이를 봤는데 굉장히 화려하고 복잡해보였다. 백준처럼 실행시간 기준으로 볼 수 있으면 좋겠다는 생각이 들었다.어쨌든 로직 자체를 생각하는 것은
16.[프로그래머스] 게임 맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844
17.[프로그래머스] 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163
18.[프로그래머스] 소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839숫자 카드로 만들 수 있는 모든 경우의 수를 찾기 위해 DFS를, 결과의 중복 제거를 위해 Set 자료형을 사용했다.나 같은 경우 자릿수 별로 숫자
19.[프로그래머스] 여행 경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164DFS와 백트래킹을 사용했다. 출발지가 departure인 티켓을 찾고서 다음 경로를 탐색한다. 하나의 경로가 완성되면 재귀 스택이 종료되며 방문
20.[프로그래머스] 피로도
https://school.programmers.co.kr/learn/courses/30/lessons/87946백트래킹과 DFS를 사용해서 모든 경우의 수를 탐색한다. 던전에 방문할 때마다 최소 필요 피로도를 체크하고 소모 피로도만큼 차감시킨다. 한 번의 경
21.[프로그래머스] 퍼즐 조각 채우기
https://school.programmers.co.kr/learn/courses/30/lessons/84021BFS/DFS 카테고리로 분류되는 문제이기는 하지만 다른 로직이 핵심이 되는 문제였다. 참고로 위 코드에서는 BFS와 DFS 모두 구현해두었다.문제
22.[백준] 1719번 택배
https://www.acmicpc.net/problem/1719다익스트라 알고리즘을 수행하면 특정 노드의 부모 노드를 알 수 있다. 위 이미지에서 1을 출발점으로 삼는다고 할 때 4까지의 최단 경로는 1-2-4이다. 이 때 4의 부모는 2, 2의 부모는 1이
23.[백준] 2665번 미로만들기
BFS + 다익스트라를 활용하여 풀었다.BFS를 사용하여 모든 경로를 탐색하면서 검은 방을 만날 때마다 흰 방으로의 변경 횟수를 1 증가시킨다. 만약 이동하려는 좌표가 현재 위치까지의 이동거리보다 작으면 경로를 갱신하지 않는다. (다익스트라)
24.[백준] 13549번 숨바꼭질 3
https://www.acmicpc.net/problem/13549하나의 노드에서는 세 개의 노드(x-1, x+1, x2)로 이동할 수 있다. x-1, x+1 노드로 움직이려면 1초 걸리고 x2 노드로 이동할 때에는 0초가 걸린다. 이 때 임의의 숫자 n을 만
25.[백준] 1504번 특정한 최단 경로
start부터 end까지의 최단 경로를 구하되, 두 개의 정점 v1, v2를 반드시 거쳐야 한다. 따라서 구해야 하는 경로는 두 가지다.1) start -> v1 -> v2 -> end2) sta
26.[백준] 1541번 잃어버린 괄호
식을 가장 작은 수로 만들기 위해서는 최대한 많은 수를 더하고 앞에 "-" 연산자를 붙여서 음수로 만들어야 한다. 이를 위해 "-"를 기준으로 식을 분리한다."-"를 기준으로 나뉘어진 문자열들은
27.[프로그래머스] 조이스틱
이 문제의 핵심을 정리하자면 다음과 같다.어떤 위치의 문자가 A가 아니라면 반드시 방문해야 한다. 즉, 문자가 A인 위치는 생략해도 된다.조이스틱을
28.[백준] 2629번 양팔저울
추를 놓는 경우의 수는 3개다. 구슬 쪽 저울에 올릴 것인지, 반대편 저울에 올린 것인지, 아예 사용하지 않을 것인지. 따라서 이 모든 경우의 수를 따져보고 구슬 무게를 만들 수 있는지 확인해야 한다. 그러나 이대로 구현하면 경우의 수가 매우 많아 시간 초과가 발생할
29.[프로그래머스] 등굣길
좌표상에서 오른쪽과 아래쪽으로만 움직이기 때문에 특정 위치에 도달했을 때의 경로는 항상 최단경로다. 따라서 우리는 학교까지의 모든 경로 개수를 구하
30.[프로그래머스] 아이템 줍기
여러 개의 직사각형으로 이루어진 도형을 2차원 배열에서 표현할 때 테두리 부분(도형의 가장 바깥쪽)은 1로, 나머지 안쪽 부분은 2씩 더해준다. 입
31.[프로그래머스] 호텔 방 배정
전체 방 개수가 10^12개 이므로 배열을 이용해 모든 방을 나타낼 경우 메모리가 부족하게 된다. 때문에 HashMap 등의 자료구조를 이용해 필요
32.[프로그래머스] 두 정수 사이의 합, 짝수의 합
두 정수 사이의 합짝수의 합위의 두 문제 모두 등차수열의 합 공식을 사용해 간단하게 풀 수 있다.매개변수로 주어지는 두 정수 a, b 중 어떤 수가 더 큰지 모르기 때문에 삼항연산자 또는 Math.min(), Math.max() 메소드를 활용해 대소관계를 정한다. 이후
33.[프로그래머스] 문자열 내림차순으로 배치하기
문자열 내림차순으로 배치하기ascii 값을 기준으로 비교하면 되니 char 배열로 변환하는건 잘 생각했으면서, 왜 StringBuilder로 변환해서 뒤집는건 생각을 못 했을까... (char 타입의 배열인 경우, Collections.reverseOrder()은 타입
34.[프로그래머스] 부족한 금액 계산하기
부족한 금액 계산하기공식 세우고 이를 구현하는건 바로 했다. 근데 테스트 케이스 4개 정도에서 자꾸 찐빠가 나는게 아닌가... 이런건 대부분 데이터가 자료형 범위를 넘어서 오버플로우가 발생하는 경우였다.원래 코드는 이거였다. 만약 price \* ...의 값이 int