반응형

문제 풀이

1. 주어진 시간이 hh:mm 일 때, mm에서 45를 빼준다.

2. 1의 값이 0보다 작은 경우 mm에 60을 더해준 후, hh에서 1을 빼준다.

3. 2 이후 hh가 -1이라면 23으로 바꿔준다.

 

* 다른 풀이로는 hh를 분으로 바꿔준 후, 45를 빼서 다시 시간과 분으로 바꿔주는 방법이 있다..

(hh * 60 + mm - 45 후 60으로 나눈 몫이 시간, 나머지가 분)

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
 
def solve(hh,mm):
  mm -= 45
  if mm < 0 :
    mm += 60
    hh -= 1
    if hh >= 0:
      return hh,mm
    else :
      return 23,mm
  else :
    return hh,mm
 
if __name__=='__main__':
  hh,mm = map(int,sys.stdin.readline().split())
  nh, nm = solve(hh,mm)
  print(nh,nm)
 cs

문제 링크

 

2884번: 알람 시계

문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다. 이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1520 내리막 길  (0) 2020.10.20
백준 1152 단어의 개수  (0) 2020.08.31
백준 9465 스티커  (0) 2020.04.18
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 1002 터렛  (0) 2020.04.09
반응형

문제 풀이

a0 a1 a2 a3 a4
b0 b1 b2 b3 b4

 스티커가 위와 같이 있다고 할 때, r번 행의 c번 열 스티커를 붙였을 때의 최댓값을 dp[r][c]라 하면, dp의 점화식은 아래와 같이 쓸 수 있다.

 r=0 인 경우 : dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]

 r=1 인 경우 : dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]

 

 위의 그림에서 a3를 붙였을 경우를 예로 들면, 스티커를 앞에서부터 붙인다면 a1, b1, b2를 붙인 다음에 a3를 붙이는 경우가 가능하다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
def solution(s):
  dp = [[s[i][0]] + [0]*(len(s[0])-1) for i in range(2)]
  dp[0][1] = dp[1][0]+s[0][1]
  dp[1][1] = dp[0][0]+s[1][1]
  for i in range(2,len(s[0])):
    dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]
    dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]
  print(max(dp[0][-1],dp[1][-1]))
 
if __name__=="__main__":
  n = int(input())
  for _ in range(n):
    size = int(input())
    s = []
    for i in range(2):
      s.append(list(map(int,sys.stdin.readline().split())))
    solution(s)
 cs

Line 3 ~ 5 : Line 6의 for문으로 dp를 처리하는 과정에서 dp[r][i-2] 연산이 들어가므로 첫 번째, 두 번째 열(c=0,1)을 미리 처리해야 한다.

문제 링크

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 1002 터렛  (0) 2020.04.09
백준 11048 이동하기  (0) 2020.03.30
반응형

문제 풀이

1. 보호소에 들어올 때는 중성화가 안되어있었어야 하므로 ANIMAL_INS.SEX_UPON_INTAKE는 I로 시작해야 한다.

2. 보호소에서 나갈 때는 중성화가 되어있어야하므로 ANIMAL_OUTS.SEX_UPON_OUTCOM은 N 또는 S로 시작해야 한다.

ORACLE Code

1
2
3
4
5
6
7
8
9
10
SELECT I.ANIMAL_ID, I.ANIMAL_TYPE, I.NAME
FROM (
    SELECT ANIMAL_ID, ANIMAL_TYPE, NAME
    FROM ANIMAL_INS
    WHERE SEX_UPON_INTAKE LIKE 'I%'
) I
INNER JOIN ANIMAL_OUTS O
ON I.ANIMAL_ID = O.ANIMAL_ID
AND SUBSTR(O.SEX_UPON_OUTCOME,1,1) IN ('N','S')
ORDER BY I.ANIMAL_ID;
 cs

Line 9에서 SEX_UPON_OUTCOME 을 가공하므로 만약 해당 칼럼에 인덱스가 걸려있으면 활용할 수 없는 것이 걸린다. Line 5처럼 Like로 N과 S에 대해 구한 후 union all을 하면 더 좋을 것 같다.

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv3 추석 트래픽  (0) 2020.09.10
프로그래머스 SQL 오랜 기간 보호한 동물(1)  (0) 2020.05.23
프로그래머스 SQL 있었는데요 없었습니다  (0) 2020.04.17
프로그래머스 SQL 없어진 기록 찾기  (0) 2020.04.17
프로그래머스 Lv3 자물쇠와 열쇠  (0) 2020.04.16
반응형

문제 풀이

ANIMAL_INS의 DATETIME이 ANIMAL_OUTS의 DATETIME 보다 늦은 ANIMAL_ID를 찾아 반환하면 된다.

 

ORACLE Code

1
2
3
4
5
SELECT I.ANIMAL_ID, I.NAME
from ANIMAL_OUTS O INNER JOIN ANIMAL_INS I
on O.ANIMAL_ID = I.ANIMAL_ID
and O.DATETIME < I.DATETIME
order by I.DATETIME;
 cs

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 오랜 기간 보호한 동물(1)  (0) 2020.05.23
프로그래머스 SQL 보호소에서 중성화한 동물  (0) 2020.04.17
프로그래머스 SQL 없어진 기록 찾기  (0) 2020.04.17
프로그래머스 Lv3 자물쇠와 열쇠  (0) 2020.04.16
프로그래머스 Lv2 JadenCase 문자열 만들기  (0) 2020.03.27
반응형

문제 풀이

ANIMAL_OUTS 의 ANIMAL_ID 중 ANIMAL_INS 에 없는 것을 찾는다.

 

ORACLE Code

1
2
3
4
5
6
7
8
SELECT ANIMAL_ID, NAME
from ANIMAL_OUTS O
where not exists (
    select 'x' 
    from ANIMAL_INS I
    where O.ANIMAL_ID = I.ANIMAL_ID
)
order by ANIMAL_ID;
 cs

Line 3 : 부분범위처리를 활용하여 문제풀이의 내용을 확인

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 보호소에서 중성화한 동물  (0) 2020.04.17
프로그래머스 SQL 있었는데요 없었습니다  (0) 2020.04.17
프로그래머스 Lv3 자물쇠와 열쇠  (0) 2020.04.16
프로그래머스 Lv2 JadenCase 문자열 만들기  (0) 2020.03.27
프로그래머스 Lv2 뉴스 클러스터링  (0) 2020.03.27
반응형

2020 카카오 코딩 테스트 1차 문제

문제풀이

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

 

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

올해에도 2020이라는 멋진 숫자와 함께, 카카오의 신입 개발자 채용을 시작했습니다! 그 여정 중 첫 단계로 1차 코딩 테스트가 지난 9월 7일 토요일 오후 2시부터 오후 7시까지 5시간 동안 진행됐는데요. 저희 준비위원들도 설렘과 긴장 속에 원활한 진행을 위해 노력했고, 무사히 1차 테스트를 마칠 수 있었습니다. 테스트에는 총 7문제가 출제됐고, 응시자는 5시간 이내에 순서와 상관없이 문제를 해결해야 […]

tech.kakao.com

여기에 써있는 풀이를 그대로 구현했다.

1. 자물쇠가 N*N 행렬이라면, 3N*3N 매트릭스를 만든 후, 가운데 자물쇠를 배치한다.

2. 열쇠를 매트릭스에 올려놓고 한 칸씩 움직이며 3N*3N 행렬의 가운데가 모두 1이 되는지 확인한다.

3. 2에서 찾지 못한다면 열쇠를 90도 돌려서 다시 2 과정을 수행한다.

4. 4번 돌렸는데도(360도) 찾지 못한다면 불가능한 경우이다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int lockLen = lock.length;
        int[][] l = new int[lockLen*3][lockLen*3];
        for(int i=0;i<lockLen;i++) {
            for(int j=0;j<lockLen;j++) {
                l[i+lockLen][j+lockLen] = lock[i][j];
            }
        }
        for(int r=0; r<4;r++) {
            key=rotate(key);
            boolean check = compare(key,l);
            if(check)return true;
        }
        return false;
    }
    public int[][] rotate(int[][] key){
        int len = key.length;
        int[][] ans = new int[len][len];
        for(int i=0;i<len;i++) {
            for(int j=0;j<len;j++) {
                ans[j][len-1-i] = key[i][j];
            }
        }
        return ans;
    }
    public boolean compare(int[][] key, int[][] lock) {
        int keyLen = key.length;
        int lockLen = lock.length;
        int diff = lockLen-keyLen;
        for(int iMove=0; iMove<=diff;iMove++) {
            for(int jMove=0; jMove<=diff;jMove++) {
                int[][] tempKey = new int[lockLen][lockLen];
                for(int i=0;i<keyLen;i++) {
                    for(int j=0;j<keyLen;j++) {
                        tempKey[i+iMove][j+jMove] = key[i][j];
                    }
                }
                boolean check = check(tempKey,lock);
                if(check)return true;
            }
        }
        return false;
    }
    public boolean check(int[][] key, int[][] lock) {
        int len = lock.length/3;
        for(int i=len;i<len*2;i++) {
            for(int j=len;j<len*2;j++) {
                if(key[i][j]+lock[i][j]!=1) {
                    return false;
                }
            }
        }
        return true;
    }
}
 cs

Line 17 : 열쇠를 90도 회전시키는 함수이다.

Line 27 : 열쇠를 3N*3N 행렬에 올려놓고 한칸씩 움직이는 과정이다.

Line 45 : 열쇠와 자물쇠가 맞는지 확인하는 함수이다.

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 있었는데요 없었습니다  (0) 2020.04.17
프로그래머스 SQL 없어진 기록 찾기  (0) 2020.04.17
프로그래머스 Lv2 JadenCase 문자열 만들기  (0) 2020.03.27
프로그래머스 Lv2 뉴스 클러스터링  (0) 2020.03.27
프로그래머스 SQL 오랜 기간 보호한 동물(2)  (0) 2020.03.23
반응형

벨만 포드 알고리즘 학습을 위해 풀어본 문제이다.

문제풀이

 벨만 포드 알고리즘 문제로, 벨만 포드 알고리즘의 자세한 내용은 여기를 참고.

 간단히 요약하자면, 노드 수를 n이라 하면, 모든 노드에 대한 relaxation을 n-1번 진행한다. 아래의 코드를 보면 총 3중 for문으로 구성되는데, 첫 번째 for문이 relaxation을 n-1번 진행할 때의 n-1이고, 두 번째 for문이 relaxation을 수행하는 노드이고, 마지막 for문이 relaxation을 수행하기 위한 두 번째 for문의 변수 노드의 이웃 탐사가 된다.

 여기서 머리 아픈 문제는 음의 루프가 존재해서 루프를 돌수록 시간이 무한히 과거로 가는 것인데, n-1번의 모든 노드에 대한 relaxation이 모두 이루어지면 더이상 relaxation이 이루어지지 않는다는 점을 활용하여, relaxation을 한번 더 수행하여 relaxation이 일어난다면 음의 루프가 있다고 판정한다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
def bf(n,edge):
  INF = 999999999
  dist = [0,0] + [INF for _ in range(n-1)]
  
  for count in range(1,n+1):
    for a in range(1,n+1):
      if dist[a] != INF :
        for b,c in edge[a].items():
          if dist[b] > dist[a]+c :
            dist[b] = dist[a]+c
            if count == n:
              print(-1)
              return
  for a in range(2,n+1):
    print(dist[a] if dist[a] != INF else -1)
 
 
if __name__=="__main__":
  n,m = map(int,sys.stdin.readline().split())
  edge = {}
  for a in range(1,n+1):
    edge[a]={}
  for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    edge[a][b]= min(c,edge[a][b]) if b in edge[a] else c
  bf(n,edge)
 cs

 

Line 4 : 1번노드에서 i번 노드까지 걸리는 시간으로, n개의 노드가 1부터 n이므로 0을 사용하지 않기 위해 0번째와 1번째를 0으로 하고 뒤부터는 INF로 초기화한다.

Line 6 : n-1 +1 번 모든 노드에 대한 relaxation을 수행한다고 했는데, relaxation이 몇 회차인지를 나타내는 첫 번째 for문이 된다.

Line 7 : relaxation을 수행하는 노드로 두번째 for문이 된다.

Line 8 : relaxation을 수행하는 노드가 아직 접근할 수 없는 노드이면 relaxation을 수행하지 않는다.

Line 9 : Line 7의 노드의 이웃들을 탐사하는 마지막 for문이 된다.

Line 12 : 음의 루프를 탐사하기 위한 조건으로, n번째에는 relaxation이 일어나면 안 된다.

Line 21 : 링크들이 담겨있는 딕셔너리로, key는 노드 번호이고, value는 (key가 도착 노드, value가 걸리는 시간)인 딕셔너리이다.

 

문제 링크

 

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
백준 1002 터렛  (0) 2020.04.09
백준 11048 이동하기  (0) 2020.03.30
백준 10610 30  (0) 2020.03.28
반응형

문제풀이

 원의 접점의 개수를 구하는 문제이다.

 두 원의 반지름 r1, r2 중 작은 것을 r, 큰 것을 R, 중심 사이의 거리를 dist라 할 때, 접점의 개수는 다음과 같다.

 접점이 한 개인 경우 : 내접(dist + r == R) 또는 외접(dist == r + R)

 없는 경우 : 두 점 사이의 거리가 반지름의 합보다 큰 경우(dist > r+R), 또는 큰 원 안에 작은 원이 들어가 있는 경우(dist + r < R)

 두 개인 경우 : 나머지

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys, math
def solution(x1,y1,r1,x2,y2,r2):
  if x1 == x2 and y1 == y2 :
    if r1 == r2:
      return -1
    else :
      return 0
  
  dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
  r = min(r1,r2)
  R = max(r1,r2)
  s = r + R
 
  #떨어져서 또는 큰원 안에 작은 원
  if dist > s or (dist + r < R): return 0
 
  #내접, 내접
  elif dist + r == R or dist == s: return 1
 
  else : return 2
 
if __name__=="__main__":
  n = int(sys.stdin.readline())
  for _ in range(n):
    x1,y1,r1,x2,y2,r2 = map(int,sys.stdin.readline().split())
    print(solution(x1,y1,r1,x2,y2,r2))
 cs

문제 링크

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 9465 스티커  (0) 2020.04.18
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 11048 이동하기  (0) 2020.03.30
백준 10610 30  (0) 2020.03.28
백준 2436 공약수  (0) 2020.03.24

+ Recent posts

티스토리툴바