척척석사의 코딩기록

수의 이진표현에 대한 문제가 되겠다.

import math
a,b = map(int,input().split())

def f(a,b):
    if a == 0 and b == 0:
        return -1
    elif a == 0 and b != 0:
        return "-"
    elif a == 1 and b == 1:
        return "*"
    #이제 비트마스킹을 활용해야함
    else:
        for i in range (1,64):
            t = a * ((2 ** i) - 1) // b
            if b * t == a * ((2 ** i) - 1):
                x = format(t, 'b') #주어진 숫자를 2진수로 변환해야할 필요가 있음
                if i >= len(x):
                    new_x = "0" * (i - len(x)) + x
                    ans = ""
                    for j in range (0,i):
                        if new_x[j] == "0":
                            ans += "-"
                        else:
                            ans += "*"
                    if len(ans) >= 61:
                        return -1
                    return ans
        return -1
print(f(a,b))

재밌는 문제였던 것 같다.

N = int(input())
R = N // 2 #반지름이 되겠다
def f(n):
    x,y = 0,n-1
    cnt = 0
    dx,dy = [1,0,1], [0,-1,-1]
    while x != y:
        for i in range (0,3):
            xx,yy = x + dx[i], y + dy[i]
            if xx ** 2 + yy ** 2 < n ** 2 and (xx + 1) ** 2 + (yy + 1) ** 2 > n ** 2:
                cnt += 1
                x,y = xx, yy
                break
    return 8 * cnt + 4
print(f(R))

반지름을 어떻게 활용할지에 대한 중요한 문제가 될 것 같다.

그래프이론을 좀 더 공부해보다가 이런 문제를 발견해서 바로 덥석 풀어봤는데 생각보다 걸리긴했네요.

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, L, R = map(int, input().split())
graph = []
for _ in range (0,N):
    a = list(map(int,input().split()))
    graph.append(a)

#L이상 R이하인 경우에는 모두 열림
dx,dy = [0,0,1,-1],[1,-1,0,0]
def bfs(mapp,cnt):
    visited = [[False for _ in range(0, N)] for _ in range(0, N)]
    pt = []
    for i in range (0,N):
        for j in range (0,N):
            for k in range (0,4):
                ii = i+dx[k]
                jj = j+dy[k]
                if 0 <= ii < N and 0 <= jj < N and L <= abs(mapp[ii][jj] - mapp[i][j]) <= R:
                    pt.append([i,j])
    if len(pt) == 0:
        return cnt
    ptt = []
    for x in pt:
        if visited[x[0]][x[1]] == False:
            deq = deque()
            deq.append(x)
            cnting = 0
            summary = 0
            pts = []
            while deq:
                z = deq.popleft()
                xx,yy = z[0], z[1]
                if visited[xx][yy] == False:
                    pts.append([xx,yy])
                    summary += mapp[xx][yy]
                    cnting += 1
                    visited[xx][yy] = True
                    for i in range (0,4):
                        a,b = xx + dx[i], yy + dy[i]
                        if 0 <= a < N and 0 <= b < N and L <= abs(mapp[a][b] - mapp[xx][yy]) <= R and visited[a][b] == False:
                            deq.append([a,b])
            ptt.append([pts, summary, cnting])
    for y in ptt:
        pts = y[0]
        t = int(y[-2] / y[-1])
        for pt in pts:
            aa,bb = pt[0],pt[1]
            mapp[aa][bb] = t
    return bfs(mapp, cnt + 1)

t = bfs(graph, 0)
print(t)

5월로 계약직으로 일하는곳도 종료되는만큼, 프로그래밍에도 좀 더 신경을 써보고자 한다.

생각보다는 쉽게 풀었던 문제인데, 

from collections import deque
N = int(input())
gp = [[] for _  in range (0,N+1)]
for _ in range (0,N-1):
    a,b = map(int,input().split())
    gp[a].append(b)
    gp[b].append(a)
depth = [[] for _ in range (0,N+1)]
depth[1] = (1,1)
deq = deque()
check = [False for _ in range (0,N+1)]
new_graph = [[] for _ in range (0,N+1)]
deq.append((1,1))
while deq:
    x = deq.popleft()
    x,y = x[0], x[1]
    check[x] = True
    for z in gp[x]:
        if check[z] == False:
            deq.append((z,y + 1))
            new_graph[x].append((z,y+1))
            
ans = [0 for _ in range (0,N+1)]

for i in range (0,N+1):
    if new_graph[i] != []:
        for x in new_graph[i]:
            ans[x[0]] = i

for i in range (2,N+1):
    print(ans[i])

말이 어렵게 쓰여있지만, 결국 해답은 뭐냐면 

다각형의 세 점을 이어서 만들 수 있는 삼각형 중 가장 넓이가 큰 것을 찾으시오 라는 문제가 되겠습니다.

여기서, 아이디어로서 사용되는 것은 신발끈 정리입니다.

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

좌표 평면에 점의 좌표가 주어져 있을 때 다각형의 넓이를 구할 수 있게 도와주는 공식이예요.

이를 활용해 아래와 같이 코드를 짤 수 있겠습니다.

def area의 부분이 넓이를 구하는 함수가 되겠습니다.

from itertools import combinations
import math
def area(a,b,c):
    x1,y1 = a[0],a[1]
    x2,y2 = b[0],b[1]
    x3,y3 = c[0],c[1]
    return int(math.fabs(x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3)) * 1/2
ans = -1
N = int(input())
pts = []
for _ in range (0,N):
    pt = list(map(int,input().split()))
    pts.append(pt)

for t in combinations(pts,3):
    t = list(t)
    a,b,c = t[0],t[1],t[2]
    ans = max(ans, area(a,b,c))
print(ans)

from collections import defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
cnt = defaultdict(int)
length = defaultdict(int)
for _ in range (0,N):
    a = input().rstrip()
    if len(a) >= M:
        cnt[a] += 1
        length[a] = len(a)
words = []
dd =  list(cnt.keys())
for word in dd:
    words.append([word, cnt[word], length[word]])

words.sort(key = lambda x:(-x[1],-x[2],x[0]))
for word in words:
    print(word[0])

문자열 정렬을 어떤 우선순위에 따라서 둘 것인지 확인해야할 필요가 있습니다.

key = lambda의 사용법을 익히기에 좋을 것 같습니다.

import sys
sys.setrecursionlimit(10000)

N,M = map(int,input().split())
x,y,di = map(int,input().split())
mapp = []
for _ in range (0,N):
    a = list(map(int,input().split()))
    mapp.append(a)

direction =[[-1,0],[0,1],[1,0],[0,-1]]
check = [[False for _ in range (0,M)] for _ in range (0,N)]
#di는 방향을 나타내고 있는 것
    
def algo(x,y,di):
    cnt = 0
    while True:
        if mapp[x][y] == 0 and check[x][y] == False:
            cnt += 1
            check[x][y] = True
    #첫번째 스텝에서 진행하는 자리가 더러우면 청소하는 경우
    #자신의 4방향 탐지하기
        jud = True
        for i in range (1,5):
        #반시계방향부터 탐색한다는 것에 유의
            t = (di - i) % 4
            xx = x + direction[t][0]
            yy = y + direction[t][1]
            if 0 <= xx < N and 0 <= yy < M:
                if mapp[xx][yy] == 0 and check[xx][yy] == False:
                    jud = False
                    x,y,di = xx,yy,t
                    break
        if jud == True:
            a = x - direction[di][0]
            b = y - direction[di][1]
            if mapp[a][b] == 1 or (0 > a or a == N or 0 > b or M == b):
                print(cnt)
                return
            x,y = a,b        
algo(x,y,di)

시간이 좀 오래 걸렸던 문제 ... 다 짜놓고서 이상한 곳에서 뻘짓을 많이했던 기억이 ....

import copy
N,M = map(int,input().split())
mapp = []
check = [[0 for _ in range (0,M)] for _ in range (0,N)]
camera = []
dx,dy = [1,0,-1,0], [0,1,0,-1]
for i in range (0,N):
    a = list(map(int,input().split()))
    mapp.append(a)
    for j in range (0,M):
        if 1 <= a[j] <= 5:
            camera.append([a[j], i,j])
ans = int(1e9)
pattern = [[],[[0],[1],[2],[3]],[[0,2],[1,3]],[[0,1],[1,2],[2,3],[3,0]],[[0,1,2],[1,2,3],[2,3,0],[3,0,1]],[[0,1,2,3]]]
#pattern은 카메라 종류를 지시함
#카메라의 x,y는 위치
def view(area,mode,x,y):
    for i in mode:
        a,b = x,y
        while True:
            a += dx[i]
            b += dy[i]
            if 0 <= a < N and 0 <= b < M:
                if area[a][b] == 0:
                    area[a][b] = -1
                elif area[a][b] == 6:
                    break
            else:
                break
            
def dfs(depth, area):
    global ans
    if depth == len(camera):
        cnt = 0
        for i in range (0,N):
            cnt += area[i].count(0)
        ans = min(ans,cnt)
        area = copy.deepcopy(mapp)
        return
    
    new_area = copy.deepcopy(area)
    cctv,x,y = camera[depth]
    for i in pattern[cctv]:
        view(new_area,i,x,y)
        dfs(depth + 1, new_area)
        new_area = copy.deepcopy(area)
dfs(0,mapp)
print(ans)

삼성은 이런 카테고리의 문제를 많이 내는구나 싶었다.

백트래킹 / dfs를 잘 익힌 다음에 시험 보러 가는 것이 좋을 것 같다