본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘 문제풀이 스킬] 자바로 알파벳을 배열 인덱스로 변환하기 서론 알고리즘 PS 를 하다보면 알파벳을 인덱스로 변환해야하는 일이 종종 생긴다. 이를테면 백준 1316번 그룹 단어 체커 백준 10809번 알파벳 찾기 등등 이외에도 코딩테스트에서도 간간히 이와 비슷한 유형의 문제들에서 알파벳을 배열의 인덱스로 변환 하는 문제들이 몇가지 존재한다. 오늘은 그 문제들을 해결하기 위해서 알파벳을 배열의 인덱스로 변환하는 방법에 대해서 알아보려 한다. 알파벳을 배열의 인덱스로 변환하기 알파벳을 배열의 인덱스로 변환한다는 말은 다음과 같다. 알파벳은 총 26개의 문자가 존재한다. 그럼 이를 배열로 바꾼다면 a 는 0 번째 인덱스로 b 는 1번째 인덱스로 ... z 는 25 인덱스로 위치할 것이다. 이러한 것을 바로 배열의 인덱스로 알파벳을 변환한다고 한다. 이것을 코드로 봐보.. 2022. 3. 19.

[알고리즘 PS] 백준 15729번 방탈출 자바 문제풀이 문제 해당 포스팅은 백준의 백준 15729 방탈출 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 Greedy 알고리즘으로 해결할 수 있다. 우선 2가지의 불을 나눠서 생각할 수 있는데 불이 모두 꺼진 상태 -> starts 원하는 불이 켜진 완성 상태 -> ends 문제 해결 컨셉은 starts 에서 배열 원소 하나씩 돌며 ends 배열과 다른 인덱스가 있다면.. 2021. 12. 8.

[알고리즘 PS] 백준 1946번 신입 사원 자바 문제풀이 문제 해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 Greedy 알고리즘을 이용해서 해결할 수 있는 문제이다. Greedy 알고리즘의 특성답게 핵심 아이디어가 중요한 문제같다. 해결법 만약 서류 점수던 면접이던 하나라도 1등에게 떨어지면 그 인원.. 2021. 8. 19.

[알고리즘 PS] 백준 2206번 벽 부수고 이동하기 자바 문제풀이 문제 해당 포스팅은 백준의 2206번 벽 부수고 이동하기 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 최단 거리라 BFS로 해결할 수 있는 문제이다. 지금까지 해결했던 BFS 에서는 제일 이해가 힘들었던 문제다. 처음은 브루트포스로 벽을 뚫고 bfs 를 수행했는데 계속해서 시간초과가 .. 2021. 8. 15.

[알고리즘 PS] 2589번 보물섬 자바 문제풀이 문제 해당 포스팅은 백준의 2589번 보물섬 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 BFS 로 해결할 수 있는 문제였다. 골드 5라고 하는데 막상 풀면 실버 1? 정도 느낌의 문제였다. 해결법 각각 배열을 돌며 L일 때 BFS 로 갈 수 있는 최대 길이를 매번 갱신해주면 된다. 주의해야할 점이 .. 2021. 8. 14.

[알고리즘 PS] 백준 9019번 DSLR 자바 문제풀이 문제 해당 포스팅은 백준의 9019번 DSLR 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 BFS 로 해결할 수 있는 재미있는 문제이다. 이 문제를 풀기 위해서 거의 3시간은 쏟았는데.. 계속해서 시간 초과 났던 문제다 ㅠㅠ 해결법 1 ~ 1만 까지 숫자가 존재할 때, 4가지 연산을 .. 2021. 8. 13.

이전 1 2 3 4 ··· 25 다음

티스토리툴바