자료구조 & 알고리즘 & cs/CodingTest (67) 썸네일형 리스트형 [java/python] 4963 - 섬의 개수 4963번: 섬의 개수 (acmicpc.net) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이제까지 배웠던 알고리즘을 복습하며 파이썬과 자바로 풀어보고 있다. 기존에 풀어봤던 dfs/bfs 랑은 좀 다르게 이 문제는 대각선으로도 이동을 한다. 그외엔 어려운 점이 없었다. 물론 파이썬은.. 그러나 자바는 아직 예상치 못하게 마주하는 난관들이 있는데 아직 코테 문법이 익숙하지 않은 탓인 것 같다. 그래서 정리해보려고 한다. 우선 파이썬 코드는 다음과 같다. [Python] # 4963 섬의 개수 imp.. [TIL] 그래프 - BFS/DFS (java) 파이썬으로 공부했던 알고리즘을 java로도 공부중이다. 파이썬의 간편한 문법에 익숙해져 있어서 java로 하니까 좀 헷갈리지만 알고리즘은 구현방법은 비슷하기 때문에 정리해보려고 한다. 백준의 그래프 문제(1260번: DFS와 BFS (acmicpc.net))로 연습하였다. 코드는 아래와 같다. package graph_bfs_dfs; import java.util.*; import java.io.*; public class Aug5Week_1260_Ssi { //두개의 그래프를 출력해야 하기 때문에 변수 선언 public static ArrayList[] graph; public static boolean[] visited; //재귀를 활용한 dfs public static void dfs(int v){.. [python] 1374 - 강의실 1374번: 강의실 (acmicpc.net) 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 전에 프로그래머스에서 비슷한 문제를 풀어봤는데 다시 풀어보려니 또 헷갈려서 정리를 해보려고 한다. 우선 이 문제는 우선순위 큐를 사용하여 쉽게 풀 수 있다. 최대한 많은 강의를 최대한 적은 수의 강의실을 사용하여야 하므로 그리디에 속한다고 볼 수도 있을 것 같다. 문제를 풀기 위해 고려해야 하는 것은 다음과 같다. 1. 여기서 강의번호는 무시해도 좋다. 2. 강의 시작 시간과 종료 시간을 묶어서 우선순위.. [python] 2014 - 소수의 곱 2014번: 소수의 곱 (acmicpc.net) 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 우선순위 큐를 해결하는 문제였다. 처음 내가 생각한 풀이는 다음과 같았다. 1. 중복조합으로 소수의 곱을 계산하여 리스트에 넣는다. 2. 힙 정렬 후 heap을 n번 반복하여 n번째 위치한 값을 구한다. 그런데 착각한 것이 주어진 소수를 곱해나가면 무한히 가능하기 때문에 중복조합으로 계산을 하면 안됐다..! 심지어 중복조합 후 구한 값을 prod를 사용해 누적합을 구해서 계산했다. 결과는.. [python] 1051- 숫자 정사각형 1051번: 숫자 정사각형 (acmicpc.net) 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 완전 탐색으로 해결하였다. 처음에는 테스트케이스를 다 통과했는데도 통과하지 못해서 고민하다가 반례를 찾아보았다. 질문 게시판에서 너무 웃긴 반례를 발견하고 적용해본 후 문제점을 알 수 있었다. 정사각형 판별 함수에서 모든 조건을 검색한 후 max 값을 return 해야 하는데 정사각형을 찾자마자 return 해버려서 답이 틀렸던 거였다. 테케는 오묘하게 그런 반례들을 확인할 수가 없었다. 이런 경우들이 부쩍 많.. [python] 1527 - 금민수의 개수 1527번: 금민수의 개수 (acmicpc.net) 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 자체는..간단하지만 백퍼 시간초과 걸리겠다 생각한 문제였다. 첫 접근방식은 범위내의 모든 수를 검사했더니 역시나 시간초과가 떴고 다른 접근 방법으로 문제를 풀이하였다. 범위가 넓기 때문에 모든 수를 검사하기 보다 자릿수를 계산하여 4와 7만 들어간 수들의 리스트를 생성한다. 그리고 그 수들이 주어진 a와 b의 범위내에 들어가는 수인지를 판단한다. 역으로 생각하면 검사해야 할 데이터가 확 줄어들기 때문에 .. [python] 프로그래머스 Lv2. - 귤 고르기 코딩테스트 연습 - 귤 고르기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제를 보고 든 생각은 조합을 이용해 풀면 되지 않나? 였으나.. 그렇게 쉽게 풀릴리가 없지. 테케는 다 통과하지만 바로 시간초과에 걸려버렸다. [처음 코드] from itertools import combinations def solution(k, tangerine) answer=100001 for com in combinations(tangerine, k): x=set(com) if answer > len(x): .. [python] 8979- 올림픽 8979번: 올림픽 (acmicpc.net) 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 간단하다고 생각했는데 서브태스크 때문에 상당히 애먹었다.. 예제는 다 통과했더라도 여러개의 테스트케이스를 찾고 확인해봐야 할 문제같다. 난이도는 높지 않지만 꼼꼼함을 요구하는 기업 코테 문제와 비슷한 것 같았다. 여러번 시도의 흔적.. 문제가 됐던 부분은 동일 등수가 있을 경우와 모든 국가의 메달 수가 0인 경우이다. 첫 번째 예제와 같이 동일 등수가 존재할 때 4개의 국가 중 두개의 국가가 2등.. 이전 1 2 3 4 ··· 9 다음
