Algorithm (117) 썸네일형 리스트형 [백준] JAVA - 10157.자리배정 package com.java.algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * K 1억까지 -> 5 ≤ C, R ≤ 1,000 1억까지안돈다 * */ public class Baekjoon_10157_자리배정 { static int[][] map; static boolean[][] visited; static int[] dr = {1,0,-1,0}; // 아래 오른 위 왼 static int[] dc = {0,1,0,-1}; // 아래 오른 위 왼 public static void main(String[] args) throws IOException { Bu.. [백준] JAVA - 2491.수열 생각 증가하는 수열 또는 감소하는 수열 중 가잔 긴 부분의 길이를 구하는 문제입니다. 증가하는 수열과 감소하는 수열 두가지로 나누어 풀었습니다. N이 최대 100,000 이기 때문에 반복문을 중복해서 쓰지 않고, 직전값과 현재 값을 비교하기 위해 Stack 자료구조를 사용했습니다. 증가하는 수열에서 가장 긴 부분을 찾을때 1. 스택이 비어있으면 값을 넣어줍니다. 2. 스택이 비어있지 않다면 스택의 peek 값과 현재 값을 비교하여 현재 값이 더 크다면 스택에 넣어줍니다. 3. 스택이 비어있지 않고 스택의 peek 값 > 현재값 이라면 현재까지 쌓인 스택의 길이를 확인하여 maxLength에 갱신해줍니다. 그 다음 스택을 비워준다음 현재값을 다시 넣습니다. 4. 반복문을 모두 돈다음 스택의 길이를 maxL.. [백준] JAVA - 2477.참외밭 생각 처음엔 방향을 고려하지 않고 큰 직사각형에서 작은 직사각형을 빼서 넓이를 구하자고 생각했습니다. 현재 방향인 dir[i] 와 dir[(i+2)%6]이 같다면 dir[(i+1)%6]이 방향값에 따라 작은 직사각형의 가로나 세로일것이다라고 구현했습니다. 하지만 이러한 방식은 참외밭이 회전할 경우에는 작은 직사각형의 가로나 세로를 구할수가없습니다. 따라서 꺾인 부분을 체크할때 직전 방향값과 다음방향값이 같을때 현재 길이값이 작은 직사각형의 가로or세로입니다. int beforeDir = (i+5)%6; int nextDir = (i+1)%6; if(dir[beforeDir] == dir[nextDir]) { //직전 방향과 다음방향값이 같을때 i가 작은 직사각형의 가로 or 세로 } 이러한 방향 특징을 .. [백준] JAVA - 2304.창고 다각형 생각 주어진 기둥에서 가장 큰 높이가 천막을 치는것을 결정하므로 왼쪽부터 시작하는 포인터와 오른쪽부터 시작하는 포인터를 잡아서 서로 좁혀지는 모양으로 영역을 구하자고 생각했습니다. 영역을 구하기 쉽게 정수 x 좌표를 담고 있는 배열을 생성하고 주어진 입력값에 해당하는 높이값을 넣어줬습니다. 이렇게 하면 하나의 막대 영역을 차례대로 더해줘서 계산할때 편리합니다. (이전 알고리즘 스터디때 풀었던 백준 14719 빗물도 이런 방법으로 영역을 구하면 쉽게 구할 수 있습니다!!) 가장 왼쪽의 x좌표값을 구하기 위해 x좌표의 최소값을 구해줍니다. 동일한 방법으로 가장 오른쪽의 x좌표값은 x좌표의 최대값을 찾아주면 됩니다. 그 다음으로 가장 높은 높이를 가진 x좌표를 구하기 위해서 반복문을 돌면서 h[maxIdx] .. [백준] Python - 1713.후보 추천하기 생각 처음에 Java의 Colletions.sort에서 람다를 사용하여 정렬 기준을 추천순,시간순으로 넣어 구현했지만 계속 틀리고 새벽까지 디버깅하다가 지쳐서 파이썬으로 20분만에 구현했습니다ㅠ0ㅠ (이번주 스터디때 Java로 구현한 친구들에게 배워야겠습니다ㅠㅠ) 사진틀을 담을 데이터 타입을 딕셔너리로 주고 value 를 [추천순,들어온시간] 인 list로 주었습니다. 이렇게 해야 딕셔너리 정렬 기준을 람다로 넣어줄때 간단하게 정의할수있습니다. 만약 여기서 value를 튜플 (추천순, 들어온시간) 이런식으로 넣어주면 튜플은 값 변경이 불가능하기 때문에 추천순을 증가시킬수가 없기때문에 리스트 타입을 써야합니다! 사진틀에 이미 걸려있으면 추천수를 증가시켜줍니다. 사진틀에 없을때 사진틀이 비어있다면 추천받은 .. [백준] JAVA - 1920.수 찾기 생각 N,M이 모두 10만이기 때문에 단순히 이중포문으로 문제를 풀면 100억이 나오게 됩니다. 따라서 logN 정도의 시간복잡도를 가지게끔 낮춰야합니다. logN의 시간복잡도를 가지는 이진탐색으로 문제를 풀었습니다. (한번 비교가 일어날때마다 리스트가 반씩 줄어들기 때문에 logN의 시간복잡도를 가집니다.) M개의 배열을 돌면서 각각의 원소들이 주어진 배열안에서 존재하는지 찾아야하므로 총 시간 복잡도는 MlogN을 가지게 됩니다. 이진탐색을 구현할때 먼저 찾으려는 배열은 정렬되어있어야 하기 때문에 origin 배열을 Array.sort를 사용하여 정렬했습니다. 그 다음, 배열의 중간값을 설정하고 중간보다 작은 값이면 왼쪽을 탐색하고 큰 값이라면 오른쪽을 탐색하는 반복문을 통해 이진탐색을 구현했습니다. .. [백준] JAVA - 14889.스타트와 링크 생각 예제에서는 N=4이고 한 팀당 2명이기 때문에 (1,2)이 한팀이고 (3,4)이 나머지 팀일때 능력치의 차이를 (S12+S21), (S34+S43)의 차이로 구했습니다. 만약 한 팀당 인원이 3명이상일땐, 예를 들어 (1,2,3)인 경우일때 팀의 능력치의 차이를 계산할땐 (S12 + S21 + S13 + S31 + S23 + S32) 와 같이 계산해줘야 합니다. N개를 N/2로 각각 두 팀으로 나눕니다. 나눌수있는 모든 가능한 경우를 조합으로 뽑았습니다. teamA와 teamB 정수형 배열을 만든다음 teamA에서 N/2만큼 조합으로 뽑았습니다. 그 다음으로 teamA에서 뽑히지 않은 번호들만 체크하여 teamB에 넣었습니다. (선택된 원소를 제외한 나머지 원소를 추출하는 더 좋은 방법이 있을것 같.. [백준] JAVA - 1339.단어 수학 생각 주어진 입력에서 중복되는 알파벳을 제거하고 알파벳으로 순열을 만든다음, 이 알파벳을 0~9 로 치환하여 입력 알파벳들의 합이 최대가 되는 알파벳 순열을 찾는 문제입니다. 이 문제에서는 알파벳이 최대 10개이기 때문에 순열을 사용해서 풀수있습니다. 비트마스킹을 사용한 순열생성 코드를 만든 다음 내부에서 알파벳을 숫자로 치환하고 누적합을 계산해줬습니다. 알파벳을 숫자로 치환할때 Key = 알파벳, Value = 숫자인 HashMap을 만든다음 가장 큰 수(9,8,7,...) 부터 왼쪽에 할당했습니다. 이렇게 숫자를 줘야만 최대합을 찾을수있습니다. HashMap에서 Key 타입을 Character로 정의했기때문에 알파벳의 합을 계산할때 charcter배열을 String으로 한번 치환한다음 마지막으로 정수.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 15 다음
